The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols

Abstract

Hada and Tanaka showed the existence of 3-round, negligible-error zero-knowledge arguments for NP based on a pair of non-standard assumptions, here called KEA1 and KEA2. In this paper we show that KEA2 is false. This renders vacuous the results of Hada and Tanaka. We recover these results, however, under a suitably modified new assumption called KEA3. What we believe is most interesting is that we show that it is possible to falsify'' assumptions like KEA2 that, due to their nature and quantifier-structure, do not lend themselves easily to efficient falsification'' (Naor).

Available format(s)
Publication info
Published elsewhere. A preliminary version appeared in Crypto 2004. This is the full version.
Keywords
zero-knowledgefoundationsassumptionsdiscrete log
Contact author(s)
mihir @ cs ucsd edu
History
2004-05-24: revised
See all versions
Short URL
https://ia.cr/2004/008

CC BY

BibTeX

@misc{cryptoeprint:2004/008,
author = {Mihir Bellare and Adriana Palacio},
title = {The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols},
howpublished = {Cryptology ePrint Archive, Paper 2004/008},
year = {2004},
note = {\url{https://eprint.iacr.org/2004/008}},
url = {https://eprint.iacr.org/2004/008}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.