Capstok — learn by doing

Why this matters

The HE literature uses three terms — PHE, SHE, FHE — that look like a marketing ladder but actually correspond to genuinely different mathematical capabilities and wildly different costs. PHE schemes (RSA, ElGamal, Paillier) have been around since the 1970s and run at ordinary public-key crypto speeds; they support exactly one operation forever. SHE schemes can do both addition and multiplication but only up to some bounded circuit depth before the noise overwhelms the message. FHE, the breakthrough that arrived in Gentry's 2009 thesis, can evaluate circuits of arbitrary depth — the key trick being a procedure called bootstrapping that resets the noise. Why care about the distinction? Because the right scheme for your application depends entirely on what you need to compute. A private sum across a million voters needs PHE and runs in milliseconds. A neural network forward pass needs SHE or FHE and might run in seconds-per-input even with 2024-era libraries. Picking the wrong rung wastes 1000x in compute.

Demo

Each rung is defined by which circuits the $\mathrm{Eval}$ algorithm accepts. PHE: a single gate type, repeated. SHE: any combination of gates, but only up to depth $L$ for a parameter $L$ baked into the keys. FHE: any polynomial-size circuit, no depth bound, achieved by composing an SHE scheme with a bootstrapping procedure that converts a 'tired' ciphertext into a 'fresh' one homomorphically.

\text{PHE: } \mathcal{C} = \{x_1 \oplus x_2 \oplus \cdots\}\ \text{ for one fixed }\oplus.\quad \text{SHE: } \mathcal{C} = \{C : \mathrm{depth}(C) \leq L\}.\quad \text{FHE: } \mathcal{C} = \text{P/poly}.

Try it yourself

Run the snippet and confirm the addition path matches but the multiplication path returns garbage. This is PHE in miniature: addition is 'free,' multiplication is impossible.
Add a third ciphertext and chain three additions. Confirm $\mathrm{Dec}(c_1 + c_2 + c_3) = (m_1 + m_2 + m_3) \bmod N$ . There is no depth bound on additions — that's the PHE property.

References

// main.go
// Toy PHE: an additively-homomorphic 'pseudo-Paillier' over a small modulus.
// Real Paillier uses RSA-style composite N = pq; this is a stripped-down version
// that is correct for addition (but NOT secure — illustrative only).
package main

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

const N = 10_007
const MASK = 1 << 32

type CT struct{ blinded, r int64 }

func randBits32() int64 {
	b := make([]byte, 4)
	rand.Read(b)
	return int64(b[0])<<24 | int64(b[1])<<16 | int64(b[2])<<8 | int64(b[3])
}

func Enc(m int64) CT {
	r := randBits32() & (MASK - 1)
	return CT{(m + r) % MASK, r} // (blinded, randomness) — toy form
}

func Dec(c CT) int64 {
	return ((c.blinded-c.r)%MASK + MASK) % MASK % N
}

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

func BadMulCT(c1, c2 CT) CT {
	return CT{(c1.blinded * c2.blinded) % MASK, (c1.r * c2.r) % MASK}
}

func main() {
	_ = big.NewInt // suppress import-not-used if bigint unused
	var m1, m2 int64 = 137, 246
	c1, c2 := Enc(m1), Enc(m2)
	cSum := AddCT(c1, c2)
	fmt.Println("plaintext sum   :", (m1+m2)%N)
	fmt.Println("decrypted sum   :", Dec(cSum))

	// Now try multiplying the ciphertexts componentwise:
	cBad := BadMulCT(c1, c2)
	fmt.Println("plaintext prod  :", (m1*m2)%N)
	fmt.Println("decrypted prod  :", Dec(cBad), " <-- garbage; this scheme is PHE not SHE")
}

Run: go run main.go

Partial vs. Somewhat vs. Fully Homomorphic Encryption

Why this matters

Demo

Try it yourself

References