Paper 2022/1375

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

Minki Hhan, Korea Institute for Advanced Study
Tomoyuki Morimae, Kyoto University
Takashi Yamakawa, NTT Social Informatics Laboratories, Kyoto University

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.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Contact author(s)
minkihhan @ kias re kr
tomoyuki morimae @ yukawa kyoto-u ac jp
takashi yamakawa @ ntt com
2023-04-23: revised
2022-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Minki Hhan and Tomoyuki Morimae and Takashi Yamakawa},
      title = {From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1375},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.