All reports by Author Yehuda Lindell:

__
TR17-112
| 27th June 2017
__

Yehuda Lindell#### How To Simulate It -- A Tutorial on the Simulation Proof Technique

__
TR11-036
| 17th March 2011
__

Gilad Asharov, Yehuda Lindell#### A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation

Revisions: 5

__
TR11-003
| 10th January 2011
__

Yehuda Lindell#### Constant-Round Zero-Knowledge Proofs of Knowledge

Revisions: 1

__
TR04-083
| 8th September 2004
__

Boaz Barak, Yehuda Lindell, Salil Vadhan#### Lower Bounds for Non-Black-Box Zero Knowledge

__
TR04-063
| 23rd July 2004
__

Yehuda Lindell, Benny Pinkas#### A Proof of Yao's Protocol for Secure Two-Party Computation

Revisions: 1

__
TR02-026
| 7th April 2002
__

Boaz Barak, Yehuda Lindell#### Strict Polynomial-time in Simulation and Extraction

Revisions: 2

Yehuda Lindell

One of the most fundamental notions of cryptography is that of \emph{simulation}. It stands behind the concepts of semantic security, zero knowledge, and security for multiparty computation. However, writing a simulator and proving security via the use of simulation is a non-trivial task, and one that many newcomers to the ... more >>>

Gilad Asharov, Yehuda Lindell

In the setting of secure multiparty computation, a set of $n$ parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any $n$-party functionality ... more >>>

Yehuda Lindell

In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all $\cal NP$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge \emph{arguments} of knowledge was proven by Feige and Shamir (CRYPTO ... more >>>

Boaz Barak, Yehuda Lindell, Salil Vadhan

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:

<ol>

<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ...
more >>>

Yehuda Lindell, Benny Pinkas

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 >>>

Boaz Barak, Yehuda Lindell

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., ... more >>>