Quantum Unpredictability
Preprint
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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- On Black-Box Separations of Quantum Digital Signatures from Pseudorandom States2024
- Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries2024
- Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions2024
- Commitments from Quantum One-Wayness2024
- Pseudorandomness with Proof of Destruction and Applications2023
- Classical Homomorphic Encryption for Quantum CircuitsSIAM Journal on Computing, 2020