UPM Institutional Repository

On the underlying hard lattice problems of GGH encryption scheme


Citation

Mandangan, Arif and Kamarulhaili, Hailiza and Asbullah, Muhammad Asyraf (2018) On the underlying hard lattice problems of GGH encryption scheme. In: 6th International Cryptology and Information Security Conference 2018 (CRYPTOLOGY2018), 9-11 July 2018, Port Dickson, Negeri Sembilan, Malaysia. (pp. 42-50).

Abstract

Based on numerous experiments, the inventors of the Goldreich, Goldwasser and Halevi encryption scheme (GGH Scheme) conjectured that the Closest Vector Problem (CVP) instance which arose from the scheme was practically intractable in lattice with a dimension more than 300. However, some attacks had successfully broken the security of the scheme. Instead of solving the conjectured intractable CVP instance, these attacks managed to simplify the instance into its simpler form. Consequently, the security of the GGH Scheme is considered breached. In this paper, we address two most notable attacks on the GGH Scheme. On top of that, we propose a new attack on the GGH Scheme that manages to simplify the underlying CVP instance into a much simpler form. From that, we explicitly define the underlying CVP instance that arises from the GGH Scheme together with its corresponding simplified instances to give further illustration on the weakness points of the scheme. By identifying how these weaknesses are exploited by the attacks, further improvement on the GGH Scheme can be carried out in the future for making the scheme better and stronger.


Download File

[img] Text
Cryptology2018-3.pdf
Restricted to Repository staff only

Download (257kB)

Additional Metadata

Item Type: Conference or Workshop Item (Paper)
Divisions: Institute for Mathematical Research
Publisher: Institute for Mathematical Research, Universiti Putra Malaysia
Keywords: GGH scheme; Lattices-based cryptosystem; Post-quantum; Closest vector problem; Algebraic cryptanalysis
Depositing User: Nabilah Mustapa
Date Deposited: 03 Mar 2019 23:55
Last Modified: 03 Mar 2019 23:55
URI: http://psasir.upm.edu.my/id/eprint/66528
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item