Page 117 - Kaleidoscope Academic Conference Proceedings 2024
P. 117
Innovation and Digital Transformation for a Sustainable World
Figure 3 – Schematic of the proposed quantum-resistant encryption for secure end-to-end communication.
to the integration of the Quantum key distributions into this reduction doesn’t imply that these lattice problems
systems other than the site-to-site VPNs. This issue may are NP-Hard for linear approximation factors. Even if a
be resolved by deriving many keys from the original key quantum solver for LWE worked for parameters very close
that QKD supplied. For instance, one may utilize a single to 1, the resulting approximation factor for lattice problems
QKD key with keys that are generated for every message would still be greater than . Currently, we lack proof
transmitted between two fixed participants on the same day. that these approximate lattice problems are NP-Hard for
It could also go beyond the classical client-server model and linear approximation factors. Therefore, while a quantum
has many use cases such as a secure quantum channel for polynomial-time algorithm for LWE would place LWE
the military or some esteemed organization. Since we are within BQP, it wouldn’t directly impact classical hardness
successfully able to integrate it into the system and establish or NP-hardness questions. Such an algorithm would still
secure communication between two parties. There can be be a significant breakthrough. The approximate versions of
still some key exchanges and session chatting features which lattice problems aren’t known to be NP-Hard, and efficient
we are introducing further. algorithms for solving them remain elusive.
6.1 Computational Complexity for Attacker 7. CONCLUSION AND FUTURE WORK
The difficulty of breaking an encryption scheme based on
The security of this lattice-based encryption scheme relies
Learning With Errors (LWE) is closely tied to solving
on the difficulty of solving the Shortest Vector Problem
the Shortest Vector Problem (SVP) for the lattice defined
(SVP) in high-dimensional lattices, particularly when random
by the encryption parameters. As lattice dimensionality
dimensions and error terms are introduced. The algorithm
increases, the computational complexity of solving SVP
generates a random basis, random dimensions, and random
grows exponentially, making it extremely challenging for
errors for each bit, making it computationally infeasible for
attackers. Randomly choosing dimensions for each bit
an attacker to recover the secret key or decrypt the ciphertext
and adding random error terms during encryption further
efficiently. However, the size and storage of ciphertexts
increase complexity. The hardness of breaking an LWE-based
and messages impose restrictions on the length of messages
encryption scheme depends on lattice dimensionality, the
that can be sent at once. To address this, we are exploring
modulus used, and the number of random dimensions
various transformations and researching methods to reduce
chosen during encryption. Solving SVP in high-dimensional
the ciphertext size to a logarithmic scale, possibly through
lattices is believed to be exponentially complex, even for
binary search algorithms. Additionally, we are investigating
powerful computers. In a client-server model, LWE-based
techniques similar to the Number Theoretic Transform (NTT)
encryption secures encrypted chats stored in the database,
for optimizing matrix multiplications, which could enhance
making decryption without keys extremely difficult due
performance without compromising security.
to the complexity of solving SVP and the randomness
introduced. Brute-forcing through the more than 10 1200
possible combinations in LWE encryption makes chosen REFERENCES
ciphertext attacks (CCA) infeasible. Regev’s reduction shows
that a quantum solver for the LWE problem with certain [1] Oded Regev, "The Learning with Errors Problem"
parameters can solve approximate versions of lattice problems in Blavatnik School of Computer Science, Tel Aviv
like SVP and SIVP over lattices of dimension . However, University.
– 73 –