Display (12) — when and
ProvedRoundOptVSS.display_12_det_ne_zeroinformation-theoretic-cryptographymultiparty-computationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1verifiable-secret-sharing
Display (12) (proof of Lemma 8.2). Let be fields, algebraic over of degree , and with . The polynomial is monic of degree , so it cannot vanish at :
and therefore for every right-hand side the system has exactly one solution (in the paper, ).
This is why the compiler needs of algebraic degree greater than : the privacy coupling of Lemma 8.2 and the hidden-point argument of Lemma B.1 both solve such a system.
Differences from the source:
- generalization: the right-hand side −b_∆ → every right-hand side v ∈ 𝔼^r; reason: the printed case is v = −b_∆
- encoding: λ of algebraic degree L over 𝔽 → IsIntegral 𝔽 lam with (minpoly 𝔽 lam).natDegree = L; reason: the degree of λ is the degree of its minimal polynomial
Preamble
import Mathlib
Formal statement
namespace RoundOptVSS
/-- **Display (12)**, proof of Lemma 8.2, p.41 of Liu-Zhang, Masserova, *Round-Optimal
Statistical Verifiable Secret Sharing with Polynomial Complexity*, manuscript (STOC 2027
submission, sha256 3a45d95d…): for `A ∈ 𝔽^{r×r}` and `λ ∈ 𝔼` of algebraic degree `L > r` over
`𝔽`, the polynomial `det(Z I_r + A) ∈ 𝔽[Z]` is monic of degree `r < L`, so it does not vanish at
`λ`; thus `(λ I_r + A) u = v` has a unique solution `u ∈ 𝔼^r` for every right-hand side (in
particular `v = −b∆`).
**Formalization Note.** `λ` is `lam`; "algebraic degree `L`" is `IsIntegral 𝔽 lam` with
`(minpoly 𝔽 lam).natDegree = L`; `A` acts on `𝔼^r` through `algebraMap 𝔽 𝔼`. -/
theorem display_12_det_ne_zero {𝔽 𝔼 : Type} [Field 𝔽] [Field 𝔼] [Algebra 𝔽 𝔼]
(lam : 𝔼) (L : ℕ) (hlam : IsIntegral 𝔽 lam) (hL : (minpoly 𝔽 lam).natDegree = L)
{r : ℕ} (A : Matrix (Fin r) (Fin r) 𝔽) (hr : r < L) :
(lam • (1 : Matrix (Fin r) (Fin r) 𝔼) + A.map (algebraMap 𝔽 𝔼)).det ≠ 0 ∧
∀ v : Fin r → 𝔼, ∃! u : Fin r → 𝔼,
(lam • (1 : Matrix (Fin r) (Fin r) 𝔼) + A.map (algebraMap 𝔽 𝔼)).mulVec u = v := by sorry
end RoundOptVSS
Source
Liu-Zhang, Masserova, Round-Optimal Statistical Verifiable Secret Sharing with Polynomial Complexity, manuscript (2026; STOC 2027 submission, sha256 3a45d95d…), display (12) and the following sentences, proof of Lemma 8.2 (p.41)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.