Resilience of lattice-based Cryptosystems to Quantum Attacks

In this paper, we present first ideas and concepts for a methodology testing the robustness of public key cryptosystems with respect to quantum attacks. As an example, the key encapsulation mechanism (KEM) described in the NIST report FIPS 203 is considered. This cryptosystem is based on a learning with error problem (LWE problem). For this reason, different quantum algorithms solving LWE problems are analyzed regarding their efficiency and precision. Thereby, we restrict ourselves to computational means i.e. the respective quantum algorithms are implemented using Python based libraries such as Eclipse Qrisp or the software packages provided by D-Wave. In order to be able to test the different algorithms, the key generator described in FIPS 203 is re-implemented, such that keys with reduced lengths can be generated. In particular, it is of great interest to investigate, which key length guarantees a satisfactory security level. Another interesting issue is how the knowledge of side-channel attacks can be used to reduce a given LWE problem. Our test results are considered as training data for neural networks having the key lengths, the type of the quantum solver and further parameters as inputs and a number for the security level of the corresponding key as output. The envisioned neural networks can be used for predicting whether a particular algorithm can be efficiently attacked under the given circumstances and parameters known to the attacker.