## CryptoDB

### Shien Jin Ong

#### Affiliation: Harvard University

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Fairness with an Honest Minority and a Rational Majority
Abstract

We provide a simple protocol for secret reconstruction in any threshold secret sharing scheme, and prove that it is fair when executed with many rational parties together with a small minority of honest parties. That is, all parties will learn the secret with high probability when the honest parties follow the protocol and the rational parties act in their own self-interest (as captured by the notion of a Bayesian subgame perfect equilibrium). The protocol only
requires a standard (synchronous) broadcast channel, and tolerates fail-stop deviations (i.e. early stopping, but not incorrectly computed messages).
Previous protocols for this problem in the cryptographic or economic models have either required an honest majority, used strong communication channels that enable simultaneous exchange of information, or settled for approximate notions of security/equilibria.

2006

EPRINT

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function
Abstract

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 the verifier to accept a false assertion except with
negligible probability. This resolves an open question posed by Naor,
Ostrovsky, Venkatesan, and Yung (CRYPTO `92, J. Cryptology `98).
Departing from previous works on this problem, we do not construct
standard statistically hiding commitments from any one-way function.
Instead, we construct a relaxed variant of commitment schemes called
"1-out-of-2-binding commitments," recently introduced by Nguyen and
Vadhan (STOC `06).

2006

EPRINT

Zero Knowledge and Soundness are Symmetric
Abstract

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems. This characterization is symmetric in its treatment of the zero knowledge and the soundness conditions, and thus we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. Furthermore, we show that a problem in NP has a *statistical* zero-knowledge argument system if and only if its complement has a computational zero-knowledge *proof* system. What is novel about these results is that they are *unconditional*, i.e., do not rely on unproven complexity assumptions such as the existence of one-way functions.
Our characterization of zero-knowledge arguments also enables us to prove a variety of other unconditional results about the class of problems in NP having zero-knowledge arguments, such as equivalences between honest-verifier and malicious-verifier zero knowledge, private coins and public coins, inefficient provers and efficient provers, and non-black-box simulation and black-box simulation. Previously, such results were only known unconditionally for zero-knowledge *proof systems*, or under the assumption that one-way functions exist for zero-knowledge argument systems.

2005

EPRINT

Concurrent Zero Knowledge without Complexity Assumptions
Abstract

We provide unconditional constructions of concurrent 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 (coNP forms of the) Shortest Vector Problem and Closest Vector Problem in lattices.
For some of the problems, such as Graph Isomorphism and Quadratic Residuosity, the proof systems have provers that can be implemented in polynomial time (given an NP witness) and have \tilde{O}(log n) rounds, which is known to be essentially optimal for black-box simulation.
To our best of knowledge, these are the first constructions of concurrent zero-knowledge protocols in the asynchronous model (without timing assumptions) that do not require complexity assumptions (such as the existence of one-way functions).

2005

EPRINT

Derandomization in Cryptography
Abstract

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 setup assumption, so it is actually an "NP proof system."
A noninteractive bit commitment scheme based on any one-way function.
The specific NW-type generator we need is a hitting set generator fooling nondeterministic circuits. It is known how to construct such a generator if ETIME = DTIME(2^O(n)) has a function of nondeterministic circuit complexity 2^\Omega(n) (Miltersen and Vinodchandran, FOCS `99).
Our witness-indistinguishable proofs are obtained by using the NW-type generator to derandomize the ZAPs of Dwork and Naor (FOCS `00). To our knowledge, this is the first construction of an NP proof system achieving a secrecy property.
Our commitment scheme is obtained by derandomizing the interactive commitment scheme of Naor (J. Cryptology, 1991). Previous constructions of noninteractive commitment schemes were only known under incomparable assumptions.

#### Coauthors

- Boaz Barak (2)
- Daniele Micciancio (2)
- Minh-Huyen Nguyen (1)
- David C. Parkes (2)
- Alon Rosen (2)
- Amit Sahai (2)
- Salil P. Vadhan (10)