Binary codes of symbols, words, oracle inputs and proofs
DefinitionCertRandQROM_Supplement_proofBitscertified-randomnesscryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracle-model
Given a code of field elements:
- a symbol is written as the bits ;
- a word as the concatenation of its symbols;
- an index in binary, least significant bit first, on as many bits as has binary digits;
- an oracle input as the index followed by the symbol;
- a proof as a flag bit followed by bits: and the word for , and zeros for .
A string is parsed as the word if it is followed by the code of , and as otherwise (flag , wrong length, or not a code).
These codes are how the classical proof and the oracle queries of the protocol appear on wires and tapes in the syntax property.
Formalization Note symBits, wordBits, idxBits, domBits, proofBits are the five codes and proofOfBits the parser, which picks the word by choice; it is unique when enc is injective.
Definition code
import Mathlib
set_option autoImplicit false
namespace CertRandQROM.Supplement
variable {K : Type} {e n m : ℕ}
/-- The bit string of a symbol `s ∈ Σ = F_q^m`: the codes `enc (s_0), …, enc (s_{m−1})` of its
`m` field coordinates, concatenated (`m·e` bits). Coladangelo et al., arXiv:2608.31112
(sha256 b75095a2…), §5.2, p.23 (`Σ = F_q^m`); Definition 6.1, p.27 (classical proofs and oracle
queries are strings). -/
def symBits (enc : K → Fin e → Bool) (s : Fin m → K) : List Bool :=
(List.ofFn fun j : Fin m => List.ofFn (enc (s j))).flatten
/-- The bit string of a word `x ∈ Σ^n`: the strings of `x_0, …, x_{n−1}`, concatenated
(`n·m·e` bits). -/
def wordBits (enc : K → Fin e → Bool) (x : Fin n → Fin m → K) : List Bool :=
(List.ofFn fun i : Fin n => symBits enc (x i)).flatten
/-- The index `i ∈ [n]` (0-based) in binary, least significant bit first, on `Nat.size n` bits
(the number of binary digits of `n`, so that every `i < n` fits). -/
def idxBits (n : ℕ) (i : Fin n) : List Bool :=
List.ofFn fun j : Fin (Nat.size n) => i.val.testBit j.val
/-- The bit string of an oracle input `(i, x) ∈ [n] × Σ` (§6.2, p.28: "functions mapping
`[n] × Σ → {0,1}`"): the index in binary followed by the symbol. -/
def domBits (enc : K → Fin e → Bool) (u : Fin n × (Fin m → K)) : List Bool :=
idxBits n u.1 ++ symBits enc u.2
/-- **The bit string of a proof `π ∈ Σ^n ∪ {⊥}`** (Construction 6.2, pp.28–29): one flag bit
(`true` = `⊥`) followed by `n·m·e` bits, the word for `π = x` and zeros for `π = ⊥`. -/
def proofBits (enc : K → Fin e → Bool) : Option (Fin n → Fin m → K) → List Bool
| none => true :: List.replicate (n * m * e) false
| some x => false :: wordBits enc x
open Classical in
/-- **Parsing a proof** (Construction 6.2, Verify, step 1, p.29: "If `π = ⊥`, then output `⊥` and
halt. Otherwise, parse `π = x = (x_1, …, x_n)`"): a string `0 ++ wordBits x` is the word `x`;
every other string (flag `1`, wrong length, or not the string of a word) is `⊥` (`none`).
**Formalization Note** The word is chosen with `Classical.choose`; when `enc` is injective
(as for a `FieldPres` at `λ ≥ 2`) it is unique. -/
noncomputable def proofOfBits (enc : K → Fin e → Bool) (s : List Bool) :
Option (Fin n → Fin m → K) :=
if h : ∃ x : Fin n → Fin m → K, s = false :: wordBits enc x then some h.choose else none
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, Verify, step 1, p.29 (PDF p.31); §6.2, Biased Random Oracle, p.28 (PDF p.30)