Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors
作者： Atsushi Takayasu , Noboru Kunihiro
DOI: 10.1007/978-3-642-39059-3_9
关键词:
摘要: At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, so-called partially approximate common problem. So far, two forms multivariate generalizations problem have been considered in context cryptanalysis. The first is simultaneous modular equations, whose was at ANTS 2012 by Cohn and Heninger. second Asiacrypt 2008 Herrmann May. Both algorithms cover Howgrave-Graham’s cases. On other hand, both problems also become identical to asymptotic cases root bounds. However, former do not such In this paper, we introduce strategy natural constructions that take into account sizes We work out selection polynomials constructing lattices. Our are superior all attacks solve can generalize case arbitrary number variables. achieve better cryptanalytic bounds some applications relate RSA cryptosystems.
springer.com
sci-hub.st 参考文章(27)
Alexander May, Using LLL-Reduction for Solving RSA and Factorization Problems The LLL Algorithm. pp. 315- 348 ,(2009) , 10.1007/978-3-642-02295-1_10
Kaori Tosu, Noboru Kunihiro, Optimal bounds for multi-prime Φ-hiding assumption australasian conference on information security and privacy. pp. 1- 14 ,(2012) , 10.1007/978-3-642-31448-3_1
Alexander May, New RSA Vulnerabilities Using Lattice Reduction Methods pp. 1- 159 ,(2003)
Mathias Herrmann, Improved cryptanalysis of the multi-prime φ-hiding assumption international conference on progress in cryptology. pp. 92- 99 ,(2011) , 10.1007/978-3-642-21969-6_6
Jean-Sébastien Coron, Antoine Joux, Ilya Kizhvatov, David Naccache, Pascal Paillier, Fault Attacks on RSA Signatures with Partially Unknown Messages cryptographic hardware and embedded systems. pp. 444- 456 ,(2009) , 10.1007/978-3-642-04138-9_31
Mathias Herrmann, Alexander May, Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits international conference on the theory and application of cryptology and information security. pp. 406- 424 ,(2008) , 10.1007/978-3-540-89255-7_25
Jean-Sébastien Coron, Avradip Mandal, David Naccache, Mehdi Tibouchi, Fully homomorphic encryption over the integers with shorter public keys international cryptology conference. ,vol. 2011, pp. 487- 504 ,(2011) , 10.1007/978-3-642-22792-9_28
Yuanmi Chen, Phong Q. Nguyen, Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers Advances in Cryptology – EUROCRYPT 2012. ,vol. 7237, pp. 502- 519 ,(2012) , 10.1007/978-3-642-29011-4_30
Nicholas Howgrave-Graham, Finding Small Roots of Univariate Modular Equations Revisited Lecture Notes in Computer Science. pp. 131- 142 ,(1997) , 10.1007/BFB0024458
Dan Boneh, Glenn Durfee, Cryptanalysis of RSA with private key d less than N 0:292 theory and application of cryptographic techniques. pp. 1- 11 ,(1999) , 10.1007/3-540-48910-X_1