On the ideal shortest vector problem over random rational primes

DOI10.1007/978-3-030-77870-5_20zbMATH Open1479.94241arXiv2004.10278OpenAlexW3158888163MaRDI QIDQ2056701FDOQ2056701

Authors: Yanbin Pan, Jun Xu, Nick Wadleigh, Qi Cheng 

Publication date: 8 December 2021

Abstract: Any ideal in a number field can be factored into a product of prime ideals. In this paper we study the prime ideal shortest vector problem (SVP) in the ring $$, a popular choice in the design of ideal lattice based cryptosystems. We show that a majority of rational primes lie under prime ideals admitting a polynomial time algorithm for SVP. Although the shortest vector problem of ideal lattices underpins the security of Ring-LWE cryptosystem, this work does not break Ring-LWE, since the security reduction is from the worst case ideal SVP to the average case Ring-LWE, and it is one-way.

Full work available at URL: https://arxiv.org/abs/2004.10278

Recommendations

• Short Stickelberger class relations and application to Ideal-SVP
• Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time
• Sieving for shortest vectors in ideal lattices
• Random self-reducibility of ideal-SVP via Arakelov random walks
• Approx-SVP in ideal lattices with pre-processing

zbMATH Keywords

ideal latticering-LWEaverage case computational complexitylattice-based cryptosystems

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Title not available (Why is that?)
• Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
• On ideal lattices and learning with errors over rings
• Factorization of the cyclotomic polynomial \(x^{2^n}+1\) over finite fields
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Efficient public key encryption based on ideal lattices (extended abstract)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fully homomorphic encryption with relatively small key and ciphertext sizes
• On lattices, learning with errors, random linear codes, and cryptography
• Title not available (Why is that?)
• Making NTRU as secure as worst-case problems over ideal lattices
• Generalized Compact Knapsacks Are Collision Resistant
• Theory of Cryptography
• Number fields
• Approx-SVP in ideal lattices with pre-processing
• A Subfield Lattice Attack on Overstretched NTRU Assumptions
• Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
• A quantum algorithm for computing the unit group of an arbitrary degree number field
• An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero
• Pseudorandomness of ring-LWE for any ring and modulus
• Recovering short generators of principal ideals in cyclotomic rings
• NTRU prime: reducing attack surface at low cost
• Short Stickelberger class relations and application to Ideal-SVP
• Revisiting Lattice Attacks on Overstretched NTRU Parameters
• Computing generator in cyclotomic integer rings. A subfield algorithm for the principal ideal problem in \(L_{|\varDelta_\mathbb {K}|}\left(\frac{1}{2}\right)\) and application to the cryptanalysis of a FHE scheme
• On the shortness of vectors to be found by the ideal-SVP quantum algorithm

Cited In (14)

• RLWE/PLWE equivalence for the maximal totally real subextension of the \(2^rpq\)-th cyclotomic field
• Subfield attacks on HSVP in ideal lattices
• Ideal-SVP is hard for small-norm uniform prime ideals
• Short principal ideal problem in multicubic fields
• Security analysis of cryptosystems using short generators over ideal lattices
• Short Stickelberger class relations and application to Ideal-SVP
• Application of automorphic forms to lattice problems
• Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems
• Subfield algorithms for ideal- and module-SVP based on the decomposition group
• On algebraic embedding for unstructured lattices
• LWE from non-commutative group rings
• Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem
• The linear transformation that relates the canonical and coefficient embeddings of ideals in cyclotomic integer rings
• Random self-reducibility of ideal-SVP via Arakelov random walks

This page was built for publication: On the ideal shortest vector problem over random rational primes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056701)