Cynthia Dwork, Moni Naor

A zap is a two-round, witness-indistinguishable protocol in which

the first round, consisting of a message from the verifier to the

prover, can be fixed ``once-and-for-all" and applied to any instance,

and where the verifier does not use any private coins.

We present a zap for every language in NP, ...
more >>>

Danny Harnik, Moni Naor

We initiate the study of the compressibility of NP problems. We

consider NP problems that have long instances but relatively

short witnesses. The question is, can one efficiently compress an

instance and store a shorter representation that maintains the

information of whether the original input is in the language or

more >>>

Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

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

Brett Hemenway, Rafail Ostrovsky

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings.

Our main result is to show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for ...
more >>>

Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the partiesâ€™ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... more >>>