Exploring One-Way Functions in Quantum Cryptography 🛡️ | TQC 2024

One-Wayness in Quantum Cryptography | Tomoyuki Morimae, Takashi Yamakawa

The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist [Kretschmer, TQC 2021; Morimae and Yamakawa, CRYPTO 2022; Ananth, Qian, and Yuen, CRYPTO 2022]. We therefore have the following important open problem in quantum cryptography: What is the most fundamental assumption in quantum cryptography? In this direction, [Brakerski, Canetti, and Qian, ITCS 2023] recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations. However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures. In this paper, we study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions proposed by Morimae and Yamakawa. We first revisit the definition of OWSGs and generalize it by allowing mixed output states. Then we show the following results. 1. We define a weaker version of OWSGs, which we call weak OWSGs, and show that they are equivalent to OWSGs. It is a quantum analogue of the amplification theorem for classical weak one-way functions. 2. (Bounded-time-secure) quantum digital signatures with quantum public keys are equivalent to OWSGs. 3. Private-key quantum money schemes (with pure money states) imply OWSGs. 4. Quantum pseudo one-time pad schemes imply both OWSGs and EFI pairs. For EFI pairs, single-copy security suffices. 5. We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statisticallyinvertible OWSGs, and show that they are equivalent to EFI pairs.

TQC 2024 | 9-13 September 2024 at OIST, Japan
http://tqc-conference.org

19th Conference on the Theory of Quantum Computation, Communication and Cryptography.

TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field.


Organisation:
OIST: Okinawa Institute for Science and Technology
Squids: Schools for Quantum Information Development



Sponsors:
JPMorganChase
Google Quantum AI
Horizon Quantum Computing
Quantinuum
Japan National Tourism Organization