arXiv preprint ·
Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Checking Leakage Witnesses versus Certifying Bounded Non-Leakage
Zero-Storage Procedural Neural Synthesis via Boundary Dynamics: Formal Verification in Lean 4 and Bare-Metal Gauntlet Validation
DegreeSpar: Structured Degree Sparsity for Efficient Secure Transformer Inference
ORBIT: A Framework for Multi-Agent Safety and Security Evaluations
Residual Transferability in Neural Image Watermarking
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.