In the paper-slip (Zettelchen) voting protocol, what role does the random starting number play, and why is "additive secret sharing" the right framing?
The starting voter picks a large random number to hide their own vote in the running total. Each subsequent voter adds their vote (0 or 1). When the slip returns to the starter, they subtract their random number — yielding the total without ever revealing any individual vote. This is additive secret sharing in disguise.
The protocol step by step:
- Voter A writes a random large number on a slip (e.g. 849) — their mask.
- A → B: B reads the running total, adds their vote (+1 for yes, +0 for no), e.g. 849 → 850, passes it on.
- B → C and C → D: same procedure, each adding their vote silently.
- D → A: the slip comes back with
849 + (total yes votes). - A subtracts 849 and broadcasts the total (in this worked example: 2 yes votes).
Why this is additive secret sharing:
- Each intermediate sum is a uniformly random integer (because A's mask was random) — knowing any partial total reveals nothing.
- Only A knows the mask, so only A can compute the final count.
- It generalises to MPC sum protocols used in real-world privacy-preserving analytics (Apple, Google federated learning).
Properties achieved:
- ✅ Vote secrecy — nobody (including A!) sees individual votes.
- ✅ Tally correctness — by linearity, the final number = sum of votes.
- ❌ Robustness — A can lie about the mask; one dishonest participant breaks the protocol.
- ❌ Verifiability — voters can't verify their vote was counted; they have to trust the chain.
Tip: This toy protocol captures the essence of secure aggregation: a sum can be computed without revealing the summands. Real systems add commitments and zero-knowledge proofs that each summand is in {0, 1} (otherwise a malicious voter could vote +1000), and threshold cryptography so no single party holds the mask.