Some algorithms for learning with errors

Nico Döttling, Jörn Müller‐Quade

Liljana Babinkostova, Ariana Chin, Aaron Kirtland +2 more

Abstract As quantum computing advances rapidly, guaranteeing the security of cryptographic protocols resistant to quantum attacks is paramount. Some leading candidate cryptosystems use the learning with errors (LWE) problem, attractive for its simplicity and hardness guaranteed by reductions from hard computational lattice problems. Its algebraic variants, ring-learning with errors (RLWE) and polynomial learning with errors (PLWE), gain efficiency over standard LWE, but their security remains to be thoroughly investigated. In this work, we consider the “smearing” condition, a condition for attacks on PLWE and RLWE introduced in Elias et al. We expand upon some questions about smearing posed by Elias et al. and show how smearing is related to the coupon collector’s problem. Furthermore, we develop an algorithm for computing probabilities related to smearing. Finally, we present a smearing-based algorithm for solving the PLWE problem.

Oded Regev

Hesty Sitohang, Roy Untung Pratama Saing, Agnes Selaras Osabela Sarahono +3 more

Ring-LWE (Ring Learning With Errors) is a post-quantum cryptography algorithm based on mathematical problems in number theory and algebra. It is an extension of LWE (Learning With Errors) first introduced by Oded Regev and is used for secure data encryption from quantum computer attacks. The process consists of three main steps: key generation, encryption, and decryption. Key generation uses random polynomials and noise to create public and private keys. While encryption produces ciphertext in the form of polynomial pairs, decryption uses the private key to return the ciphertext to the original message. To conduct the experiment, the modulus value q = 17, the modulus polynomial f(x) = x2 + 1, and the private key and random polynomial have been determined. The results of the experiment show that the message can be accurately decrypted using the private key, thus proving the success of this algorithm in maintaining data security. With its security properties that are resistant to quantum attacks, Ring-LWE is a promising alternative for future cryptography.

Jinfeng Zeng, Muxi Zheng, Hang Li +2 more

Abstract Variational Quantum Algorithms (VQAs) offer a promising approach to solving optimization problems on quantum computers. In this paper, we investigate the use of VQAs to solve the Learning With Errors (LWE) problem, a crucial challenge in post-quantum cryptography. We propose a VQA-based algorithm and a Quantum Approximate Optimization Algorithm (QAOA) for solving the Learning Parity with Noise (LPN) problem, a special case of LWE. We examine the sample complexity of combinatorial optimization methods for LPN and analyze the performance of these two variational quantum algorithms in terms of quantum resources. For the VQA algorithm, both the number of qubits and the circuit depth scale polynomially with the secret key length n . In the case of QAOA, the number of qubits matches the secret key length n , but the CNOT gate count increases exponentially with n . However, numerical simulations of the VQA-based algorithm show that choosing optimal ansatzes and optimization methods can significantly enhance success rates.

Daniele Micciancio