We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior to this work, for languages with greater-than-zero knowledge complexity (and specifically, even for knowledge complexity 1) only trivial computational complexity bounds ... more >>>

We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum, Feldman and Micali \cite{bfm}. Until recently there was a sizable polynomial gap between the most efficient noninteractive proofs for {\sf NP} based on general complexity assumptions \cite{fls} versus those based on specific algebraic assumptions \cite{Da}. Recently, ... more >>>

Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same construction can also be used to obtain collision-free hashing. more >>>

Following Ajtai's lead, Ajtai and Dwork have recently introduced a public-key encryption scheme which is secure under the assumption that a certain computational problem on lattices is hard on the worst-case. Their encryption method may cause decryption errors, though with small probability (i.e., inversely proportional to the security parameter). In ... more >>>

The Diffie-Hellman key-exchange protocol may naturally be extended to k>2 parties. This gives rise to the generalized Diffie-Hellman assumption (GDH-Assumption). Naor and Reingold have recently shown an efficient construction of pseudo-random functions and reduced the security of their construction to the GDH-Assumption. In this note, we prove that breaking this ... more >>>

Recently, Ajtai discovered a fascinating connection between the worst-case complexity and the average-case complexity of some well-known lattice problems. Later, Ajtai and Dwork proposed a cryptosystem inspired by Ajtai's work, provably secure if a particular lattice problem is difficult. We show that there is a converse to the Ajtai-Dwork security ... more >>>

This paper shows that the largest possible contrast C(k,n) in a k-out-of-n secret sharing scheme is approximately 4^(-(k-1)). More precisely, we show that 4^(-(k-1)) <= C_{k,n} <= 4^(-(k-1))}n^k/(n(n-1)...(n-(k-1))). This implies that the largest possible contrast equals 4^(-(k-1)) in the limit when n approaches infinity. For large n, the above bounds ... more >>>

\begin{abstract} A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator (PRFG) if communicating with a randomly chosen secret function from $F$ cannot be efficiently distinguished from communicating with a truly random function. We ask for the minimal hardware complexity of a PRFG. This question is motivated ... more >>>

Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a ``hidden'' element $\alpha$ of a finite field $\F_p$ of $p$ elements from rather short strings of the most significant bits of the remainder mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly at random ... more >>>

Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a ``hidden'' element $\alpha$ of a finite field $\F_p$ of $p$ elements from rather short strings of the most significant bits of the remainder mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly at random ... more >>>

Informally, an obfuscator O is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is "unintelligible" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic ... more >>>

Factoring integers is the most established problem on which cryptographic primitives are based. This work presents an efficient construction of {\em pseudorandom functions} whose security is based on the intractability of factoring. In particular, we are able to construct efficient length-preserving pseudorandom functions where each evaluation requires only a {\em ... more >>>

We consider the function ensembles emerging from the construction of Goldreich, Goldwasser and Micali (GGM), when applied to an arbitrary pseudoramdon generator. We show that, in general, such functions fail to yield correlation intractable ensembles. Specifically, it may happen that, given a description of such a function, one can easily ... more >>>

We study the role of connectivity of communication networks in private computations under information theoretic settings. It will be shown that some functions can be computed by private protocols even if the underlying network is 1-connected but not 2-connected. Then we give a complete characterisation of non-degenerate functions that can ... more >>>

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security ... more >>>

Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... more >>>

We study private computations in information-theoretical settings on networks that are not 2-connected. Non-2-connected networks are ``non-private'' in the sense that most functions cannot privately be computed on such networks. We relax the notion of privacy by introducing lossy private protocols, which generalize private protocols. We measure the information each ... more >>>

In the mid 1980's, Yao presented a constant-round protocol for securely computing any two-party functionality in the presence of semi-honest adversaries (FOCS 1986). In this paper, we provide a complete description of Yao's protocol, along with a rigorous proof of security. Despite the importance of Yao's protocol to the field ... more >>>

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S_A and S_B, respectively, such that with probability (1+eps)/2 these bits are equal. Further assume that conditioned on the event S_A = S_B no polynomial time bounded algorithm can predict the ... more >>>

We study the round complexity of two-party protocols for generating a random $n$-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). Specifically, we require that the output's ... more >>>

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. We establish several new characterizations of ZK, and use these characterizations to ... more >>>

We show that every language in NP has a *statistical* zero-knowledge argument system under the (minimal) complexity assumption that one-way functions exist. In such protocols, even a computationally unbounded verifier cannot learn anything other than the fact that the assertion being proven is true, whereas a polynomial-time prover cannot convince ... more >>>

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there is a polynomial-time computable function $f$ and a set $A$ such that for each instance ... more >>>

We develop new tools to study the relative complexities of secure multi-party computation tasks (functionalities) in the Universal Composition framework. When one task can be securely realized using another task as a black-box, we interpret this as a qualitative, complexity-theoretic reduction between the two tasks. Virtually all previous characterizations of ... more >>>

We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the i'th round of a protocol (A, B) has _accessible entropy_ at most k, if no polynomial-time strategy A^* can generate ... more >>>

The principal aim of this notes is to give a survey on the state of the art of algorithmic number theory, with particular focus on the theory of elliptic curves. Computational security is the goal of modern cryptographic constructions: the security of modern criptographic schemes stems from the assumption that ... more >>>

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$. This improves the best previously known algorithm by Ajtai, Kumar ... more >>>

In STOC '08, Peikert and Waters introduced a powerful new primitive called Lossy Trapdoor Functions (LTDFs). Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure (IND-CCA2) ... more >>>

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by ... more >>>