An Operator-Norm Approach to Security with Quantum Advice
Abstract
Non-uniform security allows an adversary to receive bounded advice about an oracle before attempting a fresh challenge. This captures the most realistic attacks and has already been studied extensively in prior work. In this work, we introduce an operator-norm approach for non-uniform security in the quantum random oracle and random permutation models. This new approach yields a unified reduction for both search success probability and distinguishing advantage. Previously, the reduction only worked with success probability even in the decision games, yielding a worse bound. Our framework enables tight bounds for Yao's box, both with and without salting, and improved bounds for pseudorandom generators. We also prove an optimal generic salting theorem for decision games. By defining a property of a game, which separates the contributions of the existing queries in the offline stage and subsequent online queries, we obtain stronger bounds for specific salted constructions. These include salted permutation inversion, tight up to logarithmic factors, and salted random-function inversion, tight up to logarithmic factors and the gap already present in classical function inversion.
Related
- Dissipation-Enabled Operator-Norm Locality Bounds for Bose-Hubbard Hamiltonians
- Quantum State Search with Classical Interactive Advice
- No Size-Preserving Amplification with Quantum Advice
- Securing quantum error correction against misleading advice from AI agents
- Security of quantum key distribution with passive basis choice and detection-efficiency mismatch for a realistic satellite setup
BibTeX
@misc{hhan2026operatornorm,
title = {{An Operator-Norm Approach to Security with Quantum Advice}},
author = {Minki Hhan and Sunghyuk Jo and Qipeng Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37467},
eprint = {2609.37467},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37467},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An Operator-Norm Approach to Security with Quantum Advice
AU - Minki Hhan
AU - Sunghyuk Jo
AU - Qipeng Liu
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.37467
UR - https://arxiv.org/abs/2609.37467
AB - Non-uniform security allows an adversary to receive bounded advice about an oracle before attempting a fresh challenge. This captures the most realistic attacks and has already been studied extensively in prior work. In this work, we introduce an operator-norm approach for non-uniform security in the quantum random oracle and random permutation models. This new approach yields a unified reduction for both search success probability and distinguishing advantage. Previously, the reduction only worked with success probability even in the decision games, yielding a worse bound. Our framework enables tight bounds for Yao's box, both with and without salting, and improved bounds for pseudorandom generators. We also prove an optimal generic salting theorem for decision games. By defining a property of a game, which separates the contributions of the existing queries in the offline stage and subsequent online queries, we obtain stronger bounds for specific salted constructions. These include salted permutation inversion, tight up to logarithmic factors, and salted random-function inversion, tight up to logarithmic factors and the gap already present in classical function inversion.
ER -