Capstok — learn by doing

Why this matters

The reason HE matters in 2024 is not the maths — the maths has been settled since 2009 — it's that the cost-benefit ratio finally crossed the line for real applications. Three families dominate. Private ML inference: a hospital sends an encrypted scan to a cloud-hosted classifier; the classifier returns an encrypted prediction; the cloud sees nothing. Secure multiparty computation with HE as the underlying primitive: parties pool data without revealing their inputs (private set intersection, federated analytics, advertising attribution). Verifiable e-voting and tally: votes are encrypted under a public key, tallies are computed homomorphically, and a threshold of trustees decrypts only the aggregate. Each use case puts different demands on the scheme — depth requirements, throughput, ciphertext size, latency tolerance — and the right scheme is rarely the same across the three. Knowing the use case landscape upfront lets you skip the wrong libraries and pick the right rung in the FHE/SHE/PHE hierarchy from the start.

Demo

Three sketches at the same level of abstraction. (1) ML inference: client encrypts $x$ , sends to server, server runs $\mathrm{Eval}(W \cdot x + b)$ homomorphically, returns ciphertext. (2) Private set intersection by HE: each party encrypts a polynomial whose roots are their set elements; the parties multiply ciphertexts to find the GCD of polynomials, whose roots are the intersection. (3) E-voting: each voter encrypts $0$ or $1$ under a tally key; the bulletin board sums all ciphertexts; the trustees jointly decrypt only the sum.

\text{ML: } \mathrm{Enc}(\mathrm{ReLU}(Wx+b)).\quad \text{PSI: } \mathrm{Enc}\left(\prod_{a \in A}(x-a) \cdot \prod_{b \in B}(x-b)\right).\quad \text{Voting: } \mathrm{Enc}\left(\sum_i v_i\right) = \prod_i \mathrm{Enc}(v_i).

Try it yourself

Run the snippet. The tallies match. Note that the server never saw any individual ballot — only their encrypted form, and only the encrypted sum.
Add a malicious voter who encrypts the value 1000 instead of 0 or 1, then re-run. The tally is wrong by 1000. This is why real e-voting protocols pair HE with zero-knowledge proofs that each ciphertext encrypts a value in $\{0,1\}$ .
For private ML inference: list three operations a typical neural network uses that cannot be evaluated as polynomial circuits (ReLU, softmax, max-pool). For each, name the standard HE workaround (polynomial approximation, sign-test via Chebyshev, etc.).
For private set intersection: assume Alice has a set of size 100 and Bob has a set of size 100,000. Why is the polynomial-roots PSI prohibitively expensive at this asymmetry? Look up labelled PSI and write one sentence explaining what it does differently.
Pick the rung — PHE, SHE, or FHE — for each of these three apps: (a) homomorphic vote tally, (b) homomorphic CNN inference, (c) homomorphic SQL COUNT(*) WHERE x > 5. Justify each choice using the multiplicative-depth picture.

References

// main.go
// Toy private-tally e-voting using the toy additively-homomorphic scheme from task 3.
// 1000 voters each cast a 0/1 ballot; the server tallies homomorphically; a trustee decrypts.
package main

import (
	"crypto/rand"
	"fmt"
	"math/big"
	mathrand "math/rand"
)

const N = 100_003
const MASK = int64(1) << 40

type CT struct{ b, r int64 }

func Enc(m int64) CT {
	rBig, _ := rand.Int(rand.Reader, big.NewInt(MASK))
	r := rBig.Int64()
	return CT{(m + r) % MASK, r}
}

func Dec(c CT) int64 {
	val := ((c.b - c.r) % MASK + MASK) % MASK
	return val % N
}

func AddCT(c1, c2 CT) CT {
	return CT{(c1.b + c2.b) % MASK, (c1.r + c2.r) % MASK}
}

func main() {
	rng := mathrand.New(mathrand.NewSource(7))

	ballots := make([]int64, 1000)
	for i := range ballots {
		ballots[i] = int64(rng.Intn(2))
	}

	encBallots := make([]CT, 1000)
	for i, b := range ballots {
		encBallots[i] = Enc(b)
	}

	// Server-side tally — never decrypts an individual ballot.
	tallyCT := encBallots[0]
	for _, c := range encBallots[1:] {
		tallyCT = AddCT(tallyCT, c)
	}

	var plainSum int64
	for _, b := range ballots {
		plainSum += b
	}

	fmt.Println("plaintext tally   :", plainSum)
	fmt.Println("homomorphic tally :", Dec(tallyCT))
	fmt.Println("individual ballots leaked? no — server only ever held ciphertexts.")
}

Run: go run main.go

What People Build with Homomorphic Encryption

Why this matters

Demo

Try it yourself

References