Cryptology ePrint Archive: Report 2008/229

Identification and Privacy: Zero-Knowledge is not Enough

Julien Bringer and Herve Chabanne and Thomas Icart

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.

Category / Keywords: cryptographic protocols / Identification, Privacy, Zero-Knowledge

Date: received 20 May 2008

Contact author: thomas icart at sagem com

Available format(s): PDF | BibTeX Citation

Version: 20080526:025409 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]