Revisiting orthogonal lattice attacks on approximate common divisor problems

DOI10.1016/J.TCS.2022.02.005MaRDI QIDQ2118873zbMATH OpenOpenAlexFDO

Authors Jun Xu, Santanu Sarkar, Lei Hu

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)

Recommendations

• Algorithms for the approximate common divisor problem
• Approximate common divisor problem and lattice sieving
• scientific article; zbMATH DE number 1852136
• Approximate common divisors via lattices
• Approximate common divisor problem and continued fractions

Cites work

• scientific article; zbMATH DE number 1676629 (Why is no real title available?)
• scientific article; zbMATH DE number 1088235 (Why is no real title available?)
• scientific article; zbMATH DE number 1962809 (Why is no real title available?)
• scientific article; zbMATH DE number 1852136 (Why is no real title available?)
• Algorithms for the approximate common divisor problem
• An LLL-reduction algorithm with quasi-linear time complexity, extended abstract
• Analyzing blockwise lattice algorithms using dynamical systems
• Approximate Integer Common Divisor Problem Relates to Implicit Factorization
• Approximate common divisors via lattices
• BKZ 2.0: Better lattice security estimates
• Batch fully homomorphic encryption over the integers
• Better lattice constructions for solving multivariate linear equations modulo unknown divisors
• FHE over the Integers: Decomposed and Batched in the Post-Quantum Regime
• Factoring polynomials with rational coefficients
• Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers
• Fully homomophic encryption over the integers revisited
• Fully homomorphic encryption over the integers
• Fully homomorphic encryption over the integers with shorter public keys
• Implicit Factoring with Shared Most Significant and Middle Bits
• Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint
• Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator
• LLL reducing with the most significant bits
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• New Multilinear Maps Over the Integers
• New directions in nearest neighbor searching with applications to lattice sieving
• On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL
• On the concrete hardness of learning with errors
• Practical multilinear maps over the integers
• Predicting Lattice Reduction
• Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers
• Revisiting the expected cost of solving uSVP and applications to LWE
• Rounding and chaining LLL: finding faster small roots of univariate polynomial congruences
• Scale-invariant fully homomorphic encryption over the integers
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• The LLL algorithm. Survey and applications

Cited in

(1)

• Revisiting Lattice Attacks on Overstretched NTRU Parameters

Describes a project that uses

Uses Software

• fhe
• BKZ

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118873)