Skip to main content
Top

2003 | OriginalPaper | Chapter

Derandomization in Cryptography

Authors : Boaz Barak, Shien Jin Ong, Salil Vadhan

Published in: Advances in Cryptology - CRYPTO 2003

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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:1) 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.”2) 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 E = TIME(2O(n)) has a function of nondeterministic circuit complexity 2Ω(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.

Metadata
Title
Derandomization in Cryptography
Authors
Boaz Barak
Shien Jin Ong
Salil Vadhan
Copyright Year
2003
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-540-45146-4_18

Premium Partner