On the optimality of lattices for the Coppersmith technique

DOI10.1007/s00200-017-0336-9zbMath1401.94136OpenAlexW2743602158MaRDI QIDQ1745898

Takakazu Satoh, Osamu Watanabe, Manindra Agrawal, Yoshinori Aono

Publication date: 18 April 2018

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.400.7163

zbMATH Keywords

impossibility resultlattice constructionCoppersmith techniqueRSA cryptanalyses

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60)

Related Items

Extended partial key exposure attacks on RSA: improvement up to full size decryption exponents ⋮ Partial key exposure attacks on RSA: achieving the Boneh-Durfee bound ⋮ Generalized cryptanalysis of small CRT-exponent RSA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Poisson distribution of lengths of lattice vectors in a random lattice
• The LLL algorithm. Survey and applications
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• OAEP reconsidered
• Square-free algorithms in positive characteristic
• Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
• Finding a Small Root of a Univariate Modular Equation
• On the Optimality of Lattices for the Coppersmith Technique
• Cryptographic Applications of Capacity Theory: On the Optimality of Coppersmith’s Method for Univariate Polynomials
• The Number of Lattice Points in a Set
• A New Lattice Construction for Partial Key Exposure Attack for RSA
• Solving Simultaneous Modular Equations of Low Degree
• A method for obtaining digital signatures and public-key cryptosystems
• Cryptanalysis of RSA with Private Key d Less than N 0.292
• On Optimal Bounds of Small Inverse Problems and Approximate GCD Problems with Higher Degree
• Minkowski Sum Based Lattice Construction for Multivariate Simultaneous Coppersmith’s Technique and Applications to RSA
• Partial Key Exposure Attacks on RSA up to Full Size Exponents
• Advances in Cryptology - CRYPTO 2003
• Predicting Lattice Reduction
• A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants
• Finding smooth integers in short intervals using CRT decoding
• On polynomial congruences

This page was built for publication: On the optimality of lattices for the Coppersmith technique