### Quantum commitments and signatures without one-way functions

Tomoyuki Morimae and Takashi Yamakawa

##### Abstract

In the classical world, the existence of commitments is equivalent to the existence of one-way functions. In the quantum setting, on the other hand, commitments are not known to imply one-way functions, but all known constructions of quantum commitments use at least one-way functions. Are one-way functions really necessary for commitments in the quantum world? In this work, we show that non-interactive quantum commitments (for classical messages) with computational hiding and statistical binding exist if pseudorandom quantum states exist. Pseudorandom quantum states are sets of quantum states that are efficiently generated but their polynomially many copies are computationally indistinguishable from the same number of copies of Haar random states [Ji, Liu, and Song, CRYPTO 2018]. It is known that pseudorandom quantum states exist even if BQP=QMA (relative to a quantum oracle) [Kretschmer, TQC 2021], which means that pseudorandom quantum states can exist even if no quantum-secure classical cryptographic primitive exists. Our result therefore shows that quantum commitments can exist even if no quantum-secure classical cryptographic primitive exists. In particular, quantum commitments can exist even if no quantum-secure one-way function exists. In this work, we also consider digital signatures, which are other fundamental primitives in cryptography. We show that one-time secure digital signatures with quantum public keys exist if pseudorandom quantum states exist. In the classical setting, the existence of digital signatures is equivalent to the existence of one-way functions. Our result, on the other hand, shows that quantum signatures can exist even if no quantum-secure classical cryptographic primitive (including quantum-secure one-way functions) exists.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
quantum cryptographybit commitmentdigital signaturesone-way functions
Contact author(s)
tomoyuki morimae @ yukawa kyoto-u ac jp
takashi yamakawa ga @ hco ntt co jp
History
2022-02-14: revised
See all versions
Short URL
https://ia.cr/2021/1691

CC BY

BibTeX

@misc{cryptoeprint:2021/1691,
author = {Tomoyuki Morimae and Takashi Yamakawa},
title = {Quantum commitments and signatures without one-way functions},
howpublished = {Cryptology ePrint Archive, Paper 2021/1691},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1691}},
url = {https://eprint.iacr.org/2021/1691}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.