International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Mihir Bellare
Adriana Palacio
Download:
URL: http://eprint.iacr.org/2004/008
Search ePrint
Search Google
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).
BibTeX
@misc{eprint-2004-11984,
  title={The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols},
  booktitle={IACR Eprint archive},
  keywords={zero-knowledge, foundations, assumptions, discrete log},
  url={http://eprint.iacr.org/2004/008},
  note={A preliminary version appeared in Crypto 2004. This is the full version. mihir at cs dot ucsd dot edu 12562 received 10 Jan 2004, last revised 24 May 2004},
  author={Mihir Bellare and Adriana Palacio},
  year=2004
}