Implicit Polynomial Recovery and Cryptanalysis of a Combinatorial Key Cryptosystem

详细信息    查看全文

• 作者：Jun Xu (12) jxu@is.ac.cn
  Lei Hu (1) hu@is.ac.cn
  Siwei Sun (1) swsun@is.ac.cn
• 关键词：Public Key Cryptography &#8211 ; Combinatorial Cryptosystem &#8211 ; Implicit Polynomial Recovery &#8211 ; Lattice &#8211 ; LLL Algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7618
• 期：1
• 页码：45-57
• 全文大小：195.3 KB
• 参考文献：1. Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 284–293 (1997)
  2. Bosma, W., Cannon, J., Playoust, C.: The Magma Algebra System I: The user language. Journal of Symbolic Computation 24, 235–265 (1997)
  3. Coppersmith, D.: Finding a Small Root of a Univariate Modular Equation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 155–165. Springer, Heidelberg (1996)
  4. Coppersmith, D., Franklin, M., Patarin, J., Reiter, M.: Low-Exponent RSA with Related Messages. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 1–9. Springer, Heidelberg (1996)
  5. Goldreich, O., Goldwasser, S., Halvei, S.: Public-Key Cryptosystems from Lattice Reduction Problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997)
  6. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A Ring-Based Public Key Cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
  7. Lenstra, A.K., Lenstra Jr., H.W., Lov谩sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515–534 (1982)
  8. Merkle, R.C., Hellman, M.E.: Hiding Information and Signatures in Trapdoor Knapsack. IEEE Transaction on Information Theory 24, 525–530 (1978)
  9. Nguyen, P.Q., Stern, J.: Cryptanalysis of the Ajtai-Dwork Cryptosystem. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 223–242. Springer, Heidelberg (1998)
  10. Odlyzko, A.M.: The rise and fall of knapsack cryptosystems. Cryptology and Computational Number Theory 42, 75–88 (1990)
  11. Shoup, V.: A library for doing number theory, http://www.shoup.net/ntl
  12. Wang, B., Hu, Y.: Diophantine Approximation Attack on a Fast Public Key Cryptosystem. In: Chen, K., Deng, R., Lai, X., Zhou, J. (eds.) ISPEC 2006. LNCS, vol. 3903, pp. 25–32. Springer, Heidelberg (2006)
  13. Wang, B., Hu, Y.: A Novel Combinatorial Public Key Cryptosystem. Informatica 21(4), 611–626 (2010)
  14. Zwillinger, D.(editor in chief): CRC Standard Mathematical Tables and Formulae, 30th edn. CRC Press, Boca Raton (1996)
• 作者单位：1. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093 China2. Graduate University of Chinese Academy of Sciences, Beijing, 100049 China
• ISSN：1611-3349

文摘

A public key cryptosystem based on factoring and a combinatorial problem of matrices over ℤ _N proposed in 2010 is analyzed in this paper. We propose an efficient partial private key recovery attack on it by solving a problem of recovering implicit polynomials with small coefficients given their large roots and deriving the large roots from the public key. From the partial information of private key, we can decrypt any ciphertext of the cryptosystem by a simple computation. Our implicit polynomial recovery is an application of lattice basis reduction.