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.

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, explain the difference between PHE, SHE, and FHE, using the analogy of building a Lego house: which schemes give you a single brick type, which give you all brick types but a height limit, and which let you build to any height?

2. Why it works (the mechanism)

Walk me step by step through why Paillier supports only addition (not multiplication). Where in the encryption formula does the multiplicative structure break down, and why couldn't a clever modification fix it without going to lattice-based constructions?

3. Advanced — application & what's next

Why is bootstrapping the *only* known technique for upgrading SHE to FHE, and what does it tell us about the structure of HE that the same trick — homomorphically evaluating the decryption circuit — works across BFV, BGV, CKKS, and TFHE despite their very different plaintext spaces?

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