Cryptanalysis of Multi-Prime \(\varPhi \) -Hiding Assumption

详细信息    查看全文

• 关键词：Multi ; Prime \(\varPhi \) ; Hiding Assumption ; Multi ; Prime \(\varPhi \) ; Hiding Problem ; Lattice ; LLL algorithm ; Coppersmith’s technique ; Gauss algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9866
• 期：1
• 页码：440-453
• 全文大小：422 KB
• 参考文献：1.Cachin, C., Micali, S., Stadler, M.A.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 402. Springer, Heidelberg (1999)CrossRef
  2.Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997)MathSciNet CrossRef MATH
  3.Gentry, C., Mackenzie, P., Ramzan, Z.: Password authenticated key exchange using hidden smooth subgroups. In: Proceedings of the 12th ACM Conference on Computer and Communications Security CCS 2005, pp. 299–309. ACM, New York (2005)
  4.Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005)CrossRef
  5.Gomez, D., Gutierrez, J., Ibeas, A.: Attacking the pollard generator. IEEE Trans. Inf. Theor. 52(12), 5518–5523 (2006)MathSciNet CrossRef MATH
  6.Hemenway, B., Ostrovsky, R.: Public-key locally-decodable codes. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 126–143. Springer, Heidelberg (2008)CrossRef
  7.Herrmann, M.: Improved cryptanalysis of the Multi-Prime \(\phi \) - Hiding Assumption. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 92–99. Springer, Heidelberg (2011)CrossRef
  8.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–424. Springer, Heidelberg (2008)CrossRef
  9.Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, p. 51. Springer, Heidelberg (2001)CrossRef
  10.Kakvi, S.A., Kiltz, E., May, A.: Certifying RSA. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 404–414. Springer, Heidelberg (2012)CrossRef
  11.Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)MathSciNet CrossRef MATH
  12.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–313. Springer, Heidelberg (2010)CrossRef
  13.Lenstra Jr., H.W.: Factoring integers with elliptic curves. Ann. Math. 126, 649–673 (1987)MathSciNet CrossRef MATH
  14.May, A.: Using LLL-reduction for solving RSA and factorization problems. In: Nguyen, P.Q., Valle, B. (eds.) The LLL Algorithm. Information Security and Cryptography, pp. 315–348. Springer, Heidelberg (2010)
  15.Sarkar, S.: Reduction in lossiness of RSA trapdoor permutation. In: Bogdanov, A., Sanadhya, S. (eds.) SPACE 2012. LNCS, vol. 7644, pp. 144–152. Springer, Heidelberg (2012)CrossRef
  16.Schridde, C., Freisleben, B.: On the validity of the \(\Phi \) -hiding assumption in cryptographic protocols. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 344–354. Springer, Heidelberg (2008)CrossRef
  17.Takayasu, A., Kunihiro, N.: Better lattice constructions for solving multivariate linear equations modulo unknown divisors. In: Boyd, C., Simpson, L. (eds.) ACISP. LNCS, vol. 7959, pp. 118–135. Springer, Heidelberg (2013)CrossRef
  18.Takayasu, A., Kunihiro, N.: Better lattice constructions for solving multivariate linear equations modulo unknown divisors. IEICE Trans. 97–A(6), 1259–1272 (2014)CrossRef MATH
  19.Tosu, K., Kunihiro, N.: Optimal bounds for multi-prime \(\Phi \) -hiding assumption. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 1–14. Springer, Heidelberg (2012)
  
• 作者单位：Jun Xu (15) (16)
  Lei Hu (15) (16)
  Santanu Sarkar (17)
  Xiaona Zhang (15) (16)
  Zhangjie Huang (15) (16)
  Liqiang Peng (15) (16)
  
  15. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093, China
  16. Data Assurance and Communications Security Research Center, Chinese Academy of Sciences, Beijing, 100093, China
  17. Indian Institute of Technology, Sardar Patel Road, Chennai, 600 036, India
  
• 丛书名：Information Security
• ISBN：978-3-319-45871-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9866

文摘

In Crypto 2010, Kiltz, O’Neill and Smith used m-prime RSA modulus N with \(m\ge 3\) for constructing lossy RSA. The security of the proposal is based on the Multi-Prime \(\varPhi \)-Hiding Assumption. In this paper, we propose a heuristic algorithm based on the Herrmann-May lattice method (Asiacrypt 2008) to solve the Multi-Prime \(\varPhi \)-Hiding Problem when prime \(e>N^{\frac{2}{3m}}\). Further, by combining with mixed lattice techniques, we give an improved heuristic algorithm to solve this problem when prime \(e>N^{\frac{2}{3m}-\frac{1}{4m^2}}\). These two results are verified by our experiments. Our bounds are better than the existing works.