Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors
详细信息 查看全文
- 作者：Atsushi Takayasu (17)
Noboru Kunihiro (17) - 关键词：Lattices ; Coppersmith’s method ; small roots ; implicit factorization ; Multi ; Prime Φ ; Hiding Assumption ; Fault Attacks ; Digital Signatures ; RSA
- 刊名：Lecture Notes in Computer Science
- 出版年：2013
- 出版时间：2013
- 年：2013
- 卷：7959
- 期：1
- 页码：136-151
- 全文大小：292KB
- 参考文献：1. Bellare, M., Rogaway, P.: Probabilistic signature scheme. US Patent 6266771 (2001)
2. Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key / d less than / N 0.292. IEEE Trans. Inf. Theory 46(4), 1339-349 (2000); Firstly appeared In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.?1592, pp. 1-1. Springer, Heidelberg (1999) CrossRef
3. Chen, Y., Nguyen, P.Q.: Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.?7237, pp. 502-19. Springer, Heidelberg (2012) CrossRef
4. Cohn, H., Heninger, N.: Approximate common divisors via lattices. Report 2011/437 in the Cryptology ePrint Archive (2011), http://eprint.iacr.org/2011/437 (to appear at Proc. of ANTS-X)
5. Coppersmith, D.: Finding a Small Root of a univariate modular Equation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol.?1070, pp. 155-65. Springer, Heidelberg (1996) CrossRef
6. Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology?10(4), 233-60 (1997) CrossRef
7. Coron, J.-S., Joux, A., Kizhvatov, I., Naccache, D., Paillier, P.: Fault Attacks on RSA Signatures with partially unknown messages. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol.?5747, pp. 444-56. Springer, Heidelberg (2009) CrossRef
8. Coron, J.-S., Lepoint, T., Tibouchi, M.: Batch Fully Homomorphic Encryption over the Integers. Report 2013/036 in the Cryptology ePrint Archive (2013), http://eprint.iacr.org/2013/036
9. Coron, J.-S., Mandal, A., Naccache, D., Tibouchi, M.: Fully Homomorphic Encryption over the Integers with Shorter Public Keys. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.?6841, pp. 487-04. Springer, Heidelberg (2011) CrossRef
10. Coron, J.-S., Naccache, D., Tibouchi, M.: Fault Attacks Against emv Signatures. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol.?5985, pp. 208-20. Springer, Heidelberg (2010) CrossRef
11. Coron, J.-S., Naccache, D., Tibouchi, M.: Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.?7237, pp. 446-64. Springer, Heidelberg (2012) CrossRef
12. van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.?6110, pp. 24-3. Springer, Heidelberg (2010) CrossRef
13. Fouque, P.-A., Guillermin, N., Leresteux, D., Tibouchi, M., Zapalowicz, J.-C.: Attacking RSA-CRT Signatures with Faults on Montgomery Multiplication. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol.?7428, pp. 447-62. Springer, Heidelberg (2012) CrossRef
14. Herrmann, M.: Improved Cryptanalysis of the Multi-Prime Φ-Hiding Assumption. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol.?6737, pp. 92-9. Springer, Heidelberg (2011) CrossRef
15. Herrmann, M., May, A.: Solving Linear Equations modulo Divisors: On factoring given any bits. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol.?5350, pp. 406-24. Springer, Heidelberg (2008) CrossRef
16. Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Darnell, M. (ed.) Cryptography and Coding 1997. LNCS, vol.?1355, pp. 131-42. Springer, Heidelberg (1997)
17. Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol.?2146, pp. 51-6. Springer, Heidelberg (2001) CrossRef
18. Kiltz, E., O’Neill, A., Smith, A.: Instantiability of RSA-OAEP under Chosen-Plaintext Attack. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.?6223, pp. 295-13. Springer, Heidelberg (2010) CrossRef
19. Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen?261, 515-34 (1982) CrossRef
20. May, A.: New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis, University of Paderborn (2003)
21. May, A.: Using LLL-reduction for solving RSA and factorization problems: A survey (2007), http://www.cits.rub.de/permonen/may.html
22. May, A., Ritzenhofen, M.: Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol.?5443, pp. 1-4. Springer, Heidelberg (2009) CrossRef
23. Sarkar, S.: Reduction in Lossiness of RSA Trapdoor Permutation. In: Bogdanov, A., Sanadhya, S. (eds.) SPACE 2012. LNCS, vol.?7644, pp. 144-52. Springer, Heidelberg (2012) CrossRef
24. Sarkar, S., Maitra, S.: Approximate Integer Common Divisor Problem relates to Implicit Factorization. IEEE Trans. Inf. Theory?57(4), 4002-013 (2011) CrossRef
25. Tosu, K., Kunihiro, N.: Optimal Bounds for Multi-Prime Φ-Hiding Assumption. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol.?7372, pp. 1-4. Springer, Heidelberg (2012) CrossRef - 作者单位：Atsushi Takayasu (17)
Noboru Kunihiro (17)
17. The University of Tokyo, Japan - ISSN：1611-3349
文摘
At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham’s algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham’s problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham’s algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.