Paper 2022/1375

From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments

Abstract

Recently, Aaronson et al. (arXiv:2009.07450) showed that detecting interference between two orthogonal states is as hard as swapping these states. While their original motivation was from quantum gravity, we show its applications in quantum cryptography. 1. We construct the first public key encryption scheme from cryptographic non-abelian group actions. Interestingly, ciphertexts of our scheme are quantum even if messages are classical. This resolves an open question posed by Ji et al. (TCC ’19). We construct the scheme through a new abstraction called swap-trapdoor function pairs, which may be of independent interest. 2. We give a simple and efficient compiler that converts the flavor of quantum bit commitments. More precisely, for any prefix X, Y $\in$ {computationally,statistically,perfectly}, if the base scheme is X-hiding and Y-binding, then the resulting scheme is Y-hiding and X-binding. Our compiler calls the base scheme only once. Previously, all known compilers call the base schemes polynomially many times (Crépeau et al., Eurocrypt ’01 and Yan, Asiacrypt ’22). For the security proof of the conversion, we generalize the result of Aaronson et al. by considering quantum auxiliary inputs.