A security upgrade on the GGH lattice-based cryptosystem
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 dimensi...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English English |
| Published: |
Penerbit UKM
2020
|
| Subjects: | |
| Online Access: | https://eprints.ums.edu.my/id/eprint/29080/1/A%20security%20upgrade%20on%20the%20GGH%20lattice-based%20cryptosystem%20ABSTRACT.pdf https://eprints.ums.edu.my/id/eprint/29080/2/A%20security%20upgrade%20on%20the%20GGH%20lattice-based%20cryptosystem%20FULL%20TEXT.pdf |
| _version_ | 1825714219805310976 |
|---|---|
| author | Arif Mandangan Hailiza Kamarulhaili Muhammad Asyraf Asbullah |
| author_facet | Arif Mandangan Hailiza Kamarulhaili Muhammad Asyraf Asbullah |
| author_sort | Arif Mandangan |
| collection | UMS |
| description | 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. |
| first_indexed | 2024-03-06T03:08:33Z |
| format | Article |
| id | ums.eprints-29080 |
| institution | Universiti Malaysia Sabah |
| language | English English |
| last_indexed | 2024-03-06T03:08:33Z |
| publishDate | 2020 |
| publisher | Penerbit UKM |
| record_format | dspace |
| spelling | ums.eprints-290802021-09-20T02:44:54Z https://eprints.ums.edu.my/id/eprint/29080/ A security upgrade on the GGH lattice-based cryptosystem Arif Mandangan Hailiza Kamarulhaili Muhammad Asyraf Asbullah QA76.75-76.765 Computer software 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. Penerbit UKM 2020 Article PeerReviewed text en https://eprints.ums.edu.my/id/eprint/29080/1/A%20security%20upgrade%20on%20the%20GGH%20lattice-based%20cryptosystem%20ABSTRACT.pdf text en https://eprints.ums.edu.my/id/eprint/29080/2/A%20security%20upgrade%20on%20the%20GGH%20lattice-based%20cryptosystem%20FULL%20TEXT.pdf Arif Mandangan and Hailiza Kamarulhaili and Muhammad Asyraf Asbullah (2020) A security upgrade on the GGH lattice-based cryptosystem. Sains Malaysiana, 49. pp. 1471-1478. ISSN 0126-6039 (P-ISSN) , 2735-0118 (E-ISSN) http://journalarticle.ukm.my/15485/1/25.pdf http://dx.doi.org/10.17576/jsm-2020-4906-25 http://dx.doi.org/10.17576/jsm-2020-4906-25 |
| spellingShingle | QA76.75-76.765 Computer software Arif Mandangan Hailiza Kamarulhaili Muhammad Asyraf Asbullah A security upgrade on the GGH lattice-based cryptosystem |
| title | A security upgrade on the GGH lattice-based cryptosystem |
| title_full | A security upgrade on the GGH lattice-based cryptosystem |
| title_fullStr | A security upgrade on the GGH lattice-based cryptosystem |
| title_full_unstemmed | A security upgrade on the GGH lattice-based cryptosystem |
| title_short | A security upgrade on the GGH lattice-based cryptosystem |
| title_sort | security upgrade on the ggh lattice based cryptosystem |
| topic | QA76.75-76.765 Computer software |
| url | https://eprints.ums.edu.my/id/eprint/29080/1/A%20security%20upgrade%20on%20the%20GGH%20lattice-based%20cryptosystem%20ABSTRACT.pdf https://eprints.ums.edu.my/id/eprint/29080/2/A%20security%20upgrade%20on%20the%20GGH%20lattice-based%20cryptosystem%20FULL%20TEXT.pdf |
| work_keys_str_mv | AT arifmandangan asecurityupgradeonthegghlatticebasedcryptosystem AT hailizakamarulhaili asecurityupgradeonthegghlatticebasedcryptosystem AT muhammadasyrafasbullah asecurityupgradeonthegghlatticebasedcryptosystem AT arifmandangan securityupgradeonthegghlatticebasedcryptosystem AT hailizakamarulhaili securityupgradeonthegghlatticebasedcryptosystem AT muhammadasyrafasbullah securityupgradeonthegghlatticebasedcryptosystem |