Syntax of : a uniform polynomial-time quantum oracle algorithm with the honest output law
DefinitionCertRandQROM_Supplement_ProveSyntaxcertified-randomnesscryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracle-model
Let be a polynomial-time presentation of the fields and generators, and let be the security parameter at which the prover of Construction 6.2 is run on the inputs . The syntax property of the prover holds when there is a polynomial-time computable function on binary strings such that for all :
- is the description of a well-formed circuit over with oracle gates;
- if , then for every oracle , running with the XOR oracle of and parsing its first output wires as a proof yields exactly the output law of at :
With this says that of Construction 6.2 is a QPT algorithm making polynomially many quantum queries; with of Construction 6.4 it is the same for .
Formalization Note "QPT" is read as a polynomial-time uniform circuit family; descriptions are in unary (published parser QStateSearch.Supplement.decodeQCircuit), so the numbers of gates and of oracle calls are polynomial in . The equality of laws is exact. For only well-formedness is required.
Definition code
import Mathlib
import Definitions.Def_PvsNP
import Definitions.Def_QStateSearch_Supplement_QCircuit_Valid
import Definitions.Def_QStateSearch_Supplement_decodeQCircuit
import Definitions.Def_CertRandQROM_code
import Definitions.Def_CertRandQROM_Supplement_FieldPres
import Definitions.Def_CertRandQROM_Supplement_proofBits
import Definitions.Def_CertRandQROM_Supplement_qOracleOf
import Definitions.Def_CertRandQROM_Supplement_circOutLaw
import Definitions.Def_CertRandQROM_Supplement_honestRejProb
set_option autoImplicit false
namespace CertRandQROM.Supplement
open Classical in
/-- **The syntax property of `Prove`** (Definition 6.1, Syntax, p.27 of Coladangelo, Khurana,
Mutreja, Roberts, Slote, Tal, arXiv:2608.31112, sha256 b75095a2…: "`Prove^H(1^λ, 1^{h∞}) → π`:
This is a QPT algorithm that takes the security parameter `1^λ` and a min-entropy threshold
`1^{h∞}` as input. It makes `poly(λ, h∞)` quantum queries to a random oracle `H` …, and outputs a
classical proof `π`"), for the prover of Construction 6.2 run at the security parameter
`par a b` on the inputs `(1^a, 1^b)`:
there is a polynomial-time computable generator `g` (published `PvsNP.PolyTimeComputable`) such
that for all `a, b`, `g(1^a 0 1^b)` is the description (published parser
`QStateSearch.Supplement.decodeQCircuit`, all numbers in unary) of a well-formed circuit `C`
over `{H, S, T, X, CNOT}` with oracle gates, and, whenever `λ = par a b ≥ 2`, for every oracle
`h : [n] × Σ → {0,1}` the proof read off the first `1 + n·m·e` wires of `C` (run with the XOR
oracle `qOracleOf` of `h`, parsed by `proofOfBits`) has **exactly** the output law
`proveOut` of `Prove^h` at parameter `λ` (decoder radius `τ = ⌊(k+1)/2⌋`, `λ` trials in
step 1).
`par a b = a` is Construction 6.2; `par = leverLam c` is `Prove′` of Construction 6.4.
**Formalization Note** "QPT" is read as a polynomial-time uniform family of circuits over a
fixed finite gate set; the paper names no model. The description is in unary, so the number of
gates, hence of oracle queries, is polynomial in `a + b`. Equality of laws is exact: every
amplitude of Construction 6.2 lies in `ℤ[1/√2]`. Field elements are written through the
presentation `P`. For `par a b < 2` (construction undefined) only well-formedness is asked. -/
def ProveSyntax (F : ℕ → Type) [∀ l, Field (F l)] [∀ l, Fintype (F l)]
[∀ l, DecidableEq (F l)] (γ : ∀ l, F l) (P : FieldPres F γ) (par : ℕ → ℕ → ℕ) : Prop :=
∃ g : PvsNP.Str → PvsNP.Str, PvsNP.PolyTimeComputable g ∧
∀ a b : ℕ, ∃ C : QStateSearch.Supplement.QCircuit,
QStateSearch.Supplement.decodeQCircuit (g (unary a ++ List.replicate b true)) = some (C, []) ∧
C.Valid ∧
(2 ≤ par a b → ∀ (h : CertRandQROM.Dom F (par a b) → Bool)
(o : Option (Fin (CertRandQROM.nPar F (par a b)) → CertRandQROM.Alph F (par a b))),
(∑ s : Fin (1 + CertRandQROM.nPar F (par a b) * CertRandQROM.mPar (par a b) *
fieldBits (par a b)) → Bool,
if proofOfBits (P.enc (par a b)) (List.ofFn s) = o then
circOutLaw (qOracleOf (P.enc (par a b)) h) C _ s
else 0)
= proveOut (CertRandQROM.code F γ (par a b))
(decRadius (CertRandQROM.kPar F (par a b))) (par a b) h o)
end CertRandQROM.Supplement
Source
Coladangelo, Khurana, Mutreja, Roberts, Slote, Tal, Unconditional Certified Randomness without Structure, arXiv:2608.31112 (sha256 b75095a2…), Definition 6.1, Syntax, p.27 (PDF p.29); Construction 6.2, Prove, pp.28–29 (PDF pp.30–31)