Pick a depth. Each prompt opens in your AI pre-loaded with the lesson. Click a row to preview the prompt.
When an HE engineer says a scheme 'supports depth-12 circuits,' they almost always mean multiplicative depth 12 — the longest chain of multiplications from input to output, ignoring additions. Why do we count multiplications and not additions? Because in lattice HE, additions are nearly free in noise terms while multiplications are expensive. The depth count is the single most important quantity that determines the cost of an HE evaluation — it sets the modulus size, which sets the ring dimension, which sets the runtime and memory. Moreover, this isn't just bookkeeping. It changes how you write algorithms: a textbook algorithm with multiplicative depth might be brutally expensive, while a carefully restructured one with constant depth is cheap. Learning to read circuits by their multiplicative depth — and to rewrite them to reduce it — is the core algorithmic skill of HE programming.
The multiplicative depth of a circuit is the maximum number of multiplication gates on any input-to-output path. A polynomial like has multiplicative depth 3 if computed left-to-right () but depth 2 if computed as a tree (). Reducing depth by re-associating is a free win in HE; reducing depth by replacing a multiplication with additions is the real game.
x > y over encrypted integers as a polynomial. (Hint: use the indicator polynomial — depth over .) Why is this expensive? What's the depth for ?// main.go
// Two equivalent computations of x^8, with very different multiplicative depths.
// We model a circuit as a tree and compute its multiplicative depth.
package main
import "fmt"
type NodeKind int
const (
KindVar NodeKind = iota
KindMul
KindAdd
)
type Node struct {
Kind NodeKind
Name string // for Var
A, B *Node // for Mul/Add
}
func Var(name string) *Node { return &Node{Kind: KindVar, Name: name} }
func Mul(a, b *Node) *Node { return &Node{Kind: KindMul, A: a, B: b} }
func Add(a, b *Node) *Node { return &Node{Kind: KindAdd, A: a, B: b} }
func multDepth(n *Node) int {
switch n.Kind {
case KindVar:
return 0
case KindAdd:
a, b := multDepth(n.A), multDepth(n.B)
if a > b {
return a
}
return b
case KindMul:
a, b := multDepth(n.A), multDepth(n.B)
if a > b {
return 1 + a
}
return 1 + b
}
return 0
}
func main() {
x := Var("x")
// Naive: x^8 = ((((((x*x)*x)*x)*x)*x)*x)*x
linear := x
for i := 0; i < 7; i++ {
linear = Mul(linear, x)
}
// Tree: x^8 = ((x*x) * (x*x)) * ((x*x) * (x*x))
x2 := Mul(x, x)
x4 := Mul(x2, x2)
tree := Mul(x4, x4)
fmt.Println("x^8 linear chain — multiplicative depth:", multDepth(linear))
fmt.Println("x^8 binary tree — multiplicative depth:", multDepth(tree))
}go run main.go