Polynomial-time presentation of the fields and generators
DefinitionCertRandQROM_Supplement_FieldPrescertified-randomnesscryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracle-model
A polynomial-time presentation of a family of fields with generators consists of
- for every a bijection , ;
- polynomial-time computable functions on binary strings that, given followed by the codes of and , return the codes of and of ;
- a polynomial-time computable function that maps to the code of .
The paper speaks of polynomial-time quantum and classical algorithms computing with elements of , , and with "an arbitrary generator" , without saying how they are written down. A presentation is exactly the data a uniform algorithm needs; the syntax property of the protocol is stated for every presentation.
Formalization Note Polynomial time is the published PvsNP.PolyTimeComputable (Mathlib's TM2ComputableInPolyTime). fieldBits λ is and unary a is . Nothing is required for . Because , the remaining field operations are computable in polynomial time from the two tables.
Definition code
import Mathlib
import Definitions.Def_PvsNP
set_option autoImplicit false
namespace CertRandQROM.Supplement
/-- The number of bits `e(λ) = log₂ q(λ) = 2⌊log₂ λ⌋` of an element of `F_{q(λ)}`,
`q(λ) = 2^{2⌊log λ⌋}` (§5.2, p.23 of Coladangelo, Khurana, Mutreja, Roberts, Slote, Tal,
*Unconditional Certified Randomness without Structure*, arXiv:2608.31112, sha256 b75095a2…). -/
def fieldBits (l : ℕ) : ℕ := 2 * Nat.log 2 l
/-- The unary numeral `1^a 0` (`true^a false`), the way the inputs `1^λ`, `1^{h∞}` of
Definition 6.1 (p.27) are written on a binary input tape. -/
def unary (a : ℕ) : PvsNP.Str := List.replicate a true ++ [false]
/-- **A polynomial-time presentation of the field family `F_{q(λ)}` and of the generators
`γ(λ)`** of §5.2 (p.23 of arXiv:2608.31112, sha256 b75095a2…): for every `λ ≥ 2` a bijection
`enc λ` of `F λ` with the bit strings of length `e(λ) = 2⌊log₂ λ⌋`, such that addition and
multiplication of `F λ` on codes (given `1^λ 0`) and the code of `γ(λ)` (from `1^λ 0`) are
computable in polynomial time (the published `PvsNP.PolyTimeComputable`, Mathlib's
`TM2ComputableInPolyTime`).
**Formalization Note** The paper writes "QPT" and "polynomial-time" algorithms over `F_q`
(Definition 6.1, Syntax, p.27) without fixing how field elements are written, and takes `γ(λ)`
to be "an arbitrary generator of `F_q^*`". A uniform algorithm needs both in computable form;
this structure is that datum. Statements about the syntax property quantify over **every**
such presentation. Nothing is required for `λ < 2`, where the construction is undefined. Since
`q(λ) ≤ λ²`, every other field operation (inverses, the absolute trace, the zero and one
elements) is computable in polynomial time from the two tables. -/
structure FieldPres (F : ℕ → Type) [∀ l, Field (F l)] (γ : ∀ l, F l) where
/-- The code of a field element: `e(λ)` bits. -/
enc : ∀ l, F l → (Fin (fieldBits l) → Bool)
/-- Every bit string of length `e(λ)` is the code of exactly one element. -/
enc_bij : ∀ l, 2 ≤ l → Function.Bijective (enc l)
/-- Addition on codes. -/
add : PvsNP.Str → PvsNP.Str
add_polytime : PvsNP.PolyTimeComputable add
add_spec : ∀ l, 2 ≤ l → ∀ a b : F l,
add (unary l ++ List.ofFn (enc l a) ++ List.ofFn (enc l b)) = List.ofFn (enc l (a + b))
/-- Multiplication on codes. -/
mul : PvsNP.Str → PvsNP.Str
mul_polytime : PvsNP.PolyTimeComputable mul
mul_spec : ∀ l, 2 ≤ l → ∀ a b : F l,
mul (unary l ++ List.ofFn (enc l a) ++ List.ofFn (enc l b)) = List.ofFn (enc l (a * b))
/-- The code of the generator `γ(λ)`. -/
gen : PvsNP.Str → PvsNP.Str
gen_polytime : PvsNP.PolyTimeComputable gen
gen_spec : ∀ l, 2 ≤ l → gen (unary l) = List.ofFn (enc l (γ l))
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); §5.2, p.23 (PDF p.25)