Rewrite Rules

Disclosure of Funding Source: This research was conducted at the Georgia Institute of Technology under the supervision of Dr. Jun Ueda, completing in July 2022, resulting in the following publication: Rewrite Rules for Automated Depth Reduction of Encrypted Control Expressions with Somewhat Homomorphic Encryption.

This study was supported in part by National Science Foundation Grant Nos. 2112793. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

$\newcommand{\associativeExpressionBefore}{\left( \left( \left( a \cdot b \right) \cdot c \right) \cdot \left( d \cdot e \right) \right) \cdot \left( f \cdot g \right)}$ $\newcommand{\associativeExpressionAfter}{\left( \left( f \cdot g \right) \cdot \left( d \cdot e \right) \right) \cdot \left( \left( a \cdot b \right) \cdot c \right)}$ $\newcommand{\distributiveExpressionBefore}{\left( \left( \left( a \cdot b \right) \cdot c \right) \cdot \left( d \cdot e \right) + f + g \right) \cdot \left( h \cdot i\right)}$ $\newcommand{\distributiveExpressionAfter}{\left( \left( a \cdot b \right) \cdot c \right) \cdot \left( d \cdot e \right) \cdot \left( h \cdot i\right) + \left(f + g \right) \cdot \left( h \cdot i\right) }$

What is an Arithmetic Circuit?

An arithmetic circuit is a directed acyclic graph, where leaf nodes are inputs and internal nodes are arithmetic operations such as addition or multiplication. In these graphs nodes which only have incoming connection but no outgoing connections are termed circuit outputs An example circuit is shown below:

Arithmetic circuit of $(a+b)$

Creating functional encrypted calculations revolves around managing cipher noise, an intrinsic aspect of HE where arithmetic operations inject noise into the ciphertext. If enough noise accumulates the calculation can no longer be decrypted and the data is lost. Multiplication produces orders of magnitude more noise than addition, so much so that many choose to treat addition as “free” and focus only on optimization for fewer multiplications.

While multiplication is bad, consecutive multiplication is far worse. This is because the amount of noise injected by a multiplicative operation increases each time that value is multiplied. For this reason we keep track of the multiplicative depth of each node with $\Delta$. That is, all inputs start with a $\Delta = 1$ and for each multiplication gate the circuit passes through the $\Delta$ will increment by $1$. This can be seen in the simple example below:

Arithmetic circuit of $(a+b) \times c$ equation. The $\Delta$ label on each node denotes that node’s multiplicative depth, notice the output depth is $2$ while all other nodes have a depth of $1$.

This research will explore automated rewrite rules that can be applied to reduce the depth of an arithmetic circuit. Two major rewrites–the associative rewrite and the distributive rewrite–are explored in the following section.

Rewrites

Associative Rewrite

The associative rewrite represents a regrouping of parameters as in $(a \cdot b) \cdot c = a \cdot (b \cdot c)$, and is only applicable to two adjacent MUL gates. For example, if $a$ has a greater depth than both $b$ and $c$, i.e.

\[\text{depth}(b), \text{depth}(c) < \text{depth}(a)\]

then, an associative rewrite will decrease the overall depth of the circuit.

This is depicted below, note however that $a$ represents some subcircuit with depth $3$ and is not a circuit input as in the previous example.

A demonstration of the rewrite $(a \cdot b) \cdot c \to a \cdot (b \cdot c)$. Before the rewrite the node $a$ (blue dashed circle) has higher depth than the other nodes. It is identified that if $a$ swaps places with $c$ (red dot-dashed circle) then the overall depth of the circuit will decrease by one.

Since $\text{depth}(a)$ is the greatest of all nodes considered, it is counterproductive to have node $a$ deep in the graph. By swapping node $a$ and $c$, we reduce the number of future MUL gates that $a$ will have to pass through by one.

Consider the more complex example $\associativeExpressionBefore$. Looking at this expression we can observe that it is left-heavy, meaning the left side of the tree is significantly deeper than the right side. This is exactly the same as the first associative rewrite example we considered above.

Associative rewrite taking $\associativeExpressionBefore$ and converting it into the more balanced $\associativeExpressionAfter$. The orange colored nodes represent elements of the critical path which is the path of maximum depth.

Notice the associative rewrite swapped $\left( \left( a \cdot b \right) \cdot c \right)$ with the $\left( f \cdot g \right)$ term. This is because associative rewrite has the tendency of convert graph depth to graph breadth, thus steering the graph towards a more balanced configuration.

The path shown in orange is the “critical path” that results in the maximum depth of the circuit. A well balanced tree will have almost all its nodes in the critical path.

Distributive Rewrite

The distributive rewrite is not able to lower circuit depth, unlike the associative rewrite, and in fact adds an additional MUL gate into the circuit. In spite of this, the distributive rewrite is advantageous by moving a MUL gates higher up in the circuit to be adjacent to a different MUL gate. When these newly neighbored gates satisfy the pattern described by \eqref{eq:associative-rewrite-requierment}, the distributive rewrite will facilitate a future associative rewrite with depth reducing ability at the cost of net one additional MUL gate.

This is shown in the figure below:

Distributive rewrite rule takin in $\distributiveExpressionBefore$ and converting it to $\distributiveExpressionAfter$. The circled regions show sub-graphs that were rearranged, while the uncircled represent newly created gates.

The distributive rewrite represents the distribution of an outside factor to a term in a sum, such as $(((x+y_1)+…)+y_k) \cdot z$. The naïve approach would be to distribute the $z$ to every addend, such as: $(x z) + (y_1 z) + … + (y_k z)$. This however, will add a MUL gate for every ADD gate on the path, which is often more than is necessary. Instead, one can selectively distribute $z$ in a form such as: $(x \cdot z) + (y_1 + … + y_k) \cdot z$.

A larger number of MUL gates negatively impacts the execution time of the resulting circuit; however, if the distributive rewrite is able to facilitate a future associative rewrite–and thus facilitate future depth reduction–then it is worth the few additional MUL gates for the depth reduction gained.

Video Presentation