Sains Malaysiana 49(6)(2020): 1471-1478

http://dx.doi.org/10.17576/jsm-2020-4906-25

A Security Upgrade on the GGH Lattice-Based Cryptosystem
(Suatu Naik-taraf Keselamatan terhadap Sistem-kripto berasaskan Kekisi GGH)

ARIF MANDANGAN^1,2, HAILIZA KAMARULHAILI¹ & MUHAMMAD ASYRAF ASBULLAH^3,4*

¹School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM Penang, Pulau Pinang, Malaysia

²Mathematics, Real Time Graphics and Visualization Laboratory, Faculty of Sciences & Natural Resources, Universiti Malaysia Sabah, Jalan UMS 88400 Kota Kinabalu, Sabah, Malaysia

³Laboratory of Cryptography, Analysis and Structure, Institute for Mathematical Sciences, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor Darul Ehsan, Malaysia

⁴Centre of Foundation Studies for Agricultural Science, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor Datul Ehsan, Malaysia

Diserahkan: 9 Ogos 2019/Diterima: 12 Februari 2020

ABSTRACT

Due to the Nguyen’s attack, the Goldreich-Goldwasser-Halevi (GGH) encryption scheme, simply referred to as GGH cryptosystem, is considered broken. The GGH cryptosystem was initially addressed as the first practical lattice-based cryptosystem. Once the cryptosystem is implemented in a lattice dimension of 300 and above, its inventors was conjectured that the cryptosystem is intractable. This conjecture was based on thorough security analyses on the cryptosystem against some powerful attacks. This conjecture became more concrete when all initial efforts for decrypting the published GGH Internet Challenges were failed. However, a novel strategy by the Nguyen’s attack for simplifying the underlying Closest-Vector Problem (CVP) instance that arose from the cryptosystem, had successfully decrypted almost all the challenges and eventually made the cryptosystem being considered broken. Therefore, the Nguyen’s attack is considered as a fatal attack on the GGH cryptosystem. In this paper, we proposed a countermeasure to combat the Nguyen’s attack. By implementing the proposed countermeasure, we proved that the simplification of the underlying CVP instance could be prevented. We also proved that, the upgraded GGH cryptosystem remains practical where the decryption could be done without error. We are optimistic that, the upgraded GGH cryptosystem could make a remarkable return into the mainstream discussion of the lattice-based cryptography.

Keywords: Closest vector problem; GGH cryptosystem; lattice-based cryptography; post-quantum cryptography; shortest-vector problem

ABSTRAK

Berpunca daripada serangan Nguyen, skim penyulitan Goldreich-Goldwasser-Halevi (GGH), secara ringkasnya dirujuk sebagai sistem-kripto GGH, kini dipertimbangkan sebagai suatu skim yang telah rosak, iaitu tidak lagi selamat. Pada awalnya, sistem-kripto GGH pernah dirujuk sebagai sistem-kripto berasaskan-kekisi pertama yang praktikal. Apabila sistem-kripto ini dilaksanakan dalam kekisi berdimensi 300 dan ke atas, maka para pencipta sistem-kripto ini pernah menjangkakan bahawa ia adalah selamat. Jangkaan ini telah dibuat berdasarkan analisis keselamatan yang terperinci terhadap sistem-kripto tersebut menentang beberapa serangan yang hebat. Jangkaan tersebut telah menjadi semakin kukuh apabila kesemua usaha awal untuk menyahsulitkan beberapa Cabaran GGH yang dipaparkan di Internet (Cabaran Internet GGH) telah mengalami kegagalan. Namun demikian, suatu strategi baharu oleh serangan Nguyen dengan meringkaskan contoh Masalah Vektor-Terhampir (MVT) yang hadir secara terselindung disebalik sistem-kripto GGH, telah berjaya menyahsulitkan hampir kesemua Cabaran Internet GGH. Kesannya, sistem-kripto GGH telah dipertimbangkan sebagai suatu skim yang rosak dan tidak lagi selamat. Maka, serangan Nguyen sudah sewajarnya dipertimbangkan sebagai serangan pemusnah terhadap sistem-kripto GGH. Dalam kajian ini, kami mencadangkan suatu tindakan menyelamat bagi menentang serangan Nguyen. Melalui pelaksanaan tindakan menyelamat yang dicadangkan ini, kami buktikan bahawa proses meringkaskan contoh MVT disebalik sistem-kripto GGH kini dapat dielakkan. Kami juga buktikan bahawa sistem-kripto GGH yang telah dinaik-taraf ini masih kekal praktikal yang mana proses penyahsulitannya boleh dilaksanakan tanpa sebarang kesilapan. Kami optimis bahawa sistem-kripto GGH yang telah dinaik-taraf tahap keselamatannya ini mampu membuat penampilan semula ke medan perbincangan arus perdana dalam arena kriptografi berasaskan-kekisi.

