Institutional Research Information Service
UCL Logo
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at http://www.ucl.ac.uk/finance/research/post_award/post_award_contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
Non-interactive Zaps and New Techniques for NIZK
  • Publication Type:
  • Authors:
    Groth J, Ostrovsky R, Sahai A
  • Publisher:
  • Publication date:
  • Pagination:
    97, 111
  • Volume:
  • Series:
    Lecture Notes in Computer Science
  • Editors:
    Dwork C
  • ISBN-13:
  • Status:
  • Name of conference:
    Advances in Cryptology - CRYPTO: 26th Annual International Cryptology Conference
  • Conference place:
    Santa Barbara, US
  • Conference start date:
  • Conference finish date:
  • Keywords:
    Non-interactive zero-knowledge, witness indistinguishability, bilinear groups, Decisional Linear Assumption.
In 2000, Dwork and Naor proved a very surprising result: that there exist “Zaps”, two-round witness-indistinguishable proofs in the plain model without a common reference string, where the Verifier asks a single question and the Prover sends back a single answer. This left open the following tantalizing question: does there exist a non-interactive witness indistinguishable proof, where the Prover sends a single message to the Verifier for some non-trivial NP-language? In 2003, Barak, Ong and Vadhan answered this question affirmatively by derandomizing Dwork and Naor’s construction under a complexity theoretic assumption, namely that Hitting Set Generators against co-nondeterministic circuits exist. In this paper, we construct non-interactive Zaps for all NP-languages. We accomplish this by introducing new techniques for building Non- Interactive Zero Knowledge (NIZK) Proof and Argument systems, which we believe to be of independent interest, and then modifying these to yield our main result. Our construction is based on the Decisional Linear Assumption, which can be seen as a bilinear group variant of the Decisional Diffie-Hellman Assumption. Furthermore, our single message witness-indistinguishable proof for Circuit Satisfiability is of size O(k|C|) bits, where k is a security parameter, and |C| is the size of the circuit. This is much more efficient than previous constructions of 1- or 2-move Zaps.
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
UCL Researchers
Dept of Computer Science
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by