Key Compression for Isogeny-Based Cryptosystems

Reza Azarderakhsh, David Jao, Kassem Kalach, Brian Koziel, Christopher Leonardi

Published May 24, 2016• 93 citations

Abstract

We present a method for key compression in quantumresistant isogeny-based cryptosystems, which allows a reduction in and transmission costs of per-party public information by a factor of two, with no e ect on security. We achieve this reduction by associating a canonical choice of elliptic curve to each j-invariant, and representing elements on the curve as linear combinations with respect to a canonical choice of basis. This method of compressing public information can be applied to numerous isogeny-based protocols, such as key exchange, zero-knowledge identi cation, and public-key encryption. We performed personal computer and ARM implementations of the key exchange with compression and decompression in C and provided timing results, showing the computational cost of key compression and decompression at various security levels. Our results show that isogeny-based cryptosystems achieve by far the smallest possible key sizes among all existing families of post-quantum cryptosystems at practical security levels; e.g. 3073-bit public keys at the quantum 128-bit security level, comparable to (non-quantum) RSA key sizes.

DOI: 10.1145/2898420.2898421

Related papers

On the Security of Supersingular Isogeny Cryptosystems.

Steven D. Galbraith⋆, Christophe Petit, Barak Shani +1 more

We study cryptosystems based on supersingular isogenies. This is an active area of research in post-quantum cryptography. Our first contribution is to give a very powerful active attack on the supersingular isogeny encryption scheme. This attack can only be prevented by using a (relatively expensive) countermeasure. Our second contribution is to show that the security of all schemes of this type depends on the difficulty of computing the endomorphism ring of a supersingular elliptic curve. This result gives significant insight into the difficulty of the isogeny problem that underlies the security of these schemes. Our third contribution is to give a reduction that uses partial knowledge of shared keys to determine an entire shared key. This can be used to retrieve the secret key, given information leaked from a side-channel attack on the key exchange protocol. A corollary of this work is the first bit security result for the supersingular isogeny key exchange: Computing any component of the j-invariant is as hard as computing the whole j-invariant.

Jan 1, 20160 citations

Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies

Luca De Feo, David Jao, Jérôme Plût

Abstract We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the non-commutativity of the endomorphism ring. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [Lecture Notes in Comput. Sci. 7071, Springer (2011), 19–34]. We add a new zero-knowledge identification scheme and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.

Journal of Mathematical CryptologyJun 11, 2014404 citations

Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.

David Jao, Luca De Feo

We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the noncommutativity of the endomorphism ring. Our work is motivated by the recent development of a subexponential-time quantum algorithm for constructing isogenies between ordinary elliptic curves. In the supersingular case, by contrast, the fastest known quantum attack remains exponential, since the noncommutativity of the endomorphism ring means that the approach used in the ordinary case does not apply. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [19]. We add a new zero-knowledge identification scheme, and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.

Jan 1, 20116 citations

Isogeny-Based Cryptography: A Promising Post-Quantum Technique

Cong Peng, Jianhua Chen, Sherali Zeadally +1 more

Recent advances in quantum computing have made existing public key cryptosystems vulnerable to enormous security threats. Therefore, numerous efforts have been exploring post-quantum cryptographic techniques to address the emergence of quantum computing. We focus on one promising post-quantum cryptography known as “isogeny-based cryptography,” first by reviewing some concepts of the elliptic curve isogeny, and then, we present three major methods for constructing isogeny-based difficult problems. Then, we present some existing isogeny-based cryptographic primitives, such as signature and key exchange, and analyze their advantages and disadvantages. Finally, we discuss a few major challenges of isogeny research that, we hope, will attract more attention to isogeny-based cryptography.

IT ProfessionalNov 1, 201924 citations

Post-Quantum Elliptic Curve Cryptography

Vladimir Soukharev

We propose and develop new schemes for post-quantum cryptography based on isogenies over elliptic curves. First we show that ordinary elliptic curves are have less than exponential security against quantum computers. These results were used as the motivation for De Feo, Jao and Pl\\^ut's construction of public key cryptosystems using supersingular elliptic curve isogenies. We extend their construction and show that isogenies between supersingular elliptic curves can be used as the underlying hard mathematical problem for other quantum-resistant schemes. For our second contribution, we propose is an undeniable signature scheme based on elliptic curve isogenies. We prove its security under certain reasonable number-theoretic computational assumptions for which no efficient quantum algorithms are known. This proposal represents only the second known quantum-resistant undeniable signature scheme, and the first such scheme secure under a number-theoretic complexity assumption. Finally, we also propose a security model for evaluating the security of authenticated encryption schemes in the post-quantum setting. Our model is based on a combination of the classical Bellare-Namprempre security model for authenticated encryption together with modifications from Boneh and Zhandry to handle message authentication against quantum adversaries. We give a generic construction based on Bellare-Namprempre for producing an authenticated encryption protocol from any quantum-resistant symmetric-key encryption scheme together with any digital signature scheme or MAC admitting any classical security reduction to a quantum-computationally hard problem. We apply the results and show how we can explicitly construct authenticated encryption schemes based on isogenies.

May 16, 20161 citation

Elliptic Curve Isogenies: A New Frontier for Post-Quantum Cryptography

PAULO SÉRGIO DE ANDRADE

The rise of quantum computing poses a significant threat to contemporary public-key cryptography, which relies on problems like integer factorization and the discrete logarithm, both of which are solvable in polynomial time by Shor's algorithm. This has prompted a global effort to develop and standardize post-quantum cryptographic primitives that are resistant to attacks by both classical and quantum computers. Among the various families of post-quantum candidates, isogeny-based cryptography has emerged as a particularly compelling, albeit challenging, alternative. This paper explores the mathematical foundations of elliptic curve isogenies and their application as a basis for quantum-resistant cryptographic protocols. We delve into the structure of supersingular elliptic curves and the associated isogeny graphs, which form the basis for the conjectured hardness of the underlying computational problems. The Supersingular Isogeny Diffie-Hellman (SIDH) protocol and its derivative, Supersingular Isogeny Key Encapsulation (SIKE), are examined in detail as principal examples of this cryptographic paradigm. We analyze their key advantages, most notably their exceptionally small key sizes, which offer significant benefits for constrained environments. However, the security landscape of isogeny-based cryptography has been dramatically reshaped by recent cryptanalytic breakthroughs that completely broke the SIKE protocol. This paper analyzes the nature of these attacks, discussing the vulnerabilities they exploited and the profound implications for the field. We conclude by surveying the current state of isogeny-based cryptography in the aftermath of these developments, outlining the proposed countermeasures, alternative designs, and the open research questions that define the new frontier for this promising area of post-quantum cryptography.

Nov 14, 20250 citations