Paper 2008/229

Identification and Privacy: Zero-Knowledge is not Enough

Julien Bringer, 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.