Certified Randomness without Structure Against Shallow-Query Adversaries

• URL: http://arxiv.org/abs/2608.24832v1
• Date: Tue, 25 Aug 2026 17:15:01 GMT
• Title: Certified Randomness without Structure Against Shallow-Query Adversaries
• Abstract summary: Yamakawa and Zhandry constructed a proof of quantumness in the quantum random oracle model (QROM)<n>We prove the security of the certifiable randomness protocol of Yamakawa-Zhandry unconditionally, without relying on the unproven Aaronson-Ambainis conjecture.
• Score: 7.663706649394509
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 high-entropy distribution over possible answers. If true, this would give a certifiable randomness protocol in the quantum random oracle model. As partial evidence for their conjecture, Yamakawa and Zhandry proved the security of their certifiable randomness protocol assuming the Aaronson-Ambainis conjecture. We prove the security of the certifiable randomness protocol of Yamakawa-Zhandry unconditionally, without relying on the unproven Aaronson-Ambainis conjecture, against low query-depth quantum adversaries: specifically, adversaries that make up to o(\log λ) adaptive quantum queries to the random oracle.

Related papers

• Unconditional Certified Randomness without Structure [7.583159020315564]
  We obtain a certified randomness protocol in the quantum random oracle model.<n>We prove unconditional security of this protocol against adversaries making subexponentially-many adaptive quantum queries to the random oracle.
  arXiv  Detail & Related papers  (2026-08-31T17:17:49Z)
• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models.<n>These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• How much secure randomness is in a quantum state? [0.0]
  How much cryptographically-secure randomness can be extracted from a quantum state? We consider a general adversarial model that allows for an adversary who has quantum side-information about both the source and the measurement device.
  arXiv  Detail & Related papers  (2024-10-21T19:16:56Z)
• Improvements on Device Independent and Semi-Device Independent Protocols of Randomness Expansion [0.0]
  Device Independent (DI) and Semi-Device Independent (semi-DI) protocols of randomness expansion are discussed. We introduce enhanced DI and semi-DI protocols that surpass existing ones in terms of output randomness rate, security, or in some instances, both. A notable contribution is the introduction of randomness expansion protocols that recycle input randomness, significantly enhancing finite round randomness rates for DI protocols based on the CHSH inequality violation.
  arXiv  Detail & Related papers  (2023-11-22T17:03:04Z)
• Quantum Conformal Prediction for Reliable Uncertainty Quantification in Quantum Machine Learning [47.991114317813555]
  Quantum models implement implicit probabilistic predictors that produce multiple random decisions for each input through measurement shots. This paper proposes to leverage such randomness to define prediction sets for both classification and regression that provably capture the uncertainty of the model.
  arXiv  Detail & Related papers  (2023-04-06T22:05:21Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Certified Robustness of Quantum Classifiers against Adversarial Examples through Quantum Noise [68.1992787416233]
  We show that adding quantum random rotation noise can improve robustness in quantum classifiers against adversarial attacks. We derive a certified robustness bound to enable quantum classifiers to defend against adversarial examples.
  arXiv  Detail & Related papers  (2022-11-02T05:17:04Z)
• Non-Abelian braiding of graph vertices in a superconducting processor [144.97755321680464]
  Indistinguishability of particles is a fundamental principle of quantum mechanics. braiding of non-Abelian anyons causes rotations in a space of degenerate wavefunctions. We experimentally verify the fusion rules of the anyons and braid them to realize their statistics.
  arXiv  Detail & Related papers  (2022-10-19T02:28:44Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle. Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent. The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
  arXiv  Detail & Related papers  (2022-08-31T17:39:29Z)
• On Certified Randomness from Fourier Sampling or Random Circuit Sampling [0.1631115063641726]
  Certified randomness has a long history in quantum information, with many potential applications. Aaronson proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. We study certified randomness in the quantum random oracle model (QROM)
  arXiv  Detail & Related papers  (2021-11-29T18:51:50Z)
• Semi-device-independent full randomness amplification based on energy bounds [0.0]
  Quantum Bell nonlocality allows for the design of protocols that amplify the randomness of public and arbitrarily biased Santha-Vazirani sources. We prove that full randomness amplification can be achieved without requiring a complete characterization of entanglement states and measurements.
  arXiv  Detail & Related papers  (2021-08-20T10:34:01Z)
• Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
  We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" access to predict values. We show the suitability of blind unforgeability for supporting canonical constructions and reductions.
  arXiv  Detail & Related papers  (2018-03-10T05:31:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.