Computation graphs

A computation graph is a directed acyclic graph whose nodes are operations and whose edges are the data dependencies between them. Compilers favor this representation because it makes a program's structure explicit: independent subcomputations are easy to spot and schedule, repeated subexpressions can be computed once and shared, unused nodes can be pruned, and optimizations become local graph rewrites that swap a node or subgraph for a cheaper equivalent.

Our system represents a CKKS program at two levels of abstraction. The compiler first builds a ciphertext graph, whose nodes are the high-level ciphertext operations the user wrote. It then lowers this into a polynomial graph, whose nodes are the ten polynomial operations that actually run on the hardware. Both representations are described below, and the optimization passes of the next section operate on each in turn.

Ciphertext graphs

[WORK IN PROGRESS]

The high-level IR: a graph whose nodes are the ciphertext operations the user wrote (additions, multiplications, rotations, and the composite operations built on them), with edges tracking how ciphertexts flow from one operation to the next.

Polynomial graphs

[WORK IN PROGRESS]

The lowered IR: each ciphertext node is expanded into the underlying polynomial operations (NTTs and inverse NTTs, modulus reductions, rescalings, and so on), exposing the level drops, key-switches, and representation changes that the ciphertext graph leaves implicit.