Threshold Cryptography — Signatures, Decryption, and DKG
Stub. Beyond basic Shamir secret sharing (already covered): threshold signatures (a generic framework and the concrete, aggregation-friendly BLS threshold scheme, with accountability-vs-privacy tradeoffs), threshold decryption schemes (generic, insecure, and secure CDH-based constructions), distributed key generation (DKG — producing a shared key with no single party ever holding it whole), monotone access structures and linear secret sharing as generalizations beyond plain t-out-of-n thresholds, and gap security for threshold schemes.
Corresponds to Chapter 22 (Shamir’s secret sharing scheme itself is already covered in secret-sharing-multi-party-and-computational-differential-privacy). Threshold signatures let any out of parties jointly produce a valid signature with no single party able to sign alone; the BLS threshold scheme (pairing-based-cryptography‘s aggregation property is exactly what makes combining partial signatures cheap) is the concrete leading construction, with accountability (identifying which parties actually signed) in tension with the privacy of not revealing that. Threshold decryption is the dual primitive for decryption rather than signing, worked through a naive insecure construction first to motivate the secure, CDH-based fix. Distributed key generation (DKG) solves the bootstrapping problem both threshold primitives need: generating a shared key where no single party (not even a dealer) ever learns the whole secret. Monotone access structures and linear secret sharing generalize beyond simple thresholds to arbitrary authorized-coalition structures, and gap security captures a security notion specific to the threshold setting, closing with a randomness beacon as an application.
Outline (TODO — flesh out each)
- Threshold signatures — a generic scheme
- BLS threshold signing; threshold signature security
- Accountability versus privacy; BLS accountable threshold signatures
- Threshold decryption schemes — generic, insecure, and secure (CDH) constructions
- Distributed key generation — defining the problem; a simple DKG protocol
- Beyond threshold: monotone access structures
- Linear secret sharing schemes and monotone span programs
- A signature scheme from linear secret sharing
- Gap security for threshold signature and decryption schemes
- Fun application: a randomness beacon