Paper 2012/572

On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption

Divya Gupta and Amit Sahai

Abstract

In this work, we consider the long-standing open question of constructing constant-round concurrent zero-knowledge protocols in the plain model. Resolving this question is known to require non-black-box techniques. We consider non-black-box techniques for zero-knowledge based on knowledge assumptions, a line of thinking initiated by the work of Hada and Tanaka (CRYPTO 1998). Prior to our work, it was not known whether knowledge assumptions could be used for achieving security in the concurrent setting, due to a number of significant limitations that we discuss here. Nevertheless, we obtain the following results: 1. We obtain the first constant round concurrent zero-knowledge argument for \textbf{NP} in the plain model based on a new variant of knowledge of exponent assumption. Furthermore, our construction avoids the inefficiency inherent in previous non-black-box techniques such that those of Barak (FOCS 2001); we obtain our result through an efficient protocol compiler. 2. Unlike Hada and Tanaka, we do not require a knowledge assumption to argue the soundness of our protocol. Instead, we use a discrete log like assumption, which we call Diffie-Hellman Logarithm Assumption, to prove the soundness of our protocol. 3. We give evidence that our new variant of knowledge of exponent assumption is in fact plausible. In particular, we show that our assumption holds in the generic group model. 4. Knowledge assumptions are especially delicate assumptions whose plausibility may be hard to gauge. We give a novel framework to express knowledge assumptions in a more flexible way, which may allow for formulation of plausible assumptions and exploration of their impact and application in cryptography.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Concurrent Zero-KnowledgeKnowledge AssumptionsNon-Black-Box Techniques
Contact author(s)
divyag @ cs ucla edu
sahai @ cs ucla edu
History
2012-10-14: received
Short URL
https://ia.cr/2012/572
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/572,
      author = {Divya Gupta and Amit Sahai},
      title = {On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2012/572},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/572}},
      url = {https://eprint.iacr.org/2012/572}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.