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 different strategies and resu...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English English |
| Published: |
Penerbit UPM
2023
|
| Subjects: | |
| Online Access: | https://eprints.ums.edu.my/id/eprint/38471/1/ABSTRACT.pdf https://eprints.ums.edu.my/id/eprint/38471/2/FULL%20TEXT.pdf |
| _version_ | 1825715543976443904 |
|---|---|
| author | Arif Mandangan Kamarulhaili, H. Asbullah, M. A. |
| author_facet | Arif Mandangan Kamarulhaili, H. Asbullah, M. A. |
| author_sort | Arif Mandangan |
| collection | UMS |
| 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 different 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 examines 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 significantly 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 | 2024-04-09T03:46:50Z |
| format | Article |
| id | ums.eprints-38471 |
| institution | Universiti Malaysia Sabah |
| language | English English |
| last_indexed | 2024-04-09T03:46:50Z |
| publishDate | 2023 |
| publisher | Penerbit UPM |
| record_format | dspace |
| spelling | ums.eprints-384712024-03-08T06:40:38Z https://eprints.ums.edu.my/id/eprint/38471/ The Efficiency of Embedding-Based Attacks on the GGH Lattice-Based Cryptosystem Arif Mandangan Kamarulhaili, H. Asbullah, M. A. Q1-295 General QA1-939 Mathematics 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 different 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 examines 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 significantly 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. Penerbit UPM 2023 Article NonPeerReviewed text en https://eprints.ums.edu.my/id/eprint/38471/1/ABSTRACT.pdf text en https://eprints.ums.edu.my/id/eprint/38471/2/FULL%20TEXT.pdf Arif Mandangan 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 https://doi.org/10.47836/mjms.17.4.09 |
| spellingShingle | Q1-295 General QA1-939 Mathematics Arif Mandangan 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 |
| topic | Q1-295 General QA1-939 Mathematics |
| url | https://eprints.ums.edu.my/id/eprint/38471/1/ABSTRACT.pdf https://eprints.ums.edu.my/id/eprint/38471/2/FULL%20TEXT.pdf |
| work_keys_str_mv | AT arifmandangan theefficiencyofembeddingbasedattacksonthegghlatticebasedcryptosystem AT kamarulhailih theefficiencyofembeddingbasedattacksonthegghlatticebasedcryptosystem AT asbullahma theefficiencyofembeddingbasedattacksonthegghlatticebasedcryptosystem AT arifmandangan efficiencyofembeddingbasedattacksonthegghlatticebasedcryptosystem AT kamarulhailih efficiencyofembeddingbasedattacksonthegghlatticebasedcryptosystem AT asbullahma efficiencyofembeddingbasedattacksonthegghlatticebasedcryptosystem |