The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem
The Goldreich-Goldwasser-Halevi (GGH) cryptosystem is declared broken due to the modified versions of the embedding attacks, known as Nguyen’s σ, Nguyen’s 2σ and Lee-Hahn’s attacks. Despite using the same approach as the original embedding attack, these attacks deployed dif-ferent strategies and res...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Universiti Putra Malaysia
2023
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/103545/ |
| _version_ | 1848864045951614976 |
|---|---|
| author | Mandangan,, A. Kamarulhaili,, H. Asbullah,, M. A. |
| author_facet | Mandangan,, A. Kamarulhaili,, H. Asbullah,, M. A. |
| author_sort | Mandangan,, A. |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | The Goldreich-Goldwasser-Halevi (GGH) cryptosystem is declared broken due to the modified versions of the embedding attacks, known as Nguyen’s σ, Nguyen’s 2σ and Lee-Hahn’s attacks. Despite using the same approach as the original embedding attack, these attacks deployed dif-ferent strategies and resulted in different performances for breaking the GGH cryptosystem. In this paper, we described those strategies in detail. Moreover, we investigated the mathematical factors behind these attacks’ ability and performance discrepancies. Mathematical proof exam-ines and discusses the factors that triggered those variances. As a result, the expected lattice gap and implemented lattice dimensions are mathematically proven as the factors that signifi-cantly influenced these attacks’ performance. By demonstrating how the attacks manipulated these factors, any lattice-based cryptosystem that relies on the hardness of the CVP could avoid repeating the same slipup as the GGH. Hence, precautionary action could be proactively taken to prevent it from being threatened by embedding-based attacks. |
| first_indexed | 2025-11-15T13:42:35Z |
| format | Article |
| id | upm-103545 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-15T13:42:35Z |
| publishDate | 2023 |
| publisher | Universiti Putra Malaysia |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-1035452024-06-30T10:16:09Z http://psasir.upm.edu.my/id/eprint/103545/ The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem Mandangan,, A. Kamarulhaili,, H. Asbullah,, M. A. The Goldreich-Goldwasser-Halevi (GGH) cryptosystem is declared broken due to the modified versions of the embedding attacks, known as Nguyen’s σ, Nguyen’s 2σ and Lee-Hahn’s attacks. Despite using the same approach as the original embedding attack, these attacks deployed dif-ferent strategies and resulted in different performances for breaking the GGH cryptosystem. In this paper, we described those strategies in detail. Moreover, we investigated the mathematical factors behind these attacks’ ability and performance discrepancies. Mathematical proof exam-ines and discusses the factors that triggered those variances. As a result, the expected lattice gap and implemented lattice dimensions are mathematically proven as the factors that signifi-cantly influenced these attacks’ performance. By demonstrating how the attacks manipulated these factors, any lattice-based cryptosystem that relies on the hardness of the CVP could avoid repeating the same slipup as the GGH. Hence, precautionary action could be proactively taken to prevent it from being threatened by embedding-based attacks. Universiti Putra Malaysia 2023 Article PeerReviewed Mandangan,, A. and Kamarulhaili,, H. and Asbullah,, M. A. (2023) The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem. Malaysian Journal of Mathematical Sciences, 17 (4). pp. 673-690. ISSN 1823-8343; ESSN: 2289-750X https://mjms.upm.edu.my/lihatmakalah.php?kod=2023/December/17/4/673-690 10.47836/mjms.17.4.09 |
| spellingShingle | Mandangan,, A. Kamarulhaili,, H. Asbullah,, M. A. The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem |
| title | The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem |
| title_full | The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem |
| title_fullStr | The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem |
| title_full_unstemmed | The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem |
| title_short | The efficiency of embedding-based attacks on the GGH lattice-based cryptosystem |
| title_sort | efficiency of embedding-based attacks on the ggh lattice-based cryptosystem |
| url | http://psasir.upm.edu.my/id/eprint/103545/ http://psasir.upm.edu.my/id/eprint/103545/ http://psasir.upm.edu.my/id/eprint/103545/ |