Security And Key Generation Upgrades On The Goldreich-Goldwasser-Halevi Lattice-Based Encryption Scheme
Loading...
Date
2021-03
Authors
Mandangan, Arif
Journal Title
Journal ISSN
Volume Title
Publisher
Universiti Sains Malaysia
Abstract
Security of the Goldreich-Goldwasser-Halevi encryption scheme
(GGH cryptosystem) relies on the lattice-based computational problem namely the
Closest-Vector Problem (CVP) which is proven to be NP-hard. Nevertheless, issues
surrounding its security and key generation algorithm have limit the interest from
researchers and practitioners. In this study, upgrades on the security and key generation
of the GGH cryptosystem are proposed. In security aspect, a novel countermeasure is
proposed to beat the fatal attack on it known as the Nguyen’s embedding attack. The
countermeasure repairs the main flaw in the design of the GGH cryptosystem that is
exploited by the Nguyen’s embedding attack. The countermeasure is developed using
two strategies. The first strategy is by introducing a new set of entries, denoted as 𝐸,
for generating the entries of the vector 𝑒⃗ to prevent this vector from being eliminated
from the encryption equation. This is vital to ensure that the simplification of the GGHCVP
done by the Nguyen’s embedding attack can be stopped. In the second strategy,
a distribution to fix the number of appearances for each entry of the set 𝐸 in the vector
𝑒⃗ is proposed to maintain the GGH-CVP distance as 𝜎√𝑛. On the other hand, key
generation aspect addresses keys categorization and private key inversion issues. To
overcome the keys categorization issue, few new conditions in the key generation
algorithm are established. The currently deployed categorization criteria are unclear
and too subjective. By considering the established conditions, the classification
process is clearer and technical error can be prevented. Finally, a new integer matrix is developed for addressing inversion problem surrounding the private basis 𝐺 ∈ ℤ𝑛×𝑛.
The inverse of this matrix, 𝐺−1 ∈ ℝ𝑛×𝑛 consists of numerous long floating-point
numbers. Consequently, storing and operating the matrix 𝐺−1 in decryption algorithm
become issues that might permit the occurrence of decryption error. Therefore, the
developed matrix 𝐺 ̃
∈ ℤ𝑛×𝑛 is an integer matrix that has an inverse 𝐺 ̃
−1 ∈ ℝ𝑛×𝑛
consisting only a single non-integer entry. Through the proposed upgrades, the GGH
cryptosystem would potentially make a remarkable return into mainstream discussion
in lattice-based cryptography as well as post quantum cryptography.
Description
Keywords
Mathematics