Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Oblivious Transfer:
TR02-001 | 8th January 2002
Cynthia Dwork, Moni Naor

Zaps and Their Applications

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

TR06-022 | 17th February 2006
Danny Harnik, Moni Naor

On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

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

TR10-020 | 19th February 2010
Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

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

TR10-127 | 9th August 2010
Brett Hemenway, Rafail Ostrovsky

Building Injective Trapdoor Functions From Oblivious Transfer

Revisions: 1

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

ISSN 1433-8092 | Imprint