International Association for Cryptologic Research

International Association
for Cryptologic Research


Thomas Icart


Identification and Privacy: Zero-Knowledge is not Enough
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.
Strengthening the Tree-Based Hash Protocols against Compromise of some Tags
In 2004, Molnar and Wagner introduced in [6] a very appealing scheme dedicated to the identification of RFID tags. Their protocol relies on a binary tree of secrets which are shared -- for all nodes except the leaves -- amongst the tags. Hence the compromise of one tag also has implications on the other tags with whom it shares keys. We introduce a modification of the initial scheme to allow us to strengthen RFID tags by implementing secrets with Physical Obfuscated Keys (POK). This doing, we augment tags and tree resistance against physical threats.
Efficient Scalar Multiplication by Isogeny Decompositions
On an elliptic curve, the degree of an isogeny corresponds essentially to the degrees of the polynomial expressions involved in its application. The multiplication--by--$\ell$ map $[\ell]$ has degree~$\ell^2$, therefore the complexity to directly evaluate $[\ell](P)$ is $O(\ell^2)$. For a small prime $\ell\, (= 2, 3)$ such that the additive binary representation provides no better performance, this represents the true cost of application of scalar multiplication. If an elliptic curves admits an isogeny $\varphi$ of degree $\ell$ then the costs of computing $\varphi(P)$ should in contrast be $O(\ell)$ field operations. Since we then have a product expression $[\ell] = \hat{\varphi}\varphi$, the existence of an $\ell$-isogeny $\varphi$ on an elliptic curve yields a theoretical improvement from $O(\ell^2)$ to $O(\ell)$ field operations for the evaluation of $[\ell](P)$ by na\"ive application of the defining polynomials. In this work we investigate actual improvements for small $\ell$ of this asymptotic complexity. For this purpose, we describe the general construction of families of curves with a suitable decomposition $[\ell] = \hat{\varphi}\varphi$, and provide explicit examples of such a family of curves with simple decomposition for~$[3]$. Finally we derive a new tripling algorithm to find complexity improvements to triplication on a curve in certain projective coordinate systems, then combine this new operation to non-adjacent forms for $\ell$-adic expansions in order to obtain an improved strategy for scalar multiplication on elliptic curves.