Revisiting orthogonal lattice attacks on approximate common divisor problems

DOI10.1016/J.TCS.2022.02.005OpenAlexW4213307161MaRDI QIDQ2118873

Jun Xu, Lei Hu, Santanu Sarkar

Publication date: 23 March 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.02.005

zbMATH Keywords

latticelattice reduction algorithmorthogonal lattice attackapproximate common divisor problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• BKZ
• fhe

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the concrete hardness of learning with errors
• The LLL algorithm. Survey and applications
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Revisiting the expected cost of solving uSVP and applications to LWE
• Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator
• Practical Multilinear Maps over the Integers
• Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers
• Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers
• Fully Homomophic Encryption over the Integers Revisited
• Approximate common divisors via lattices
• Algorithms for the approximate common divisor problem
• BKZ 2.0: Better Lattice Security Estimates
• LLL reducing with the most significant bits
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• New Multilinear Maps Over the Integers
• Implicit Factoring with Shared Most Significant and Middle Bits
• Fully Homomorphic Encryption over the Integers
• Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• New directions in nearest neighbor searching with applications to lattice sieving
• Batch Fully Homomorphic Encryption over the Integers
• Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
• Fully Homomorphic Encryption over the Integers with Shorter Public Keys
• Approximate Integer Common Divisor Problem Relates to Implicit Factorization
• Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors
• Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences
• Scale-Invariant Fully Homomorphic Encryption over the Integers
• An LLL-reduction algorithm with quasi-linear time complexity
• Predicting Lattice Reduction
• FHE over the Integers: Decomposed and Batched in the Post-Quantum Regime
• On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL

This page was built for publication: Revisiting orthogonal lattice attacks on approximate common divisor problems