International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Identification and Privacy: Zero-Knowledge is not Enough

Authors:
Julien Bringer
Hervé Chabanne
Thomas Icart
Download:
URL: http://eprint.iacr.org/2008/229
Search ePrint
Search Google
Abstract: At first glance, privacy and zero-knowledgeness seem to be similar properties. A scheme is private when no information is revealed on the prover and in a zero-knowledge scheme, communications should not leak provers' secrets. Until recently, privacy threats were only partially formalized and some zero-knowledge (ZK) schemes have been proposed so far to ensure privacy. We here explain why the intended goal is not reached. Following the privacy model proposed by Vaudenay at Asiacrypt 2007, we then reconsider the analysis of these schemes and thereafter introduce a general framework to modify identification schemes leading to different levels of privacy. Our new protocols can be useful, for instance, for identity documents, where privacy is a great issue. Furthermore, we propose efficient implementations of zero-knowledge and private identification schemes based on modifications of the GPS scheme. The security and the privacy are based on a new problem: the Short Exponent Strong Diffie-Hellman (SESDH) problem. The hardness of this problem is related to the hardness of the Strong Diffie-Hellman (SDH) problem and to the hardness of the Discrete Logarithm with Short Exponent (DLSE) problem. The security and privacy of these new schemes are proved in the random oracle paradigm.
BibTeX
@misc{eprint-2008-17906,
  title={Identification and Privacy: Zero-Knowledge is not Enough},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / Identification, Privacy, Zero-Knowledge},
  url={http://eprint.iacr.org/2008/229},
  note={ thomas.icart@sagem.com 14019 received 20 May 2008},
  author={Julien Bringer and Hervé Chabanne and Thomas Icart},
  year=2008
}