The majority construction of One Compatible Hint PIR (§7.2–§7.3)
DefinitionITPIRPreproc_MatchVec_Supplement_MajorityThis file defines the objects of the majority construction of Dujmovic, Lai and Wichs (§7.2–§7.3).
Layout and parameters. Let . Database rows are , each identified with its binary label in , and columns are labelled by sign vectors , so a database is with entries and a position is a pair . For an integer construction parameter set
The label length is . For sign vectors, is the integer inner product.
Seeds. A seed is with . It determines the row vectors , . The seed is good when for all .
Keys. The key space is . The rows of a key are its blocks. The selected set is . Since is odd there are no ties. The compatible keys are . The conditional sampler for replaces each block by whenever .
Query. draws independent uniform coins:
- a retain/flip coin for every block;
- a label of bits for every coordinate of every block;
- a fresh uniform key.
If two labels collide within a block, the query returns the fresh key with . Otherwise every retained block is kept. In every flipped block , put ; among the coordinates with , the with the smallest labels are negated, and the query returns .
Answer. The reported positions are
enumerates in row order, and within a row in lexicographic order of the column labels. It aborts if there are more than reported positions, and otherwise returns the list of the bits in that order.
Hint and Decode. . returns in three cases: , the answer aborts, or some position of is not reported. Otherwise it returns .
These objects are the majority primitive whose properties are Claims 7.4.1–7.4.3 and which the full scheme of Theorem 7.1 runs with a random seed.
Formalization Note Signs are the units . Row labels use the published binary-digit map colVec. is Nat.clog 2 (d^4). The lexicographic order puts coordinate first and before . Query is a probability mass function on (key, ), with written true. Its fresh key is drawn with the other coins and used only on a collision, which gives the same output law. When labels are distinct, "the eligible coordinates with the smallest labels" are the eligible coordinates with fewer than eligible coordinates of smaller label. Decode looks up each position of in the pairing of the enumeration of with .
import Mathlib
import Definitions.Def_ITPIRPreproc_MatchVec_BasicKeys
import Definitions.Def_ITPIRPreproc_MatchVec_OneCompatibleHint
open scoped ENNReal
open Matrix
namespace ITPIRPreproc.MatchVec.Supplement
/-!
# The majority construction of One Compatible Hint PIR (§7.2–§7.3, printed pp.24–27)
"We use the padded matrix layout of Section 5.2, so n = m² and h = log₂ m, except that columns
are now labeled by sign vectors b ∈ {−1,+1}^h. All matrix products in this section are over the
integers, and sgn acts coordinatewise. Fix an integer construction parameter H ≥ h + 64, and set
d = 2H^14 + 1, ∆ = H^5, µ = H^{−6}. (19)"
Conventions.
* `m = 2^h`; rows are `a ∈ Fin (2^h)`, identified with their binary label `colVec a ∈ F₂^h`
(published in `Def_ITPIRPreproc_MatchVec_BasicKeys`: digit `t` is bit `t` of `a`).
* Signs are units of `ℤ` (`ℤˣ = {−1, +1}`); a sign vector of length `k` is `Fin k → ℤˣ`, and
`⟨x, y⟩ = Σ_k x_k y_k ∈ ℤ`.
* A position is `(a, b) ∈ [m] × {−1,+1}^h` (`MPos h`); a database is `D : [m] → {−1,+1}^h → Bool`
(`D[a, b]`, columns labelled by sign vectors).
* Probabilities are uniform laws on finite sets, written with cardinalities or with `avgOver`
(published in `Def_ITPIRPreproc_MatchVec_OneCompatibleHint`); the randomized `Query` is a `PMF`.
-/
/-- The dimension `d = 2H^14 + 1` of (19). -/
def dim (H : ℕ) : ℕ := 2 * H ^ 14 + 1
/-- The shift `∆ = H^5` of (19). -/
def shift (H : ℕ) : ℤ := (H : ℤ) ^ 5
/-- The near-orthogonality parameter `µ = H^{−6}` of (19). -/
noncomputable def mu (H : ℕ) : ℝ := ((H : ℝ) ^ 6)⁻¹
/-- The label length `H² + ⌈4 log₂ d⌉` of Query step (a); `⌈4 log₂ d⌉ = ⌈log₂ d⁴⌉ = Nat.clog 2 (d⁴)`. -/
def labelBits (H : ℕ) : ℕ := H ^ 2 + Nat.clog 2 (dim H ^ 4)
/-- The integer inner product `⟨x, y⟩ = Σ_k x_k y_k` of two sign vectors. -/
def ip {k : ℕ} (x y : Fin k → ℤˣ) : ℤ := ∑ j, (x j : ℤ) * (y j : ℤ)
/-- A seed `σ = ((g_k, τ_k))_{k ∈ [d]}` with `(g_k, τ_k) ∈ F₂^h × F₂`. -/
abbrev Seed (h H : ℕ) := Fin (dim H) → (Fin h → ZMod 2) × ZMod 2
/-- The row vector (20): `v_{a,k} = (−1)^{⟨a, g_k⟩₂ + τ_k}`, `a` read as its binary label. -/
def rowVec {h H : ℕ} (σ : Seed h H) (a : Fin (2 ^ h)) : Fin (dim H) → ℤˣ :=
fun k => if colVec a ⬝ᵥ (σ k).1 + (σ k).2 = 0 then 1 else -1
/-- The seed is **good** (21): `|⟨v_a, v_{a′}⟩| ≤ µ d` for all rows `a ≠ a′`. -/
def IsGood {h H : ℕ} (σ : Seed h H) : Prop :=
∀ a a' : Fin (2 ^ h), a ≠ a' →
|((ip (rowVec σ a) (rowVec σ a') : ℤ) : ℝ)| ≤ mu H * (dim H : ℝ)
noncomputable instance {h H : ℕ} (σ : Seed h H) : Decidable (IsGood σ) := by
unfold IsGood; infer_instance
/-- The key space `R = {−1,+1}^{h×d}`; `R t` is block `t` (the row `r_t^T`). -/
abbrev Key (h H : ℕ) := Fin h → Fin (dim H) → ℤˣ
/-- A position `(a, b) ∈ [m] × {−1,+1}^h`. -/
abbrev MPos (h : ℕ) := Fin (2 ^ h) × (Fin h → ℤˣ)
/-- A database `D ∈ {0,1}^{m×m}`, columns labelled by sign vectors. -/
abbrev MDB (h : ℕ) := Fin (2 ^ h) → (Fin h → ℤˣ) → Bool
/-- The column `sgn(R v_a) ∈ {−1,+1}^h` selected by key `R` in row `a` (`d` is odd, so
`⟨r_t, v_a⟩ ≠ 0` and the sign is `+1` exactly when the inner product is positive). -/
def selCol {h H : ℕ} (σ : Seed h H) (R : Key h H) (a : Fin (2 ^ h)) : Fin h → ℤˣ :=
fun t => if 0 < ip (R t) (rowVec σ a) then 1 else -1
/-- `i ∈ S(R)` for the selected set (22) `S(R) = {(a, sgn(R v_a)) : a ∈ [m]}`. -/
def majSel {h H : ℕ} (σ : Seed h H) (R : Key h H) (i : MPos h) : Prop :=
selCol σ R i.1 = i.2
instance {h H : ℕ} (σ : Seed h H) (R : Key h H) (i : MPos h) : Decidable (majSel σ R i) := by
unfold majSel; infer_instance
/-- The compatible keys `R_i = {R ∈ R : i ∈ S(R)}`. -/
def majCompat {h H : ℕ} (σ : Seed h H) (i : MPos h) : Finset (Key h H) :=
Finset.univ.filter fun R => majSel σ R i
/-- The conditional sampler for `R_i`, `i = (a⋆, b⋆)`: given independent uniform blocks
`r_t ∈ {−1,+1}^d`, replace `r_t` by `−r_t` whenever `sgn⟨r_t, v_{a⋆}⟩ ≠ b⋆_t`. -/
def majSampler {h H : ℕ} (σ : Seed h H) (i : MPos h) (R₀ : Key h H) : Key h H :=
fun t => if Int.sign (ip (R₀ t) (rowVec σ i.1)) = ((i.2 t : ℤˣ) : ℤ) then R₀ t else -R₀ t
/-- The coins of `Query`: per block a flip coin (`true` = flipped), per coordinate of each block a
label of `H² + ⌈4 log₂ d⌉` bits, and a fresh key used only in the collision branch. -/
abbrev Coins (h H : ℕ) :=
(Fin h → Bool) × (Fin h → Fin (dim H) → Fin (2 ^ labelBits H)) × Key h H
/-- Step (b): two labels collide within some block. -/
def Collision {h H : ℕ} (c : Coins h H) : Prop :=
∃ t : Fin h, ∃ k k' : Fin (dim H), k ≠ k' ∧ c.2.1 t k = c.2.1 t k'
instance {h H : ℕ} (c : Coins h H) : Decidable (Collision c) := by
unfold Collision; infer_instance
/-- Step (c) for a flipped block `t`: with `F_t = b⋆_t⟨r_t, v_{a⋆}⟩`, among the coordinates `k`
with `r_{t,k} = b⋆_t v_{a⋆,k}` negate the `F_t` with the smallest labels (labels are distinct
when this step runs). -/
def flipBlock {h H : ℕ} (σ : Seed h H) (i : MPos h) (R : Key h H)
(lab : Fin h → Fin (dim H) → Fin (2 ^ labelBits H)) (t : Fin h) : Fin (dim H) → ℤˣ :=
let v := rowVec σ i.1
let F := (((i.2 t : ℤˣ) : ℤ) * ip (R t) v).toNat
fun k =>
if R t k = i.2 t * v k ∧
(Finset.univ.filter fun k' => R t k' = i.2 t * v k' ∧ lab t k' < lab t k).card < F
then -R t k else R t k
/-- The output of `Query(i, R)` on coins `c`: `(fresh key, fail)` on a label collision, otherwise
`(Q, ok)` where `Q` keeps the retained blocks and replaces each flipped block by `flipBlock`.
(`true` is `ok`, `false` is `fail`.) -/
def queryMap {h H : ℕ} (σ : Seed h H) (i : MPos h) (R : Key h H) (c : Coins h H) :
Key h H × Bool :=
if Collision c then (c.2.2, false)
else (fun t => if c.1 t then flipBlock σ i R c.2.1 t else R t, true)
/-- `Query(i, R)`: the law of `(Q, u)` under uniform coins (steps (a)–(d)). -/
noncomputable def majQuery {h H : ℕ} (σ : Seed h H) (i : MPos h) (R : Key h H) :
PMF (Key h H × Bool) :=
(PMF.uniformOfFintype (Coins h H)).map (queryMap σ i R)
/-- `(a, b) ∈ S⁺(Q)` (23): `b_t ⟨q_t, v_a⟩ ≥ −∆` for all `t ∈ [h]`. -/
def Reported {h H : ℕ} (σ : Seed h H) (Q : Key h H) (p : MPos h) : Prop :=
∀ t : Fin h, -shift H ≤ ((p.2 t : ℤˣ) : ℤ) * ip (Q t) (rowVec σ p.1)
instance {h H : ℕ} (σ : Seed h H) (Q : Key h H) (p : MPos h) : Decidable (Reported σ Q p) := by
unfold Reported; infer_instance
/-- All column labels `{−1,+1}^h` in lexicographic order: coordinate `0` first, `−1 < +1`. -/
def colList (h : ℕ) : List (Fin h → ℤˣ) :=
(List.finRange (2 ^ h)).map fun c t => if c.val.testBit (h - 1 - t.val) then 1 else -1
/-- `S⁺(Q)` enumerated in row order and, within a row, in lexicographic order of the column
labels. -/
def enumReported {h H : ℕ} (σ : Seed h H) (Q : Key h H) : List (MPos h) :=
(List.finRange (2 ^ h)).flatMap fun a =>
((colList h).filter fun b => decide (Reported σ Q (a, b))).map fun b => (a, b)
/-- `Answer(D, Q)`: `none` (= abort) if `|S⁺(Q)| > 8m`, else `some β` with
`β = (D[a, b])_{(a,b) ∈ S⁺(Q)}` in the enumeration order. -/
def majAnswer {h H : ℕ} (σ : Seed h H) (D : MDB h) (Q : Key h H) : Option (List Bool) :=
let L := enumReported σ Q
if 8 * 2 ^ h < L.length then none else some (L.map fun p => D p.1 p.2)
/-- The XOR of a list of bits. -/
def xorList (l : List Bool) : Bool := l.foldr Bool.xor false
/-- `Hint(D, R) = ⊕_{a ∈ [m]} D[a, sgn(R v_a)]`. -/
def majHint {h H : ℕ} (σ : Seed h H) (D : MDB h) (R : Key h H) : Bool :=
xorList ((List.finRange (2 ^ h)).map fun a => D a (selCol σ R a))
/-- `Decode(i, R, z, Q, u, ans)`: `⊥` (`none`) if `u = fail` or `ans = abort`; otherwise
associate the answer bits with the positions of `S⁺(Q)` in the server's order; `⊥` if some
position of `S(R) ∖ {i}` is absent; else `z ⊕ ⊕_{(a,b) ∈ S(R)∖{i}} β_{a,b}` (24). -/
def majDecode {h H : ℕ} (σ : Seed h H) (i : MPos h) (R : Key h H) (z : Bool) (Q : Key h H)
(u : Bool) (ans : Option (List Bool)) : Option Bool :=
match u, ans with
| true, some β =>
let L := enumReported σ Q
let others : List (MPos h) := (List.finRange (2 ^ h)).filterMap fun a =>
if ((a, selCol σ R a) : MPos h) = i then none else some (a, selCol σ R a)
let look := others.map fun p => List.lookup p (L.zip β)
if look.all Option.isSome then
some (Bool.xor z (xorList (look.map fun o => o.getD false)))
else none
| _, _ => none
/-- The client's output `Decode(i, R, Hint(D, R), Q, u, Answer(D, Q))` on the query outcome
`p = (Q, u)`. -/
def majOutcome {h H : ℕ} (σ : Seed h H) (D : MDB h) (i : MPos h) (R : Key h H)
(p : Key h H × Bool) : Option Bool :=
majDecode σ i R (majHint σ D R) p.1 p.2 (majAnswer σ D p.1)
end ITPIRPreproc.MatchVec.Supplement