On the ideal shortest vector problem over random rational primes
From MaRDI portal
Publication:2056701
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
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
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