All reports by Author Shien Jin Ong:

__
TR06-139
| 14th November 2006
__

Shien Jin Ong, Salil Vadhan#### Zero Knowledge and Soundness are Symmetric

Revisions: 1

__
TR06-075
| 19th June 2006
__

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan#### Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

__
TR05-114
| 9th October 2005
__

Boaz Barak, Shien Jin Ong, Salil Vadhan#### Derandomization in Cryptography

__
TR05-093
| 24th August 2005
__

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan#### Concurrent Zero Knowledge without Complexity Assumptions

Shien Jin Ong, Salil Vadhan

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. ... more >>>

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan

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

Boaz Barak, Shien Jin Ong, Salil Vadhan

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... more >>>

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

We provide <i>unconditional</i> constructions of <i>concurrent</i>

statistical zero-knowledge proofs for a variety of non-trivial

problems (not known to have probabilistic polynomial-time

algorithms). The problems include Graph Isomorphism, Graph

Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a

restricted version of Statistical Difference, and approximate

versions of the (<b>coNP</b> forms of the) Shortest Vector ...
more >>>