Efficient Quantum Public-Key Encryption From Learning With Errors
This addresses the need for secure quantum encryption methods, offering a novel approach with theoretical guarantees, though it is incremental in building on existing LWE-based cryptography.
The paper tackles the problem of constructing quantum public-key encryption by proposing a scheme based on the Extrapolated Dihedral Coset problem, which is equivalent to the Learning With Errors problem under quantum reductions, achieving information-theoretic security for limited public keys and LWE-based security for polynomial keys, with public keys of size ˜O(n) qubits and efficient 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 $\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.