Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden.
powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden.
powered by
Abstract
The worst-case hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) is a central matter in lattice based cryptography. Assuming the worst-case hardness of Ideal-SVP allows to prove the Ring-LWE and Ring-SIS assumptions, and therefore to prove the security of numerous cryptographic schemes and protocols — including key-exchange, digital signatures, public-key encryption and fully-homomorphic encryption.
A series of recent works has shown that Principal Ideal-SVP is not always as hard as finding short vectors in general lattices, and some schemes were broken using quantum algorithms — the Soliloquy encryption scheme, Smart-Vercauteren fully homomorphic encryption scheme from PKC 2010, and Gentry-Garg-Halevi cryptographic multilinear-maps from Eurocrypt 2013.
Those broken schemes were using a special class of principal ideals, but these works also showed how to solve SVP for principal ideals in the worst-case in quantum polynomial time for an approximation factor of \(\exp (\tilde{O}(\sqrt{n}))\). This exposed an unexpected hardness gap between general lattices and some structured ones, and called into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE.
In this work, we generalize the previous result to general ideals. Precisely, we show how to solve the close principal multiple problem (CPM) by exploiting the classical theorem that the class-group is annihilated by the (Galois-module action of) the so-called Stickelberger ideal. Under some plausible number-theoretical hypothesis, our approach provides a close principal multiple in quantum polynomial time. Combined with the previous results, this solves Ideal-SVP in the worst case in quantum polynomial time for an approximation factor of \(\exp (\tilde{O}(\sqrt{n}))\).
Although it does not seem that the security of Ring-LWE based cryptosystems is directly affected, we contribute novel ideas to the cryptanalysis of schemes based on structured lattices. Moreover, our result shows a deepening of the gap between general lattices and structured ones.
Anzeige
Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.
The earlier result of [JMV09, Corrolary 1.3] is not sufficient as it does not keep track of the dependence on the degree of the number fields, left hidden in the constants.
One notes that this solution is not integral as desired, yet getting rid of negative exponents will be easy, at least in the relative class group \(\mathrm {Cl}^-_K\).
Note that, as a computational problem, this task is non-uniform. That is, it must be ran once for each conductor m of interest, but does not need to be re-run for each CPM instance in \(\mathcal O_K\). A proof of existence of such a factor basis would already have a consequence in a complexity theoretic perspective. We however heuristically argue in Sect. 2.3 that a good basis can actually be found efficiently.
In fact, Proposition 2 is a corollary of [BS16, Theorem 1.1]. Even though it is not stated explicitly in that paper, it must be attributed to that paper nevertheless. Indeed, the implication is straightforward and its authors have already sketched it in public talks. Our purpose here is merely to include technical details for completeness.