Syntax of : a deterministic polynomial-time oracle machine computing
DefinitionCertRandQROM_Supplement_VerifySyntaxFor a code and an oracle , the verifier of Construction 6.2 is
Let be a polynomial-time presentation and the security parameter used on inputs . The syntax property of the verifier holds when there is one deterministic polynomial-time oracle machine such that for all with , every oracle and every binary string ,
where is parsed as a word of or as (any unparseable string is ), and queries through the codes of oracle inputs.
With this is the syntax of in Construction 6.2; with it is that of in Construction 6.4.
Formalization Note verifyOut is on (test: the published CertRandQROM.IsCorrect). The machine is the published BQPNotInIP.OracleSep.OracleMachine: a polynomial-time step function and a polynomial clock in the input length that bounds the number of steps, the number of oracle queries and the size of configurations.
import Mathlib
import Definitions.Def_PvsNP
import Definitions.Def_BQPNotInIP_OracleSep_OracleMachine
import Definitions.Def_CertRandQROM_code
import Definitions.Def_CertRandQROM_IsCorrect
import Definitions.Def_CertRandQROM_Supplement_FieldPres
import Definitions.Def_CertRandQROM_Supplement_proofBits
import Definitions.Def_CertRandQROM_Supplement_qOracleOf
set_option autoImplicit false
namespace CertRandQROM.Supplement
open Classical in
/-- **`Verify^h` of Construction 6.2** (p.29 of Coladangelo et al., arXiv:2608.31112, sha256
b75095a2…): "1. If `π = ⊥`, then output `⊥` and halt. Otherwise, parse `π = x`. 2. If `x ∈ C`,
and `H_i(x_i) = 0` for all `i ∈ [n]`, then output `x`. Otherwise, output `⊥`" (`none` = `⊥`;
the test is the published `CertRandQROM.IsCorrect`). -/
noncomputable def verifyOut {n : ℕ} {S : Type} (C : Finset (Fin n → S)) (h : Fin n × S → Bool) :
Option (Fin n → S) → Option (Fin n → S)
| none => none
| some x => if CertRandQROM.IsCorrect C h x then some x else none
/-- **The syntax property of `Verify`** (Definition 6.1, Syntax, p.27 of arXiv:2608.31112, sha256
b75095a2…: "`Verify^H(1^λ, 1^{h∞}, π) → x`: This is a deterministic classical polynomial-time
algorithm that takes `1^λ`, `1^{h∞}`, and a proof `π` as input. It makes `poly(λ, h∞)` queries to
the random oracle `H`, and outputs either a string `x` …, or `⊥`"), for the verifier of
Construction 6.2 run at the security parameter `par a b` on the inputs `(1^a, 1^b, π)`:
there is one deterministic polynomial-time oracle machine `M` (published
`BQPNotInIP.OracleSep.OracleMachine`: a polynomial-time step function and a polynomial clock
bounding the number of steps, the number of queries and the configuration size) such that for
all `a, b` with `λ = par a b ≥ 2`, every oracle `h : [n] × Σ → {0,1}` and every string `π`,
`M` with the oracle `strOracleOf h` on input `1^a 0 1^b 0 π` outputs the string
(`proofBits`) of `Verify^h(π)`, where `π` is parsed by `proofOfBits` (an unparseable string is
`⊥`).
`par a b = a` is Construction 6.2; `par = leverLam c` is `Verify′` of Construction 6.4.
**Formalization Note** The paper names no machine model; the clock is a polynomial in the
input length `a + b + 2 + |π|`, so the number of queries is `poly(λ, h∞)` for proofs of the
honest length. Field elements are written through the presentation `P`. -/
def VerifySyntax (F : ℕ → Type) [∀ l, Field (F l)] [∀ l, Fintype (F l)]
[∀ l, DecidableEq (F l)] (γ : ∀ l, F l) (P : FieldPres F γ) (par : ℕ → ℕ → ℕ) : Prop :=
∃ M : BQPNotInIP.OracleSep.OracleMachine,
∀ a b : ℕ, 2 ≤ par a b → ∀ (h : CertRandQROM.Dom F (par a b) → Bool) (π : PvsNP.Str),
M.run (strOracleOf (P.enc (par a b)) h) (unary a ++ unary b ++ π) =
proofBits (P.enc (par a b))
(verifyOut (CertRandQROM.code F γ (par a b)) h (proofOfBits (P.enc (par a b)) π))
end CertRandQROM.Supplement