Developed QFESTA, an Efficient Isogeny-Based Cryptography with Small Public Key and Ciphertext Size
Using a technique that breaks SIKE, the NIST standardization candidate

News Highlights:

TOKYO - September 5, 2024 - NTT Corporation (Headquarters: Chiyoda Ward, Tokyo; Representative Member of the Board and President: Akira Shimada; hereinafter "NTT") has constructed a new isogeny-based¹ cryptography, QFESTA, which is highly secure (IND-CCA²) against quantum computers and computationally efficient. Isogeny-based cryptography has been attracting attention because of the small public key and ciphertext data size compared to other candidates, and SIKE had been attracting particular attention. However, an attacking technique that breaks the security of SIKE was discovered in 2022, and alternatives to SIKE have been explored since but all of them have major issues with the computational cost of encryption and decryption. The proposed QFESTA is the most computationally efficient of the many proposed alternatives to SIKE. In the future, NTT will study the application of RandIsogImages, a component of QFESTA, to cryptographic protocols such as digital signatures.
　This achievement was presented at Crypto 2024³, the premier international cryptology conference held in August 2024.

1. Backgrounds

Quantum computers are based on the principles of quantum mechanics and are currently being developed around the world. In 1994, Shor's algorithm⁴ showed that RSA and elliptic curve cryptography, which are widely used today, can be broken by quantum computers. For this reason, research on post-quantum cryptography, which is unbreakable even with a quantum computer, has been actively conducted in recent years.
　There are several types of candidates for post-quantum cryptography, including lattice-based, code-based, and isogeny-based one, which are being studied simultaneously as a portfolio strategy. Among them, the isogeny-based cryptography has attracted attention because of its smaller public key and ciphertext data sizes compared to the other candidates (Figure 1 shows a comparison of data sizes of QFESTA and major post-quantum cryptographies.) An isogeny-based cryptography (key encapsulation mechanism⁵) named SIKE, has particularly attracted attention as it remained in Round 4 of the National Institute of Standards and Technology (NIST) standardization competition⁶. However, with the discovery of an attack⁷ to break the security of SIKE in 2022, this method is no longer secure. Since then, many alternatives have been proposed, but all of them have faced significant computational costs for encryption and decryption. To solve this problem, new isogeny-based cryptographies are being developed and the competition is intensifying.

2. Contributions

In the joint paper⁸ with the University of Tokyo, NTT constructed QFESTA, a new isogeny-based cryptography as an alternative to SIKE. Using an attack on SIKE, we have constructed a new algorithm RandIsogImages, which computes an isogeny of non-smooth degree⁹. By applying this algorithm, we constructed QFESTA, which is more than twice as fast as the conventional isogeny-based cryptography. We have also mathematically proved that QFESTA satisfies the security level specified by NIST¹⁰ under several assumptions.
　QFESTA has the highest computational efficiency among the many alternatives to SIKE. (Figure 2 shows a comparison of computation cost with a conventional method.) The proposed algorithm, RandIsogImages, is versatile in that there is almost no restriction on the degree and is expected to promote the development of isogeny-based cryptography in the future.
　These results were accepted to Crypto 2024, the premier international cryptology conference, and presented at the conference on August 21.

Note.
Secret key: The proposed method QFESTA is less than 1/5 compared to lattice encryption (Kyber). Less than 1/20 of code encryption (McEliece).
Public key: The proposed method QFESTA is less than 1/3 compared with lattice encryption (Kyber). Less than 1/800 of code encryption (McEliece).
Ciphertext: Compared with the proposed method QFESTA, the code encryption (McEliece) is smaller than 1/5, but the size of the private key and public key of the code encryption (McEliece) is much larger than that of the proposed method QFESTA.

Note. The higher the security level, the longer the computation time.
The ratio shown in the graph is decreasing because the conventional FESTA increases more than QFESTA.
*FESTA: Fast Encryption from Supersingular Torsion Attacks. Andrea Basso, Luciano Maino, and Giacomo Pope. (2023)

3. Outlook

In the future, we will study the application of RandIsogImages to other protocols such as digital signatures and contribute to the post-quantization of digital signatures.
　Through this research, we will further contribute to developing cryptographic protocols that provide secure and reliable communications in preparation for the advent of the quantum computer era.

[Glossary]

^1.Isogenies: A type of homomorphism between elliptic curves. Given two elliptic curves, it is considered hard to obtain an isogeny connecting them even with a quantum computer.

^2.IND-CCA: Indistinguishability against chosen-ciphertext attacks, the most secure against encryption method.

^3.Crypto 2024: https://crypto.iacr.org/2024/

^4.Shor's algorithm: An algorithm that can be implemented by quantum computers. Using this algorithm, mathematical problems such as prime factorization problems and discrete logarithm problems can be solved faster than ordinary computers. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Peter W. Shor. (1994)

^5.Key encapsulation mechanism: A type of cryptographies for key exchange.

^6.NIST Standardization Competition: https://csrc.nist.gov/projects/post-quantum-cryptography

^7.An efficient key recovery attack on SIDH. Wouter Castryck, Thomas Decru. (2022)

^8.QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras. Kohei Nakagawa (NTT Social Informatics Laboratories), Hiroshi Onuki (The University of Tokyo). (2024)

^9.Non-smooth degree: Isogenies have a concept called degree. When the degree is "smooth," meaning it consists only of small prime factors, the isogeny can be efficiently computed by conventional methods. However, it has been hard to efficiently compute isogenies of non-smooth degrees.

^10.Security level specified by NIST: There are five security levels (1-5), the higher the number, the higher the security. For example, a level of 1 means that the cost of attacks on encryption is similar to the cost of attacks on the common key encryption AES-128, and a level of 5 means that the cost of attacks is similar to the common key encryption AES-256.

About NTT

NTT contributes to a sustainable society through the power of innovation. We are a leading global technology company providing services to consumers and businesses as a mobile operator, infrastructure, networks, applications, and consulting provider. Our offerings include digital business consulting, managed application services, workplace and cloud solutions, data center and edge computing, all supported by our deep global industry expertise. We are over $97B in revenue and 330,000 employees, with $3.6B in annual R&D investments. Our operations span across 80+ countries and regions, allowing us to serve clients in over 190 of them. We serve over 75% of Fortune Global 100 companies, thousands of other enterprise and government clients and millions of consumers.