{"id":"arxiv/2608.24832","url":"https://arxiv.org/abs/2608.24832","tags":["quant-ph","cs.CR"],"score":0,"title":"Certified Randomness without Structure Against Shallow-Query Adversaries","domain":"quant-ph","source":"arxiv","authors":["Dakshita Khurana","Bhaskar Roberts","Avishay Tal"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}