Polynomial Commitments and Verifiable Secret Sharing
Stub. The polynomial-based mathematical toolkit specific to distributed-computing cryptography, beyond basic Shamir sharing (already covered): Lagrange's theorem viewed algorithmically, polynomials over a finite field and the finite-field FFT, verifiable information dispersal, polynomial secret sharing against passive and crash adversaries, the BGW88 verifiable secret sharing (VSS) protocol, Chaum's Dining Cryptographers protocol (and the additivity property of polynomial secret sharing it relies on), bilinear accumulators from polynomial commitments, and range proofs from polynomial commitments.
secret-sharing-multi-party-and-computational-differential-privacy already covers basic Shamir secret sharing; this note covers the deeper polynomial machinery distributed-computing research builds on top of it. Covers Lagrange’s theorem viewed through an algorithmic lens (reconstruction as polynomial interpolation), polynomials over a finite field and the finite-field FFT (evaluating/interpolating a degree- polynomial at many points efficiently — the computational engine behind fast Reed-Solomon-style erasure coding and secret sharing at scale), and Verifiable Information Dispersal as an application. Polynomial secret sharing against a passive adversary generalizes basic Shamir sharing to a distributed-computing setting with multiple communicating parties, extended to a crash adversary, and the BGW88 protocol adds verifiability: parties can detect a dealer cheating, not just tolerate a threshold of missing shares. Chaum’s Dining Cryptographers protocol is covered as a striking application of the additivity of polynomial secret sharing (sharing additively combine, letting parties jointly compute a sum without revealing individual inputs) to anonymous communication. Closes with two cryptographic-commitment applications central to modern SNARK/blockchain systems: bilinear accumulators from polynomial commitments (compress a whole polynomial into a short commitment, with efficient evaluation proofs) and range proofs from polynomial commitments — see pairing-based-cryptography for the underlying pairings and non-interactive-zero-knowledge-and-snarks for the general succinct-proof landscape these feed into.
Outline (TODO — flesh out each)
- Lagrange’s theorem through the algorithmic lens
- Polynomials over a finite field — a lightweight introduction
- The Fast Fourier Transform over finite fields
- Verifiable Information Dispersal
- Polynomial secret sharing against a passive adversary
- Polynomial secret sharing against a crash adversary
- The BGW88 protocol for Verifiable Secret Sharing (VSS)
- Chaum’s Dining Cryptographers and the additivity of polynomial secret sharing
- Bilinear accumulators from polynomial commitments
- Range proofs from polynomial commitments