Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Mathematical Cryptology

On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in ℚ(𝜁 2 𝑠 )

Jean‐François Biasse, Fang Song

Published Aug 14, 2019• 1 citation
Publisher

Abstract

Abstract A family of ring-based cryptosystems, including the multilinear maps of Garg, Gentry and Halevi [Candidate multilinear maps from ideal lattices, Advances in Cryptology—EUROCRYPT 2013, Lecture Notes in Comput. Sci. 7881, Springer, Heidelberg 2013, 1–17] and the fully homomorphic encryption scheme of Smart and Vercauteren [Fully homomorphic encryption with relatively small key and ciphertext sizes, Public Key Cryptography—PKC 2010, Lecture Notes in Comput. Sci. 6056, Springer, Berlin 2010, 420–443], are based on the hardness of finding a short generator of a principal ideal (short-PIP) in a number field typically in ℚ ⁢ ( ζ 2 s ) {\mathbb{Q}(\zeta_{2^{s}})} . In this paper, we present a polynomial-time quantum algorithm for recovering a generator of a principal ideal in ℚ ⁢ ( ζ 2 s ) {\mathbb{Q}(\zeta_{2^{s}})} , and we recall how this can be used to attack the schemes relying on the short-PIP in ℚ ⁢ ( ζ 2 s ) {\mathbb{Q}(\zeta_{2^{s}})} by using the work of Cramer et al. [R. Cramer, L. Ducas, C. Peikert and O. Regev, Recovering short generators of principal ideals in cyclotomic rings, IACR Cryptology ePrint Archive 2015, https://eprint.iacr.org/2015/313 ], which is derived from observations of Campbell, Groves and Shepherd [SOLILOQUY, a cautionary tale]. We put this attack into perspective by reviewing earlier attempts at providing an efficient quantum algorithm for solving the PIP in ℚ ⁢ ( ζ 2 s ) {\mathbb{Q}(\zeta_{2^{s}})} . The assumption that short-PIP is hard was challenged by Campbell, Groves and Shepherd. They proposed an approach for solving short-PIP that proceeds in two steps: first they sketched a quantum algorithm for finding an arbitrary generator (not necessarily short) of the input principal ideal. Then they suggested that it is feasible to compute a short generator efficiently from the generator in step 1. Cramer et al. validated step 2 of the approach by giving a detailed analysis. In this paper, we focus on step 1, and we show that step 1 can run in quantum polynomial time if we use an algorithm for the continuous hidden subgroup problem (HSP) due to Eisenträger et al. [K. Eisenträger, S. Hallgren, A. Kitaev and F. Song, A quantum algorithm for computing the unit group of an arbitrary degree number field, Proceedings of the 2014 ACM Symposium on Theory of Computing—STOC’14, ACM, New York 2014, 293–302].

DOI
10.1515/jmc-2015-0046

Related papers

On the analysis of quantum algorithms for solving the short principal ideal problem

Iu-Iong Ng

In this thesis, we analyse and improve the best known ecient quantum algorithm for solving the Short Principal Ideal Problem (SPIP) in cyclotomic elds, which, given an ideal, determines whether the ideal is principal and outputs a suciently short generator.SPIP is fundamental in cryptography and computational number theory.The standard solution to SPIP can unfold in a two-part process involving the Principal Ideal Problem (PIP) and the Short Generator Problem (SGP).This thesis consists of the following two results.For PIP, we calculate the upper bound on quantum space complexity of the quantum algorithm proposed by Biasse and Song at SODA 2016 (BS) for solving PIP.PIP is the problem that, given an ideal, determines whether the ideal is principal and outputs a generator of the ideal if it is principal.The best known classical algorithm solves PIP in subexponential time, while the BS quantum algorithm nds a generator in polynomial time.Whether the cryptographic systems relying on the hardness of PIP have become insecure depends not only on the existence of polynomial time algorithms solving it but also on whether the algorithms should be implementable.Quantum computers nowadays have only hundreds of qubits, which means that quantum algorithms using too many qubits are not feasible for now.By estimating the qubits used in the BS algorithm, we want to estimate the threat at the moment.

•Mar 25, 2025•0 citations

Usability of structured lattices for a post-quantum cryptography: practical computations, and a study of some real Kummer extensions

Andrea Lesavourey

Lattice-based cryptography is an excellent candidate for post-quantum cryptography, i.e. cryptosystems which are resistant to attacks run on quantum computers. For efficiency reason, most of the constructions explored nowadays are based on structured lattices, such as module lattices or ideal lattices. The security of most constructions can be related to the hardness of retrieving a short element in such lattices, and one does not know yet to what extent these additional structures weaken the cryptosystems. A related problem – which is an extension of a classical problem in computational number theory – called the Short Principal Ideal Problem (or SPIP), consists of finding a short generator of a principal ideal. Its assumed hardness has been used to build some cryptographic schemes. However it has been shown to be solvable in quantum polynomial time over cyclotomic fields, through an attack which uses the Log-unit lattice of the field considered. Later, practical results showed that multiquadratic fields were also weak to this strategy.\nThe main general question that we study in this thesis is To what extent can structured lattices be used to build a post-quantum cryptography?

•Jan 1, 2021•0 citations

Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Ming-Xing Luo

We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies $γ\le 21 < q/2=1664.5$ for ML-KEM-1024, with a success probability $\ge 0.99$. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain $\Q\subset \Q(ζ_8)\subset\cdots\subset \Q(ζ_{2^k})$ which yields a polynomial-time quantum algorithm costing $O(n^3 \log^2 n)$ gates, $O(n^2 \log n)$ qubits, and poly$(n)$ classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms.

quant-pharXiv:2605.17412•May 19, 2026•0 citations

An efficient quantum algorithm for computing $S$-units and its applications

Jean‐François Biasse, Song, Fang

In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the $S$-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, S-class groups, relative class group and the unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.

arXiv:2510.02280•Oct 2, 2025•0 citations

Creating a Challenge for Ideal Lattices.

Thomas Plantard, Michael Schneider

Abstract. Lattice-based cryptography is one of the candidates in the area of post-quantum cryptography. Cryptographic schemes with security reductions to hard lattice problems (like the Shortest Vector Problem SVP) offer an alternative to recent number theory-based schemes. In order to guarantee asymptotic efficiency, most lattice-based schemes are instantiated using polynomial rings over integers. These lattices are called ideal lattices. It is assumed that the hardness of lattice problems in lattices over integer rings remains the same as in regular lattices. In order to prove or disprove this assumption, we instantiate random ideal lattices that allow to test algorithms that solve SVP and its approximate version. The Ideal Lattice Challenge allows online submission of short vectors to enter a hall of fame for full comparison. We adjoin a set of first experiments and a first comparison of ideal and regular lattices.

•Jan 1, 2013•14 citations

A Provably Secure Variant of ETRU Based on Extended Ideal Lattices Over Direct Product of Dedekind Domains

Reza Ebrahimi Atani, Shahabaddin Ebrahimi Atani, Amir Hassani Karbasi

Jarvis and Nevins presented ETRU in 2013 which has applausive performance with moderate key-sizes and conjectured resistance to quantum computers. ETRU, as an efficient NTRUEncrypt-like cryptosystem, is over the ring of Eisenstein integers that is faster with smaller keys for the same or better level of security than does NTRUEncrypt which is a desirable alternative to public-key cryptosystems based on factorisation and discrete logarithm problem. However, because of its construction, doubts have regularly arisen on its security. In this paper, we propose how to modify ETRU to make it provably secure, under our modified assumption of quantum hardness of standard worst-case lattice problems, restricted to extended ideal lattices related to some extensions of cyclotomic fields structures. We describe the structure of all generated polynomial rings of quotient over direct product of Dedekind domains Z and Z[ζ3], where ζ3 is complex cube root of unity. We give a detailed description to show that if the private key polynomials of the ETRU are selected from direct product of some Dedekind domains using discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its range. The security then proves for our main system from the already proven hardness of the R-SIS and R-LWE problems by their extensions.

•Dec 1, 2018•4 citations
Abstract A family of ring-based cryptosystems, including the multilinear maps of Garg, Gentry and Halevi [Candidate multilinear maps from ideal lattices, Advances in Cryptology—EUROCRYPT 2013, Lecture Notes in Comput. Sci. 7881, Springer, Heidelberg 2013, 1–17] and the fully homomorphic encryption scheme of Smart and Vercauteren [Fully homomorphic encryption with relatively small key and ciphertext sizes, Public Key Cryptography—PKC 2010, Lecture Notes in Comput. Sci. 6056, Springer, Berlin 2010, 420–443], are based on the hardness of finding a short generator of a principal ideal (short-PIP) in a number field typically in ℚ ⁢ ( ζ 2 s ) {\mathbb{Q}(\zeta_{2^{s}})} . In this paper, we present a polynomial-time quantum algorithm for recovering a generator of a principal ideal in ℚ ⁢ ( ζ 2 s ) {\mathbb{Q}(\zeta_{2^{s}})} , and we recall how this can be used to attack the schemes relying on the short-PIP in ℚ ⁢ ( ζ 2 s ) {\mathbb{Q}(\zeta_{2^{s}})} by using the work of Cramer et al. [R. Cramer, L. Ducas, C. Peikert and O. Regev, Recovering short generators of principal ideals in cyclotomic rings, IACR Cryptology ePrint Archive 2015, https://eprint.iacr.org/2015/313 ], which is derived from observations of Campbell, Groves and Shepherd [SOLILOQUY, a cautionary tale]. We put this attack into perspective by reviewing earlier attempts at providing an efficient quantum algorithm for solving the PIP in ℚ ⁢ ( ζ 2 s ) {\mathbb{Q}(\zeta_{2^{s}})} . The assumption that short-PIP is hard was challenged by Campbell, Groves and Shepherd. They proposed an approach for solving short-PIP that proceeds in two steps: first they sketched a quantum algorithm for finding an arbitrary generator (not necessarily short) of the input principal ideal. Then they suggested that it is feasible to compute a short generator efficiently from the generator in step 1. Cramer et al. validated step 2 of the approach by giving a detailed analysis. In this paper, we focus on step 1, and we show that step 1 can run in quantum polynomial time if we use an algorithm for the continuous hidden subgroup problem (HSP) due to Eisenträger et al. [K. Eisenträger, S. Hallgren, A. Kitaev and F. Song, A quantum algorithm for computing the unit group of an arbitrary degree number field, Proceedings of the 2014 ACM Symposium on Theory of Computing—STOC’14, ACM, New York 2014, 293–302].
In this thesis, we analyse and improve the best known ecient quantum algorithm for solving the Short Principal Ideal Problem (SPIP) in cyclotomic elds, which, given an ideal, determines whether the ideal is principal and outputs a suciently short generator.SPIP is fundamental in cryptography and computational number theory.The standard solution to SPIP can unfold in a two-part process involving the Principal Ideal Problem (PIP) and the Short Generator Problem (SGP).This thesis consists of the following two results.For PIP, we calculate the upper bound on quantum space complexity of the quantum algorithm proposed by Biasse and Song at SODA 2016 (BS) for solving PIP.PIP is the problem that, given an ideal, determines whether the ideal is principal and outputs a generator of the ideal if it is principal.The best known classical algorithm solves PIP in subexponential time, while the BS quantum algorithm nds a generator in polynomial time.Whether the cryptographic systems relying on the hardness of PIP have become insecure depends not only on the existence of polynomial time algorithms solving it but also on whether the algorithms should be implementable.Quantum computers nowadays have only hundreds of qubits, which means that quantum algorithms using too many qubits are not feasible for now.By estimating the qubits used in the BS algorithm, we want to estimate the threat at the moment.
Lattice-based cryptography is an excellent candidate for post-quantum cryptography, i.e. cryptosystems which are resistant to attacks run on quantum computers. For efficiency reason, most of the constructions explored nowadays are based on structured lattices, such as module lattices or ideal lattices. The security of most constructions can be related to the hardness of retrieving a short element in such lattices, and one does not know yet to what extent these additional structures weaken the cryptosystems. A related problem – which is an extension of a classical problem in computational number theory – called the Short Principal Ideal Problem (or SPIP), consists of finding a short generator of a principal ideal. Its assumed hardness has been used to build some cryptographic schemes. However it has been shown to be solvable in quantum polynomial time over cyclotomic fields, through an attack which uses the Log-unit lattice of the field considered. Later, practical results showed that multiquadratic fields were also weak to this strategy.\nThe main general question that we study in this thesis is To what extent can structured lattices be used to build a post-quantum cryptography?
We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies γ≤21<q/2=1664.5γ\le 21 < q/2=1664.5γ≤21<q/2=1664.5 for ML-KEM-1024, with a success probability ≥0.99\ge 0.99≥0.99. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain $\Q\subset \Q(ζ_8)\subset\cdots\subset \Q(ζ_{2^k})$ which yields a polynomial-time quantum algorithm costing O(n3log⁡2n)O(n^3 \log^2 n)O(n3log2n) gates, O(n2log⁡n)O(n^2 \log n)O(n2logn) qubits, and poly(n)(n)(n) classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms.
An efficient quantum algorithm for computing SSS-units and its applications
In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the SSS-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, S-class groups, relative class group and the unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.
Abstract. Lattice-based cryptography is one of the candidates in the area of post-quantum cryptography. Cryptographic schemes with security reductions to hard lattice problems (like the Shortest Vector Problem SVP) offer an alternative to recent number theory-based schemes. In order to guarantee asymptotic efficiency, most lattice-based schemes are instantiated using polynomial rings over integers. These lattices are called ideal lattices. It is assumed that the hardness of lattice problems in lattices over integer rings remains the same as in regular lattices. In order to prove or disprove this assumption, we instantiate random ideal lattices that allow to test algorithms that solve SVP and its approximate version. The Ideal Lattice Challenge allows online submission of short vectors to enter a hall of fame for full comparison. We adjoin a set of first experiments and a first comparison of ideal and regular lattices.
Jarvis and Nevins presented ETRU in 2013 which has applausive performance with moderate key-sizes and conjectured resistance to quantum computers. ETRU, as an efficient NTRUEncrypt-like cryptosystem, is over the ring of Eisenstein integers that is faster with smaller keys for the same or better level of security than does NTRUEncrypt which is a desirable alternative to public-key cryptosystems based on factorisation and discrete logarithm problem. However, because of its construction, doubts have regularly arisen on its security. In this paper, we propose how to modify ETRU to make it provably secure, under our modified assumption of quantum hardness of standard worst-case lattice problems, restricted to extended ideal lattices related to some extensions of cyclotomic fields structures. We describe the structure of all generated polynomial rings of quotient over direct product of Dedekind domains Z and Z[ζ3], where ζ3 is complex cube root of unity. We give a detailed description to show that if the private key polynomials of the ETRU are selected from direct product of some Dedekind domains using discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its range. The security then proves for our main system from the already proven hardness of the R-SIS and R-LWE problems by their extensions.