Non-uniformity and quantum advice in the quantum random oracle model

DOI10.1007/978-3-031-30545-0_5MaRDI QIDQ6138081zbMATH OpenOpenAlexFDO

Authors Qipeng Liu

Publication date 16 January 2024

Published in Advances in Cryptology – EUROCRYPT 2023 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.06693

Mathematics Subject Classification ID

Cryptography (94A60) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94) Computer security (68M25)

Abstract: QROM (quantum random oracle model), introduced by Boneh et al. (Asiacrypt 2011), captures all generic algorithms. However, it fails to describe non-uniform quantum algorithms with preprocessing power, which receives a piece of bounded classical or quantum advice. As non-uniform algorithms are largely believed to be the right model for attackers, starting from the work by Nayebi, Aaronson, Belovs, and Trevisan (QIC 2015), a line of works investigates non-uniform security in the random oracle model. Chung, Guo, Liu, and Qian (FOCS 2020) provide a framework and establish non-uniform security for many cryptographic applications. In this work, we continue the study on quantum advice in the QROM. We provide a new idea that generalizes the previous multi-instance framework, which we believe is more quantum-friendly and should be the quantum analogue of multi-instance games. To this end, we match the bounds with quantum advice to those with classical advice by Chung et al., showing quantum advice is almost as good/bad as classical advice for many natural security games in the QROM. Finally, we show that for some contrived games in the QROM, quantum advice can be exponentially better than classical advice for some parameter regimes. To our best knowledge, it provides some evidence of a general separation between quantum and classical advice relative to an unstructured oracle.

Recommendations

• Quantum random oracle model with auxiliary input
• Classical vs quantum random oracles
• A Note on the Instantiability of the Quantum Random Oracle
• Non-Observable Quantum Random Oracle Model
• Random oracles in a quantum world

Cites work

• scientific article; zbMATH DE number 5485520 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 7759460 (Why is no real title available?)
• A cryptanalytic time-memory trade-off
• Exponential separation of quantum and classical one-way communication complexity
• Fixing cracks in the concrete: random oracles with auxiliary input, revisited
• Limitations of Quantum Advice and One-Way Communication
• Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models
• On the power of nonuniformity in proofs of security
• Quantum Arthur-Merlin games
• Quantum computation and quantum information. 10th anniversary edition
• Quantum random oracle model with auxiliary input
• Quantum versus classical proofs and advice
• Random Oracles and Auxiliary Input
• Random oracles and non-uniformity
• Random oracles in a quantum world
• Schrödinger's pirate: how to trace a quantum decoder
• The function-inversion problem: barriers and opportunities
• Time space tradeoffs for attacks against one-way functions and PRGs
• Unifying presampling via concentration bounds

Cited in

(3)

• Tight characterizations for preprocessing against cryptographic salting
• Unconditionally secure quantum commitments with preprocessing
• Unconditionally secure commitments with quantum auxiliary inputs

This page was built for publication: Non-uniformity and quantum advice in the quantum random oracle model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138081)