Paper 2022/1384

Non-uniformity and Quantum Advice in the Random Oracle Model

Qipeng Liu, Simon Institute for the Theory of Computing
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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
QROM non-uniform attacks
Contact author(s)
qipengliu0 @ gmail com
History
2022-10-14: approved
2022-10-13: received
See all versions
Short URL
https://ia.cr/2022/1384
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1384,
      author = {Qipeng Liu},
      title = {Non-uniformity and Quantum Advice in the Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1384},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1384}},
      url = {https://eprint.iacr.org/2022/1384}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.