Kata kunci: Kriptografi berasaskan kekisi; kriptografi pasca kuantum; masalah vektor terhampir; masalah vektor terpendek; sistem-kripto GGH

RUJUKAN

Ajtai, M. & Dwork, C. 1997. A public-key cryptosystem with worst-case/average-case equivalence. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. El Paso, Texas. pp. 284-293.

Barros, C.F.de. & Schechter, L.M. 2014. GGH may not be dead after all. Proceedings of XXXV Brazilian National Congress in Applied and Computational Mathematics (CNMAC2014). Natal, Brazil.

Elgamal, T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transaction on Information Theory 31(4): 469-472.

Galbraith, S.D. 2012. Mathematics of Public Key Cryptography. 1st ed. New York: Cambridge University Press.

Goldreich, O., Goldwasser, S. & Halevi, S. 1997a. Public-key cryptosystems from lattice reduction problems. Proceedings of 17^th Annual International Cryptology Conference. Santa Barbara, California, USA. pp. 112-131.

Goldreich, O., Goldwasser, S. & Halevi, S. 1997b. Challenges for the GGH Cryptosystem.http://groups.csail.mit.edu/cis/lattice/challenge.html.

Hoffstein, J., Pipher, J. & Silverman, J.H. 1998. NTRU: A new high-speed public key cryptosystem. Proceedings of the Third International Algorithmic Number Theory Symposium, ANTS’98. pp. 267-288.

Hoffstein, J., Pipher, J. & Silverman, J.H. 2008. An Introduction to Mathematical Cryptography. New York: Springer-Verlag.

Ismail, E.S. & Hasan, Y.A. 2006. A new version of ElGamal signature scheme. Sains Malaysiana 35(2): 69-72.

Jaju, S.A. & Chowhan, S.S. 2015. A modified RSA algorithm to enhance security for digital signature. 2015 International Conference and Workshop on Computing and Communication (IEMCON). Vancouver, Canada. pp. 1-5.

Koblitz, N. 1987. Elliptic curve cryptosystems. Mathematics of Computation 48(177): 203-209.

Lyubashevsky, V., Peikert, C. & Regev, O. 2010. On ideal lattices and learning with errors over rings. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg. pp. 1-23.   

Mandangan, A., Kamarulhaili, H. & Asbullah, M.A. 2019. On the smallest-basis problem underlying the GGH lattice-based cryptosystem. Malaysian Journal of Mathematical Sciences 13(S): 1-11.

Mandangan, A., Kamarulhaili, H. & Asbullah, M.A. 2018. On the underlying hard lattice problems of GGH encryption scheme. Proceedings of the 6th International Cryptology and Information Security Conference 2018 (CRYPTOLOGY2018). Port Dickson, Negeri Sembilan, Malaysia. pp. 42-50.

Micciancio, D. & Regev, O. 2009. Lattice-based cryptography.  In Post-Quantum Cryptography, edited by Bernstein, D.J., Buchmann, J. & Dahmen, E. Berlin, Heidelberg: Springer.

Nguyen, P. 1999. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto ‘97. In Advances in Cryptology - CRYPTO’ 99, edited by Wiener, M. Berlin, Heidelberg: Springer.

Pol, J.H.v.d. 2011. Lattice-based cryptography. Master of Science Theses, Eindhoven University of Technology (Unpublished).

Regev, O. 2005. On lattices, learning with errors, random linear codes, and cryptography. Stoc '05: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. Baltimore, MD, USA. pp. 84-93.

Rivest, R.L., Shamir, A. & Adleman, L. 1978. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2): 120-126.

Schnorr, C.P., Fischlin, M., Koy, H. & May, A. 1997. Lattice attacks on GGH Cryptosystem. Rump session of Crypto '97.

Serre, D.N. 2010. Matrices: Theory and Applications. 2nd ed. Heidelberg London: Springer-Verlag.

Shor, P.W. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. 35th Annual Symposium on Foundations of Computer Science. Santa Fe, NM, USA. pp. 124-134.

Yoshino, M. & Kunihiro, N. 2012. Improving GGH cryptosystem for large error vector. Information Symposium on Information Theory and its Applications (ISITA). pp. 416-420.

Zazali, H.H. & Othman, W.A.M. 2012.  Key exchange in Elliptic Curve Cryptography based on the decomposition problem. Sains Malaysiana 41(7): 907-910.

*Pengarang untuk surat-menyurat; email: ma_asyraf@upm.edu.my