A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID

Amit Behera; Giulio Malavolta; Tomoyuki Morimae; Tamer Mour; Takashi Yamakawa

Paper 2024/1567

A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID

Amit Behera

, Ben-Gurion University of the Negev

Giulio Malavolta, Bocconi University

Tomoyuki Morimae, Kyoto University

Tamer Mour, Bocconi University

Takashi Yamakawa, NTT Social Informatics Laboratories

Abstract

While in classical cryptography, one-way functions (OWFs) are widely regarded as the “minimal assumption,” the situation in quantum cryptography is less clear. Recent works have put forward two concurrent candidates for the minimal assumption in quantum cryptography: One-way state generators (OWSGs), postulating the existence of a hard search problem with an efficient verification algorithm, and EFI pairs, postulating the existence of a hard distinguishing problem. Two recent papers [Khurana and Tomer STOC’24; Batra and Jain FOCS’24] showed that OWSGs imply EFI pairs, but the reverse direction remained open. In this work, we give strong evidence that the opposite direction does not hold: We show that there is a quantum unitary oracle relative to which EFI pairs exist, but OWSGs do not. In fact, we show a slightly stronger statement that holds also for EFI pairs that output classical bits (QEFID). As a consequence, we separate, via our oracle, QEFID, and one-way puzzles from OWSGs and several other Microcrypt primitives, including efficiently verifiable one-way puzzles and unclonable state generators. In particular, this solves a problem left open in [Chung, Goldin, and Gray Crypto’24]. Using similar techniques, we also establish a fully black-box separation (which is slightly weaker than an oracle separation) between private-key quantum money schemes and QEFID pairs. One conceptual implication of our work is that the existence of an efficient verification algorithm may lead to qualitatively stronger primitives in quantum cryptography.

Note: Report-no: YITP-24-127. Minor corrections and typos were addressed in version 2.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Quantum Cryptography Minimal Assumptions Microcrypt Black-box separation
Contact author(s): behera @ post bgu ac il
giulio malavolta @ unibocconi it
tomoyuki morimae @ yukawa kyoto-u ac jp
tamer mour @ gmail com
takashi yamakawa obf @ gmail com
History: 2024-10-14: last of 3 revisions; 2024-10-04: received; See all versions
Short URL: https://ia.cr/2024/1567
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1567,
      author = {Amit Behera and Giulio Malavolta and Tomoyuki Morimae and Tamer Mour and Takashi Yamakawa},
      title = {A New World in the Depths of Microcrypt: Separating {OWSGs} and Quantum Money from {QEFID}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1567},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1567}
}