A certified randomness protocol in the quantum random oracle model is obtained that proves unconditional security of this protocol against adversaries making subexponentially-many adaptive quantum queries to the random oracle.
Abstract
We obtain a certified randomness protocol in the quantum random oracle model. The protocol is non-interactive and publicly verifiable with a classical verifier, and is based on Yamakawa and Zhandry's proof of quantumness [JACM'24]. We prove unconditional security of this protocol against adversaries making subexponentially-many adaptive quantum queries to the random oracle. Prior work on certified randomness relative to a random oracle additionally assumed the Aaronson--Ambainis conjecture or proved security only against low query-depth adversaries.
In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a codeword preimage of a publicly computable function H. They conjectured that given any H, a successful prover must sample their preimage from a...
This work defines and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript, and shows an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.
This work proves a new, essentially tight, lower bound on the single-round von Neumann entropy against adversaries holding both classical and quantum side-information, and establishes the main ingredient for rigorous security proofs against general quantum attacks in this framework.
Thomas A. Hahn, Efrat Gerchkovitz, Ester Yehuda et al.· 0 citations
We show how to compile an arbitrary classical circuit into a fault-tolerant circuit, which performs the desired computation even when an almost-linear number of bits are adversarially chosen and corrupted in each timestep. Using a variant of this fault-tolerance scheme that only detects (rather than corrects) corruptio...
Anurag Anshu, N. P. Breuckmann, Louis Golowich et al.· 0 citations
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, wh...
Zvika Brakerski, Andrew Huang, Y. Kalai et al.· 0 citations
A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advanta...
Markus Bläser, M. Gullans, Dominik Hangleiter et al.· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
