Quantum information enables many cryptographic primitives that are impossible in the classical world. A line of works has developed cryptographic protocol under the assumption that quantum adversaries are restricted to noisy intermediate-scale quantum (NISQ) computing power, enabling strong one-time functionalities. But the advent of early fault-tolerant quantum computers eras will allow deeper logical quantum circuits, calling into questions the applicability of these NISQ-based assumptions. In this work, we adapt the classically accessible random oracle model (CAROM) as in [BDF+11] and [AK22], in which adversaries are only allowed to classically query the random oracle. The restriction is well motivated for NISQ quantum adversaries and may remain plausible in the presence of early fault-tolerant quantum computers. Then, we show that an efficient simulation-secure one-time memory (OTM) is possible under CAROM. Our protocol uses only BB84 states and has quadratic communication: for a $λ$ -bit message and integer-valued parameters $n=n(λ)$ and $\ell=\ell(λ)$ , the construction uses $n\ell$ qubits and $(n+2)λ$ classical bits, and for any quantum adversary with at most $2^{\ell/2-1}-1$ classical queries to the random oracle, its simulation advantage is at most $(n+3)\left(\frac{3}{4}\right)^n.$ Hence exponentially small simulation advantage in $n$ .Quantum information enables many cryptographic primitives that are impossible in the classical world. A line of works has developed cryptographic protocol under the assumption that quantum adversaries are restricted to noisy intermediate-scale quantum (NISQ) computing power, enabling strong one-time functionalities. But the advent of early fault-tolerant quantum computers eras will allow deeper logical quantum circuits, calling into questions the applicability of these NISQ-based assumptions. In this work, we adapt the classically accessible random oracle model (CAROM) as in [BDF+11] and [AK22], in which adversaries are only allowed to classically query the random oracle. The restriction is well motivated for NISQ quantum adversaries and may remain plausible in the presence of early fault-tolerant quantum computers. Then, we show that an efficient simulation-secure one-time memory (OTM) is possible under CAROM. Our protocol uses only BB84 states and has quadratic communication: for a $λ$-bit message and integer-valued parameters $n=n(λ)$ and $\ell=\ell(λ)$, the construction uses $n\ell$ qubits and $(n+2)λ$ classical bits, and for any quantum adversary with at most $2^{\ell/2-1}-1$ classical queries to the random oracle, its simulation advantage is at most $(n+3)\left(\frac{3}{4}\right)^n.$ Hence exponentially small simulation advantage in $n$.

quant-pharXiv:2609.32603Sep 29, 20260 citations

Quantum Biased Oracles

亮周河内, Akinori Kawachi

Jan 1, 20050 citations

Quantum Random Oracle Model for Quantum Public-Key Encryption

Tao Shang, Ranyiliu Chen, Qi Lei

Random oracle model is a general security analysis tool for rigorous security proof and effective cryptographic protocol design. In the quantum world, the attempts of constructing a quantum random oracle (QRO) have been made, such as quantum-accessible random oracle for post-quantum cryptography and quantum random oracle for quantum digital signature. As in the classical circumstance, it is crucial and challenging to design and instantiate the QRO model with an appropriate quantum hash function. In this work, we construct a QRO model for quantum public-key encryption against key-collision attack, due to the near-orthogonality property of the QRO. To explore a feasible instantiation procedure in the quantum setting, we distinctively give two instantiation examples of QRO by means of single-qubit rotation and quantum fingerprinting, and compare the numerical results of their performances under the key-collision attack. As a result, we extend the QRO model to the security analysis of quantum public-key encryption beyond quantum digital signature, and immunity from collision-type attacks.Random oracle model is a general security analysis tool for rigorous security proof and effective cryptographic protocol design. In the quantum world, the attempts of constructing a quantum random oracle (QRO) have been made, such as quantum-accessible random oracle for post-quantum cryptography and quantum random oracle for quantum digital signature. As in the classical circumstance, it is crucial and challenging to design and instantiate the QRO model with an appropriate quantum hash function. In this work, we construct a QRO model for quantum public-key encryption against key-collision attack, due to the near-orthogonality property of the QRO. To explore a feasible instantiation procedure in the quantum setting, we distinctively give two instantiation examples of QRO by means of single-qubit rotation and quantum fingerprinting, and compare the numerical results of their performances under the key-collision attack. As a result, we extend the QRO model to the security analysis of quantum public-key encryption beyond quantum digital signature, and immunity from collision-type attacks.

IEEE AccessJan 1, 201912 citations

Quantum Randomness

Scott Aaronson

American ScientistJan 1, 20146 citations

λ

-bit message and integer-valued parameters

n=n(λ)

and

\ell=\ell(λ)

, the construction uses

n\ell

qubits and

(n+2)λ

classical bits, and for any quantum adversary with at most

2^{\ell/2-1}-1

classical queries to the random oracle, its simulation advantage is at most

(n+3)\left(\frac{3}{4}\right)^n.

Hence exponentially small simulation advantage in

n