On the ideal shortest vector problem over random rational primes

DOI10.1007/978-3-030-77870-5_20zbMath1479.94241arXiv2004.10278OpenAlexW3158888163MaRDI QIDQ2056701

Qi Cheng, Yanbin Pan, Nick Wadleigh, Jun Xu

Publication date: 8 December 2021

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

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)

Related Items (4)

Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems ⋮ Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem ⋮ Subfield attacks on HSVP in ideal lattices ⋮ LWE from non-commutative group rings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Factorization of the cyclotomic polynomial \(x^{2^n}+1\) over finite fields
• NTRU prime: reducing attack surface at low cost
• On the shortness of vectors to be found by the ideal-SVP quantum algorithm
• Approx-SVP in ideal lattices with pre-processing
• Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
• A Subfield Lattice Attack on Overstretched NTRU Assumptions
• An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero
• Making NTRU as Secure as Worst-Case Problems over Ideal Lattices
• Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes
• On Ideal Lattices and Learning with Errors over Rings
• Generalized Compact Knapsacks Are Collision Resistant
• Efficient Public Key Encryption Based on Ideal Lattices
• Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
• Pseudorandomness of ring-LWE for any ring and modulus
• A quantum algorithm for computing the unit group of an arbitrary degree number field
• Revisiting Lattice Attacks on Overstretched NTRU Parameters
• Computing Generator in Cyclotomic Integer Rings
• Short Stickelberger Class Relations and Application to Ideal-SVP
• Recovering Short Generators of Principal Ideals in Cyclotomic Rings
• Theory of Cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Number fields

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