Abstract This paper presents two distinct chosen-ciphertext attacks (CCA) against lattice-based encryption and decryption schemes, in particular based on the LWE problem, a class of post-quantum cryptographic algorithms. First we attack fully homomorphic encryption-decryption schemes (FHE) exploiting the additional information that the small modulus reduction offers. We compare this attack with the $$CPA^D$$ attack presented in Checri (2024). Afterwards we present an attack against Kyber.CPAPKE, and another against a weakened version of Kyber.KEM where the cyphertext is not checked for correctness; and compare them to the previous Key Mismatch Attack in Qin (2021). Our work remarks the importance of protecting the decryption function in the different implementations of these cryptographic schemes, and the importance of CCA security in nowadays cryptosystems.
Abstract This paper presents two distinct chosen-ciphertext attacks (CCA) against lattice-based encryption and decryption schemes, in particular based on the LWE problem, a class of post-quantum cryptographic algorithms. First we attack fully homomorphic encryption-decryption schemes (FHE) exploiting the additional information that the small modulus reduction offers. We compare this attack with the CPAD attack presented in Checri (2024). Afterwards we present an attack against Kyber.CPAPKE, and another against a weakened version of Kyber.KEM where the cyphertext is not checked for correctness; and compare them to the previous Key Mismatch Attack in Qin (2021). Our work remarks the importance of protecting the decryption function in the different implementations of these cryptographic schemes, and the importance of CCA security in nowadays cryptosystems.
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.
Quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key requires a linear number of decryption queries. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.
Abstract: In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1) We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2) We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3) The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.
Fully homomorphic encryption (FHE) scheme allows for performing computations on encrypted data without decrypting it which makes it more popular in various domains. Most previous FHE constructions are limited by the large ciphertext expansion rate and error growth rate. Learning with errors (LWE) problem is a popular primitive for constructing lattice-based FHE. Many algebraic variants of LWE are also developed with further promising cryptographic features. Most previous known LWE variants (over the commutative base rings) are unified into a general framework by Peikert et al. at TCC 2019. In 2022, a new algebraically structured LWE problem over the d-degree cyclic algebra (CLWE) (with modulus q), a typical non-commutative ring, was proposed by Grover et al.. To further explore the utility and potential advantages of this new variant, it is interesting to design new lattice-based FHE schemes by using CLWE. In this paper, by following the diagrams of Gentry-Sahai-Waters (GSW13 for short), we propose a FHE scheme based on the CLWE with an even small ciphertext size. Due to our further expansion of the plaintext space, the average ciphertext expansion rate (CER for short) is smaller. More precisely, compared to original GSW13 and the related GSW-style constructions, the ciphertext size of our proposal is reduced by almost at least 23.69%, and the average CER is reduced about 96% due to our expansion of the plaintext space. Besides, our FHE has an even small error growth rate (EGR for short). After one time multiplication of two ciphertexts, the asymptotical EGR is reduced about 49.8% compared to the original GSW13 and the related GSW-style constructions. Typically, the smaller ciphertext size, CER and EGR make our FHE scheme more efficient in trusted computing environment.
This paper proposes a generic construction of CCA-secure fully homomorphic encryption (FHE) scheme.First, we introduce a new primitive called multi-identity fully homomorphic encryption, which works in the multi-identity setting; that is, homomorphic evaluation can performed on ciphertexts created with different identities.Then, we propose an IND-sID-CPA secure multi-identity leveled FHE scheme over lattice.Finally, we present CCA-secure FHE from our proposed multi-identity FHE scheme and strongly EUF-CMA secure signature.The security analysis shows that our FHE scheme is CCA2-secure when the evaluation key is unavailable to the adversary, and remains CCA1-secure when the evaluation key is exposed in the standard model.
In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1) We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2) We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3) The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.