Efficient zero-knowledge identification schemes which respect privacy

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 reconsider the analysis of these schemes. We firstly propose a framework which enables to transform some generic ZK scheme into private scheme. We then apply as a relevant example this framework to the GPS scheme. This leads to efficient implementations of zero-knowledge identification schemes which respect privacy. Their security and their privacy are based on the problem of the Short Exponent Decisional Diffie-Hellman problem.