Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.
Most cryptographic primitives are defined by a security game — IND-CPA, IND-CCA, EUF-CMA. HE is unusual because the correctness condition is the interesting half of the definition: an HE scheme is one where, for any circuit in some allowed class, evaluating on ciphertexts gives a ciphertext that decrypts to applied to the plaintexts. This sounds obvious in English but pinning it down precisely is what separates HE from 'I XORed two ciphertexts together and got something.' The definition tells you what an HE library is promising and, critically, what it isn't — it does not promise that the output ciphertext looks like a fresh encryption (that's circuit privacy), and it does not promise unbounded depth (that's full homomorphism). Internalize the four-tuple now and you'll read the rest of the literature without confusion.
An HE scheme is a tuple . KeyGen produces a public/secret key pair. Enc takes the public key and a plaintext message and produces a ciphertext. Dec takes the secret key and a ciphertext and produces a plaintext. Eval takes the public key, a circuit description , and a tuple of ciphertexts and returns a new ciphertext. The defining property is the homomorphic correctness equation below: evaluating on ciphertexts and then decrypting equals evaluating on plaintexts directly.
Enc to return m + 1000 (a constant offset). The assertion now fails — locate the line in Eval you'd need to change to restore correctness, and write down what Eval would look like.KeyGen/Enc/Dec as a Caesar-cipher-style scheme over integers (, ). Show that for works: — close, but not quite right. Find the off-by- correction would need.Use these three in order. Each builds on the one before.
In one paragraph, explain the homomorphic correctness equation $\mathrm{Dec}(\mathrm{Eval}(C, \mathrm{Enc}(m))) = C(m)$ in plain English. Why is the equation written this way and not, say, $\mathrm{Eval}(C, \mathrm{Enc}(m)) = \mathrm{Enc}(C(m))$ — is there a difference?
Walk me through the formal definition of an HE scheme as a four-tuple $(\mathrm{KeyGen}, \mathrm{Enc}, \mathrm{Dec}, \mathrm{Eval})$, giving the input/output type of each algorithm and the correctness/security/compactness conditions each must satisfy.
Compactness says $|\mathrm{Eval}(C, c_1, \ldots, c_n)|$ is bounded independently of $|C|$. Why is this the technically deep requirement that 'almost-HE' schemes (like ones based on garbled circuits) fail to meet, and why does dropping compactness collapse HE back to interactive secure computation?
Evalcompactness — the size of 's output must not grow with the size of . Sketch why a scheme that just returns as the 'evaluated ciphertext' technically satisfies the correctness equation but is useless — the client ends up doing all the work.// main.go
// Toy demonstration with the *trivially homomorphic* identity scheme,
// just to make the type signatures concrete. (No security here — that's the point.)
package main
import "fmt"
type Keys struct {
pk int // public params
sk int // secret
}
func KeyGen() Keys {
return Keys{pk: 0, sk: 42}
}
func Enc(pk, m int) int {
return m // toy: identity
}
func Dec(sk, c int) int {
return c
}
func Eval(pk int, circuit func(int, int) int, cts ...int) int {
return circuit(cts[0], cts[1]) // legal because Enc is the identity on ints
}
func main() {
// Verify the homomorphic correctness equation for C = (x,y) -> x*y + 7
keys := KeyGen()
m1, m2 := 5, 9
c1, c2 := Enc(keys.pk, m1), Enc(keys.pk, m2)
C := func(x, y int) int { return x*y + 7 }
lhs := Dec(keys.sk, Eval(keys.pk, C, c1, c2))
rhs := C(m1, m2)
fmt.Println("LHS (decrypt-after-eval):", lhs)
fmt.Println("RHS (plaintext eval): ", rhs)
if lhs != rhs {
panic("homomorphic correctness violated")
}
}
go run main.go