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

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, the 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 ∈ 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.

When can we efficiently distinguish a superposition of two orthogonal states from their probabilistic mix? A folklore answer to this question was that we can efficiently distinguish them whenever we can efficiently map one of the states to the other. Recently, Aaronson, Atia and, Susskind [AAS20] gave a complete answer to the question. They confirmed that the folklore was almost correct but what actually characterizes the distinguishability is the ability to swap the two states rather than the ability to map one of the states to the other. We explain their result in more detail by using the example of Schrödinger's cat following [AAS20]. Let |Alive and |Dead be orthogonal states, which can be understood as the states of alive and dead cats in Schrödinger's cat experiment. Then, the authors showed that one can efficiently swap |Alive and |Dead