Our main result is a quantum public-key encryption scheme based on the Extrapolated Dihedral Coset problem (EDCP) which is equivalent, under quantum polynomial-time reductions, to the Learning With Errors (LWE) problem. For limited number of public keys (roughly linear in the security parameter), the proposed scheme is information-theoretically secure. For polynomial number of public keys, breaking the scheme is as hard as solving the LWE problem. The public keys in our scheme are quantum states of size $\tilde{O}(n)$ qubits. The key generation and decryption algorithms require $\tilde{O}(n)$ qubit operations while the encryption algorithm takes $O(1)$ qubit operations.
Our main result is a quantum public-key encryption scheme based on the Extrapolated Dihedral Coset problem (EDCP) which is equivalent, under quantum polynomial-time reductions, to the Learning With Errors (LWE) problem. For limited number of public keys (roughly linear in the security parameter), the proposed scheme is information-theoretically secure. For polynomial number of public keys, breaking the scheme is as hard as solving the LWE problem. The public keys in our scheme are quantum states of size O~(n) qubits. The key generation and decryption algorithms require O~(n) qubit operations while the encryption algorithm takes O(1) qubit operations.
In this work, we introduce a novel post-quantum public key encryption scheme over integers, leveraging a hybrid approach that combines large random numbers with the Learning With Errors (LWE) system. The scheme addresses the security challenges posed by quantum computing advancements, aiming to provide a robust solution resistant to quantum-based attacks. By using the unknown random number hardness assumption with enhancements to the traditional LWE framework and operating directly on integers, this approach ensures a high level of cryptographic security while maintaining computational efficiency. Extensive theoretical and experimental analyses demonstrate that the proposed encryption system achieves state-of-the-art performance: encryption execution time as low as2.45×10−5seconds, decryption time of4.47×10−5seconds, and an integrity check time of5.30×10−5seconds. Moreover, the ciphertext size is reduced to only 1330 bits while maintaining a 256 -bit security level, representing a significant reduction in storage requirements compared to conventional lattice-based approaches. These results confirm that our scheme not only provides strong quantum-resistant security guarantees but also delivers excellent efficiency and scalability, making it a viable candidate for secure communications in bandwidth-limited and resource-constrained environments in the quantum era.
To prevent eavesdropping and tampering, network security protocols take advantage of asymmetric ciphers to establish session-specific shared keys with which further communication is encrypted using symmetric ciphers. Commonly used asymmetric algorithms include public key encryption, key exchange, and identity-based encryption (IBE). However, network security protocols based on classic identity-based encryption schemes do not have perfect forward secrecy. To solve this problem, we construct the first quantum IBE (QIBE) scheme based on the learning with errors (LWE) problem, which is also the first cryptographic scheme that applies the LWE problem to quantum encryption. We prove that our scheme is fully secure under the random oracle model and highlight the following advantages: (1) Network security protocols with our QIBE scheme provide perfect forward secrecy. The ciphertext is transmitted in the form of a quantum state unknown to the adversary and cannot be copied and stored. Thus, in network security protocols based on QIBE construction, the adversary does not have any previous quantum ciphertext to decrypt for obtaining the previous session key, even if the private identity key is threatened. (2) Classic key generation centre (KGC) systems can still be used in the QIBE scheme to generate and distribute private identity keys, reducing the cost when implementing this scheme. The classic KGC systems can be used because the master public and secret keys of our scheme are both in the form of classic bits. Finally, we present quantum circuits to implement this QIBE scheme and analyse its required quantum resources for given numbers of qubits, Hadamard gates, phase gates, T gates, and CNOT (controlled-NOT) gates. One of our main findings is that the quantum resources required by our scheme increase linearly with the number of plaintext bits to be encrypted.
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.
We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. (*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.
The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems.
In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let ζp be a primitive p-th root of unity, let π=ζp−1, and write q=pt and L=t(p−1). We work over Rq=Zq[ζp]≅Z[ζp]/(πL), where the isomorphism follows from the total ramification identity (p)=(π)p−1. We exploit the resulting π-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo πL,πL−1,…,π. For every fixed prime p and modulus q=pt, our algorithm solves the CCP in time and sample complexity 2Op(lognlogq), using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when q=poly(n). This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting.
However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.
We show polynomial-time quantum algorithms for the following problems:
(*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant.
(*) Extrapolated dihedral coset problem (EDCP) with certain parameters.
(*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.
The SIS, EDCP, and LWE problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for those variants.
Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contributions are introducing a filtering technique and solving LWE given LWE-like quantum states with interesting parameters.