Abstract
Denoting by P=[k]G the elliptic-curve double-and-add multiplication of a public base point G by a secret k, we show that allowing an adversary access to the projective representation of P, obtained using a particular double and add method, may result in information being revealed about k.
Such access might be granted to an adversary by a poor software implementation that does not erase the Z coordinate of P from the computer’s memory or by a computationally-constrained secure token that sub-contracts the affine conversion of P to the external world.
From a wider perspective, our result proves that the choice of representation of elliptic curve points can reveal information about their underlying discrete logarithms, hence casting potential doubt on the appropriateness of blindly modelling elliptic-curves as generic groups.
As a conclusion, our result underlines the necessity to sanitize Z after the affine conversion or, alternatively, randomize P before releasing it out.
Chapter PDF
Similar content being viewed by others
References
Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic Curves in Cryptography. Cambridge University Press, Cambridge (1999)
Brown, D.: Generic Groups, Collision Resistance, and ECDSA, ePrint Report 2002/026, http://eprint.iacr.org/
Howgrave-Graham, N.A., Smart, N.P.: Lattice attacks on digital signature schemes. Designs, Codes and Cryptography 23, 283–290 (2001)
IEEE 1363, IEEE standard specifications for public key cryptography (2000)
Joux, A., Stern, J.: Lattice Reduction: a Toolbox for the Cryptanalyst. Journal of Cryptology 11, 161–186 (1998)
López, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in GF(2n). In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 201–212. Springer, Heidelberg (1999)
Nguyen, P., Shparlinski, I.: The Insecurity of the Digital Signature Algorithm with Partially Known Nonces. Journal of Cryptology 15, 151–176 (2002)
Nguyen, P., Stern, J.: The hardness of the subset sum problem and its cryptographic implications. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 31–46. Springer, Heidelberg (1999)
Pointcheval, D., Stern, J.: Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology 13, 361–396 (2000)
Smart, N.P.: The Exact Security of ECIES in the Generic Group Model. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 73–84. Springer, Heidelberg (2001)
Stern, J., Pointcheval, D., Malone-Lee, J., Smart, N.P.: Flaws in Applying Proof Methodologies to Signature Schemes. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 93–110. Springer, Heidelberg (2002)
Schnorr, C.P.: Efficient Signature Generation by Smart Cards. Journal of Cryptology 4, 161–174 (1991)
U.S. Department of Commerce, National Institute of Standards and Technology. Digital Signature Standard. Federal Information Processing Standard Publication 186 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Naccache, D., Smart, N.P., Stern, J. (2004). Projective Coordinates Leak. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology - EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-24676-3_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21935-4
Online ISBN: 978-3-540-24676-3
eBook Packages: Springer Book Archive