Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices

DOI10.1007/978-3-030-64834-3_12OpenAlexW3112426870MaRDI QIDQ2692387

Olivier Bernard, Adeline Roux-Langlois

Publication date: 21 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-64834-3_12

zbMATH Keywords

ideal latticesapprox-SVPPHS algorithm

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (4)

Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem ⋮ Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP ⋮ A short basis of the Stickelberger ideal of a cyclotomic field ⋮ On ideal class group computation of imaginary multiquadratic fields

Uses Software

• Magma
• SageMath
• BKZ
• NTRU
• fpLLL
• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The LLL algorithm. Survey and applications
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factorization of polynomials over finite fields
• Factoring polynomials with rational coefficients
• The Magma algebra system. I: The user language
• Sieving for closest lattice vectors (with preprocessing)
• 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
• Worst-case to average-case reductions for module lattices
• A Decade of Lattice Cryptography
• Subexponential class group and unit group computation in large degree number fields
• Mathematics of Public Key Cryptography
• Squarefree values of trinomial discriminants
• BKZ 2.0: Better Lattice Security Estimates
• On Ideal Lattices and Learning with Errors over Rings
• Efficient Public Key Encryption Based on Ideal Lattices
• Integral bases in algebraic number fields.
• 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
• Predicting Lattice Reduction
• Computing Generator in Cyclotomic Integer Rings
• Short Stickelberger Class Relations and Application to Ideal-SVP
• Recovering Short Generators of Principal Ideals in Cyclotomic Rings
• Algorithmic Number Theory
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices