Optimizing Gaussian Measure of Lattices using Dimensionality Reduction
Kelechi Chuwkunonyerem Emerole, Said Boussakta · 2020
The Shortest Vector problem is an intractable mathematical basis for the design of Learning with error-based Lattice cryptography which is a cryptographic primitive that has the capability to secure data against quantum threats. Approaches to tackle this problem have been based on the sampling from a discrete Gaussian distribution that is close to a theoretical one by exploiting the orthogonality of a lattice basis to ensure the secrecy of the basis from a polynomial time algorithm especially with a large dimensional Euclidean space. This orthogonality is achieved by using LLL(Lenstra-Lenstra-Lovasz) reduction to decompose the basis into its Gram-Schmidt equivalent with drawbacks in complexity as well as reduction to worst case scenarios. We propose to apply Dimensionality reduction to decompose the basis into linear independent vectors by constructing a collapse function as an optimization problem which can be solved on the condition that a Projection of the basis vectors from the High dimensional space to low dimensional manifold would have nearly orthogonal constitution. From the result of the Monte Carlo simulation, our approach improves the BER performance over the LLL algorithm for about 1db and 4db in the 4 × 4 and 6 × 6 uncoded system using 4QAM constellation.