Cryptanalysis of the Double-Moduli Cryptosystem

Abstract

In this article we present a lattice attack done on a NTRU-like scheme introduced by Verkhovsky in [1]. We show how, based on the relation between the public and private key, we can construct an attack which allows any passive adversary to decrypt the encrypted messages. We explain, step by step, how an attacker can construct an equivalent private key and guess what the original plaintext was. Our attack is efficient and provides good experimental results.

Share and Cite:

S. Mihaela Bogos and S. Vaudenay, "Cryptanalysis of the Double-Moduli Cryptosystem," International Journal of Communications, Network and System Sciences, Vol. 5 No. 12, 2012, pp. 834-838. doi: 10.4236/ijcns.2012.512088.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] B. S. Verkhovsky, “Double-Moduli Gaussian Encryption/Decryption with Primary Residues and Secret Controls,” IJCNS, Vol. 4, No. 7, 2011, pp. 475-481. doi:10.4236/ijcns.2011.47058
[2] D. Coppersmith and A. Shamir, “Lattice Attacks on NTRU,” Advances in Cryptology—EUROCRYPT ’97, International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, 11-15 May 1997, pp. 52-61.
[3] A. May, “Cryptanalysis of NTRU,” 1999. http://www-stud.rbi.informatik.uni-frankfurt.de/~alex/ntru.ps
[4] J. Hoffstein, J. Pipher and J.H. Silverman, “NTRU: A Ring-Based Public Key Cryptosystem,” Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, 21-25 June 1998, pp. 267-288.
[5] A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, “Factoring Polynomials with Rational Coefficients,” Mathematische Annalen, Vol. 261, No. 4, 1982, pp. 515-534. doi:10.1007/BF01457454
[6] D. Stehle and R. Steinfeld, “Making NTRU as Secure as Worst-Case Problems over Ideal Lattices,” Advances in Cryptology—EUROCRYPT 2011—30th Annual International Conference on the Theory and applications of Cryptographic Techniques, Tallinn, 15-19 May 2011, pp. 27-47.
[7] J. Hastad, “On Using RSA with Low Exponent in a Public Key Network,” Advances in Cryptology—CRYPTO ’85, Santa Barbara, 18-22 August 1985, pp. 403-408.
[8] J. C. Lagarias and A. M. Odlyzko, “Solving Low-Density Subset Sum Problems,” Journal of the ACM, Vol. 32, No. 1, 1985, pp. 229-246. doi:10.1145/2455.2461
[9] C. Gentry, J. Jonsson, J. Stern and M. Szydlo, “CryptANALYSIS of the NTRU Signature Scheme (NSS) from Eurocrypt 2001,” Advances in Cryptology—ASIACRYPT’01, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, 9-13 December 2001, pp. 1-20.
[10] P. Q. Nguyen and D. Stehlé, “An LLL Algorithm with Quadratic Complexity,” SIAM Journal on Computing, Vol. 39, No. 3, 2009, pp. 874-903. doi:10.1137/070705702
[11] C.-P. Schnorr, “A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms,” Theoretical Computer Science Journal, Vol. 53, 1987, pp. 201-224. doi:10.1016/0304-3975(87)90064-8
[12] P. Q. Nguyen and J. Stern, “Merkle-Hellman Revisited: A Cryptanalysis of the Qu-Vanstone Cryptosystem Based on Group Factorizations,” Advances in Cryptology—CRYPTO’97, 17th Annual International Cryptology Conference, Santa Barbara, 17-21 August 1997, pp. 198-212.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.