Output law of the honest prover of Construction 6.2 and its rejection probability
DefinitionCertRandQROM_Supplement_honestRejProbcertified-randomnesscryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracle-model
Fix a code (), a decoding radius , a trial count and an oracle ; write .
- Step 1. For each the prover tries up to times to prepare ; each trial succeeds with probability . If some coordinate fails all its trials the prover outputs . The probability that it does not abort is
- Steps 2–5. With and , the prover forms and applies , then , then , obtaining a state .
- Step 6. It measures the second register and outputs the outcome :
The rejection probability is , where is correct when and for all . At security parameter the construction uses , and .
This is the quantity whose average over the biased oracle the correctness property bounds.
Formalization Note zeroSet is , stepOneSucc is , phiVec, psiVec are the amplitude functions of , , finalState is as a function of the two registers, proveOut is the law on (none ), rejProb the rejection probability and honestRejProb F γ λ h its value for the parameters of Construction 6.2 at . The trial outcomes of step 1 are integrated out exactly: given success the state is whatever the history. When the law is with probability .
Definition code
import Mathlib
import Definitions.Def_CertRandQROM_code
import Definitions.Def_CertRandQROM_IsCorrect
import Definitions.Def_CertRandQROM_Supplement_decodeDual
import Definitions.Def_CertRandQROM_Supplement_qft
set_option autoImplicit false
namespace CertRandQROM.Supplement
variable {K : Type} [Field K] [Fintype K] [DecidableEq K] {n m : ℕ}
open Classical in
/-- `T_i^{H_i} = {e_i ∈ Σ : H_i(e_i) = 0}` (proof of Theorem 6.6, p.31 of Coladangelo et al.,
arXiv:2608.31112, sha256 b75095a2…), for an oracle `h : [n] × Σ → {0,1}` (`false` = `0`). -/
noncomputable def zeroSet (h : Fin n × (Fin m → K) → Bool) (i : Fin n) : Finset (Fin m → K) :=
Finset.univ.filter fun e => h (i, e) = false
/-- **Step 1 of `Prove^h` succeeds** (Construction 6.2, step 1, pp.28–29): for each `i ∈ [n]`,
independently, up to `L` trials, each preparing the uniform superposition over `Σ`, evaluating
`H_i` coherently and measuring; a trial succeeds (leaving `|φ_i⟩`) with probability `|T_i|/|Σ|`.
The probability that no coordinate exhausts its `L` trials is
`Π_i (1 − (1 − |T_i|/|Σ|)^L)`; Construction 6.2 uses `L = λ`. -/
noncomputable def stepOneSucc (L : ℕ) (h : Fin n × (Fin m → K) → Bool) : ℝ :=
∏ i, (1 - (1 - ((zeroSet h i).card : ℝ) / (Fintype.card (Fin m → K) : ℝ)) ^ L)
/-- `|φ⟩ = |φ_1⟩ ⊗ ⋯ ⊗ |φ_n⟩`, `|φ_i⟩ = |T_i|^{−1/2} Σ_{e_i ∈ T_i} |e_i⟩` (Construction 6.2,
steps 1–2, pp.28–29). -/
noncomputable def phiVec (h : Fin n × (Fin m → K) → Bool) : (Fin n → Fin m → K) → ℂ :=
fun e => ∏ i, if h (i, e i) = false then ((Real.sqrt (zeroSet h i).card)⁻¹ : ℂ) else 0
open Classical in
/-- `|ψ⟩ = |C|^{−1/2} Σ_{x ∈ C} |x⟩` (Construction 6.2, step 3, p.29). -/
noncomputable def psiVec (C : Finset (Fin n → Fin m → K)) : (Fin n → Fin m → K) → ℂ :=
fun x => if x ∈ C then ((Real.sqrt C.card)⁻¹ : ℂ) else 0
/-- **The final state of `Prove^h` before the measurement** (Construction 6.2, steps 4–5, p.29),
given that step 1 succeeded: `|η⟩ = QFT^{⊗n}|ψ⟩ ⊗ QFT^{⊗n}|φ⟩`, then
`U_add |x⟩|e⟩ = |x⟩|x + e⟩`, then `U_decode |x⟩|z⟩ = |x − Decode_{C⊥}(z)⟩|z⟩`, then
`I ⊗ (QFT_Σ^{−1})^{⊗n}`. As a function of the two registers `(x′, w)`:
`final(x′, w) = (QFT^{−1 ⊗n}_z ↦ η(x′ + D(z), z − x′ − D(z)))(w)` with `D = Decode_{C⊥}` at
radius `τ`. -/
noncomputable def finalState (C : Finset (Fin n → Fin m → K)) (τ : ℕ)
(h : Fin n × (Fin m → K) → Bool) (x' w : Fin n → Fin m → K) : ℂ :=
qftInv (fun z => qft (psiVec C) (x' + decodeDual C τ z) *
qft (phiVec h) (z - (x' + decodeDual C τ z))) w
/-- **The output law of `Prove^h`** (Construction 6.2, pp.28–29) on `Option (Σ^n)`
(`none` = `π = ⊥`): abort with probability `1 − stepOneSucc`; otherwise measure the second
register of `finalState` in the computational basis (step 6), so
`Pr[π = w] = stepOneSucc · Σ_{x′} |final(x′, w)|²`. -/
noncomputable def proveOut (C : Finset (Fin n → Fin m → K)) (τ L : ℕ)
(h : Fin n × (Fin m → K) → Bool) : Option (Fin n → Fin m → K) → ℝ
| none => 1 - stepOneSucc L h
| some w => stepOneSucc L h * ∑ x', Complex.normSq (finalState C τ h x' w)
open Classical in
/-- `Pr[Verify^h(Prove^h) = ⊥ | H = h]` (Definition 6.1, Correctness, p.28, for Construction 6.2,
p.29): `Verify` rejects `π = ⊥` and every `x` that is not correct (`x ∉ C` or `H_i(x_i) = 1` for
some `i`; the published `CertRandQROM.IsCorrect`). -/
noncomputable def rejProb (C : Finset (Fin n → Fin m → K)) (τ L : ℕ)
(h : Fin n × (Fin m → K) → Bool) : ℝ :=
proveOut C τ L h none +
∑ w, if CertRandQROM.IsCorrect C h w then 0 else proveOut C τ L h (some w)
/-- **Rejection probability of the honest prover of Construction 6.2 at security parameter `λ`**
for a fixed oracle `h : [n] × Σ → {0,1}` (Coladangelo, Khurana, Mutreja, Roberts, Slote, Tal,
arXiv:2608.31112, sha256 b75095a2…, Construction 6.2 pp.28–29, Definition 6.1 p.28): the code is
`C_λ = CertRandQROM.code F γ λ` (§5.2), `Decode_{C⊥}` has radius `τ = ⌊(k(λ) + 1)/2⌋` (p.25),
and step 1 makes at most `λ` trials per coordinate.
**Formalization Note** The prover's internal randomness (the trial outcomes of step 1 and the
final measurement) is integrated out exactly: given success of step 1 the state is `|φ⟩`
whatever the trial history. The input `1^{h∞}` is ignored by `Prove` and `Verify`, so the
quantity does not depend on it. -/
noncomputable def honestRejProb (F : ℕ → Type) [∀ l, Field (F l)] [∀ l, Fintype (F l)]
[∀ l, DecidableEq (F l)] (γ : ∀ l, F l) (l : ℕ) (h : CertRandQROM.Dom F l → Bool) : ℝ :=
rejProb (CertRandQROM.code F γ l) (decRadius (CertRandQROM.kPar F l)) l h
end CertRandQROM.Supplement
Source
Coladangelo, Khurana, Mutreja, Roberts, Slote, Tal, Unconditional Certified Randomness without Structure, arXiv:2608.31112 (sha256 b75095a2…), Construction 6.2, pp.28–29 (PDF pp.30–31); Definition 6.1, Correctness, p.28 (PDF p.30); T_i^{H_i}, p.31 (PDF p.33)