On the ideal shortest vector problem over random rational primes
From MaRDI portal
(Redirected from Publication:2056701)
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.
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
Cites work
- scientific article; zbMATH DE number 3980484 (Why is no real title available?)
- scientific article; zbMATH DE number 1186948 (Why is no real title available?)
- scientific article; zbMATH DE number 1256724 (Why is no real title available?)
- scientific article; zbMATH DE number 1313469 (Why is no real title available?)
- scientific article; zbMATH DE number 2120513 (Why is no real title available?)
- A Subfield Lattice Attack on Overstretched NTRU Assumptions
- 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
- Approx-SVP in ideal lattices with pre-processing
- 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
- Efficient public key encryption based on ideal lattices (extended abstract)
- Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
- Factoring polynomials with rational coefficients
- Factorization of the cyclotomic polynomial \(x^{2^n}+1\) over finite fields
- Fully homomorphic encryption with relatively small key and ciphertext sizes
- Generalized Compact Knapsacks Are Collision Resistant
- Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Making NTRU as secure as worst-case problems over ideal lattices
- NTRU prime: reducing attack surface at low cost
- Number fields
- On ideal lattices and learning with errors over rings
- On lattices, learning with errors, random linear codes, and cryptography
- On the shortness of vectors to be found by the ideal-SVP quantum algorithm
- Pseudorandomness of ring-LWE for any ring and modulus
- Recovering short generators of principal ideals in cyclotomic rings
- Revisiting Lattice Attacks on Overstretched NTRU Parameters
- Short Stickelberger class relations and application to Ideal-SVP
- Theory of Cryptography
Cited in
(14)- Random self-reducibility of ideal-SVP via Arakelov random walks
- Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems
- Short Stickelberger class relations and application to Ideal-SVP
- RLWE/PLWE equivalence for the maximal totally real subextension of the \(2^rpq\)-th cyclotomic field
- Application of automorphic forms to lattice problems
- Short principal ideal problem in multicubic fields
- Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem
- Security analysis of cryptosystems using short generators over ideal lattices
- Subfield algorithms for ideal- and module-SVP based on the decomposition group
- On algebraic embedding for unstructured lattices
- Subfield attacks on HSVP in ideal lattices
- LWE from non-commutative group rings
- The linear transformation that relates the canonical and coefficient embeddings of ideals in cyclotomic integer rings
- Ideal-SVP is hard for small-norm uniform prime ideals
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)
