A Quantum Attack on LWE with Arbitrary Error Distribution.

Apollo Albright, Boris Gelfand, Michael Dixon

We show that a class of optical physical unclonable functions (PUFs) can be efficiently PAC-learned to arbitrary precision with arbitrarily high probability, even in the presence of intentionally injected noise, given access to polynomially many challenge-response pairs, under mild and practical assumptions about the distributions of the noise and challenge vectors. We motivate our analysis by identifying similarities between the integrated version of Pappu’s original optical PUF design and the post-quantum Learning with Errors (LWE) cryptosystem. We derive polynomial bounds for the required number of samples and the computational complexity of a linear regression algorithm, based on size parameters of the PUF, the distributions of the challenge and noise vectors, and the desired accuracy and probability of success of the regression algorithm. We use a similar analysis to that done by Bootle et al. [“LWE without modular reduction and improved side-channel attacks against BLISS,” in Advances in Cryptology – ASIACRYPT 2018], who demonstrated a learning attack on poorly implemented versions of LWE cryptosystems. This extends the results of Rührmair et al. [“Optical PUFs reloaded,” Cryptology ePrint Archive, 2013], who presented a theoretical framework showing that a subset of this class of PUFs is learnable in polynomial time in the absence of injected noise, under the assumption that the optics of the PUF were either linear or had negligible nonlinear effects. (Rührmair et al. also included an experimental validation of this technique, which of course included measurement uncertainty, demonstrating robustness to the presence of natural noise.) We recommend that the design of strong PUFs should be treated as a cryptographic engineering problem in physics, as PUF designs would benefit greatly from basing their physics and security on standard cryptographic assumptions. Finally, we identify future research directions, including suggestions for how to modify an LWE-based optical PUF design to better defend against cryptanalytic attacks.

Alex Lombardi, Ethan Mook, Willy Quach +1 more

Максим Евгеньевич Широков

Assistant Professor Dr. S. Sreelatha, Assistant Professor Dr. P. Pushpa

The imminent arrival of large-scale quantum computers necessitates a transition from classical number-theoretic cryptography to post-quantum alternatives. Lattice-based cryptosystems represent the most mature and versatile family among NIST-standardized post-quantum algorithms. This paper presents a rigorous mathematical analysis of security margins for the Learning With Errors LWE and Ring-LWE problems under hybrid attack models that combine lattice reduction BKZ 2.0 with meet-in-the-middle techniques. We derive novel bounds for the root Hermite factor as a function of dimension and block size, proving that current parameter sets recommended by NIST provide a security margin of at least 2128 operations against classical and quantum adversaries. Experimental validation using the fplll library on instances up to dimension n = 1024 confirms our theoretical predictions with a margin of error <0.3%. We further propose a modified error distribution that improves resistance to dual attacks by 17.4% without significant performance degradation.

Yaru Wang, Haodong Jiang, Zhi Ma

Research on the security of lattice-based public-key encryption schemes against misuse attacks is an important part of the cryptographic assessment of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process. In particular, many NIST-PQC cryptosystems follow the same meta-cryptosystem. At EUROCRYPT 2019, Ba˘etu et al. mounted a classical key recovery under plaintext checking attacks (KR-PCA) and a quantum key recovery under chosen ciphertext attacks (KR-CCA). They analyzed the security of the weak version of nine submissions to NIST. In this paper, we focus on learning with error (LWE)-based FrodoPKE, whose IND-CPA security is tightly related to the hardness of plain LWE problems. We first review the meta-cryptosystem and quantum algorithm for solving quantum LWE problems. Then, we consider the case where the noise follows a discrete Gaussian distribution and recompute the success probability for quantum LWE by using Hoeffding bound. Finally, we give a quantum key recovery algorithm based on LWE under CCA attack and analyze the security of Frodo. Compared with the existing work of Ba˘etu et al., our method reduces the number of queries from 22 to 1 with the same success probability.

Xavier Bonnetain, María Naya‐Plasencia, André Schrottenloher