Yehuda Lindell

STOC Conference 2008 Conference Paper

Complete fairness in secure two-party computation

• S. Dov Gordon
• Carmit Hazay
• Jonathan Katz
• Yehuda Lindell

STOC Conference 2006 Conference Paper

Black-box constructions for secure computation

• Yuval Ishai
• Eyal Kushilevitz
• Yehuda Lindell
• Erez Petrank

It is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. We study the way such computational assumptions are used. Specifically, we ask whether the secure protocol can use the underlying primitive (e.g., one-way trapdoor permutation) in a black-box way, or must it be nonblack-box (by referring to the code that computes this primitive)? Despite the fact that many general constructions of cryptographic schemes (e.g., CPA-secure encryption) refer to the underlying primitive in a black-box way only, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).In this paper, we study whether such nonblack-box use is essential. We present protocols that use only black-box access to a family of (enhanced) trapdoor permutations or to a homomorphic public-key encryption scheme. The result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive (e.g., a trapdoor permutation) and whose computational complexity grows only linearly with that of the underlying primitive. This is the first protocol to exhibit these properties.

STOC Conference 2006 Conference Paper

Information-theoretically secure protocols and security under composition

• Eyal Kushilevitz
• Yehuda Lindell
• Tal Rabin

STOC Conference 2005 Conference Paper

Concurrent general composition of secure protocols in the timing model

• Yael Tauman Kalai
• Yehuda Lindell
• Manoj Prabhakaran 0001

STOC Conference 2003 Conference Paper

Bounded-concurrent secure two-party computation without setup assumptions

• Yehuda Lindell

FOCS Conference 2003 Conference Paper

General Composition and Universal Composability in Secure Multi-Party Computation

• Yehuda Lindell

Concurrent general composition relates to a setting where a secure protocol is run in a network concurrently with other, arbitrary protocols. Clearly, security in such a setting is what is desired, or even needed, in modern computer networks where many different protocols are executed concurrently. Our main result is a proof that security under concurrent general composition is equivalent to a relaxed variant of universal composability (where the only difference relates to the order of quantifiers in the definition). An important corollary of this theorem is that existing impossibility results for universal composability (or actually its relaxed variant) are inherent in any definition achieving security under concurrent general composition. We stress that the impossibility results obtained are not "black-box", and apply even to non-black-box simulation. Our main result also demonstrates that the definition of universal composability is somewhat "minimal", in that the composition guarantee provided by universal composability (almost) implies the definition itself. This indicates that the security definition of universal composability is not overly restrictive.

FOCS Conference 2003 Conference Paper

Lower Bounds for Non-Black-Box Zero Knowledge

• Boaz Barak
• Yehuda Lindell
• Salil P. Vadhan

We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a constant-round zero-knowledge strong proof (or argument) of knowledge (as defined by Goldreich, 2001) for a nontrivial language; 2. There does not exist a two-round zero-knowledge proof system with perfect completeness for an NP-complete language; 3. There does not exist a constant-round public-coin proof system for a nontrivial language that is resettable zero knowledge. This result also extends to bounded resettable zero knowledge. In contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) argument system that is bounded-resettable zero knowledge.

STOC Conference 2002 Conference Paper

On the composition of authenticated byzantine agreement

• Yehuda Lindell
• Anna Lysyanskaya
• Tal Rabin

STOC Conference 2002 Conference Paper

Strict polynomial-time in simulation and extraction

• Boaz Barak
• Yehuda Lindell

STOC Conference 2002 Conference Paper

Universally composable two-party and multi-party secure computation

• Ran Canetti
• Yehuda Lindell
• Rafail Ostrovsky
• Amit Sahai

We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.

FOCS Conference 2001 Conference Paper

Resettably-Sound Zero-Knowledge and its Applications

• Boaz Barak
• Oded Goldreich 0001
• Shafi Goldwasser
• Yehuda Lindell

Resettably-sound proofs and arguments maintain soundness even when the prover can reset the verifier to use the same random coins in repeated executions of the protocol. We show that resettably-sound zero-knowledge arguments for NP exist if collision-free hash functions exist. In contrast, resettably-sound zero-knowledge proofs are possible only for languages in P/poly. We present two applications of resettably-sound zero-knowledge arguments. First, we construct resettable zero-knowledge arguments of knowledge for NP, using a natural relaxation of the definition of arguments (and proofs) of knowledge. We note that, under the standard definition of proof of knowledge, it is impossible to obtain resettable zero-knowledge arguments of knowledge for languages outside BPP. Second, we construct a constant-round resettable zero-knowledge argument for NP in the public-key model, under the assumption that collision-free hash functions exist. This improves upon the sub-exponential hardness assumption required by previous constructions. We emphasize that our results use non-black-box zero-knowledge simulations. Indeed, we show that some of the results are impossible to achieve using black-box simulations. In particular, only languages in BPP have resettably-sound arguments that are zero-knowledge with respect to black-box simulation.