International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Quantum Unpredictability

Authors:
Tomoyuki Morimae , Yukawa Institute for Theoritical Physics, Kyoto University
Shogo Yamada , Yukawa Institute for Theoritical Physics, Kyoto University
Takashi Yamakawa , NTT Social Informatics Laboratories, Tokyo, Japan
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2024
Abstract: Unpredictable functions (UPFs) play essential roles in classical cryptography, including message authentication codes (MACs) and digital signatures. In this paper, we introduce a quantum analog of UPFs, which we call unpredictable state generators (UPSGs). UPSGs are implied by pseudorandom function-like states generators (PRFSs), which are a quantum analog of pseudorandom functions (PRFs), and therefore UPSGs could exist even if one-way functions do not exist, similar to other recently introduced primitives like pseudorandom state generators (PRSGs), one-way state generators (OWSGs), and EFIs. In classical cryptography, UPFs are equivalent to PRFs, but in the quantum case, the equivalence is not clear, and UPSGs could be weaker than PRFSs. Despite this, we demonstrate that all known applications of PRFSs are also achievable with UPSGs. They include IND-CPA-secure secret-key encryption and EUF-CMA-secure MACs with unclonable tags. Our findings suggest that, for many applications, quantum unpredictability, rather than quantum pseudorandomness, is sufficient.
BibTeX
@inproceedings{asiacrypt-2024-34572,
  title={Quantum Unpredictability},
  publisher={Springer-Verlag},
  author={Tomoyuki Morimae and Shogo Yamada and Takashi Yamakawa},
  year=2024
}