Score:2

What's the degree of a circuit in homomorphic encryption?

lt flag

In the paper of BGV, I find an interesting sentence as below:

One may view our new scheme as a very powerful SWHE scheme in which this dependence on degree has been replaced with a similar dependence on depth. (Recall the degree of a circuit may be exponential in its depth.)"

The author says that BGV scheme relys on the depth of circuit and previous scheme relys on the degree of circuit, and says that the degree of circuit maybe be much larger than depth of circuit, so what's the difference between depth and degree of circuit in homomorphic encryption?

Score:1
ng flag

The distinction between depth and degree depends on the topology of the circuit. For arithmetic circuits, given any polynomial $p(x)$, there are many equivalent circuits that compute it. Each circuit corresponds to an explicit way of associating the operations in $p(x)$. For a basic example, consider $p(x_1,x_2,x_3) = x_1x_2+x_3x_2 + x_3.$ One can write this various ways, for example

$$p_1(x_1,x_2,x_3) = (x_2(x_1+x_3))+x_3,$$

or

$$p_2(x_1,x_2,x_3) = (x_3(1+x_2) + (x_1x_2)).$$

These define two alternative circuits (writing them down explicitly may be useful), but doesn't help with your overall question --- both have the same depth (namely 3).

A standard example of where depth and degree diverge is $p(x) = x^{2^k}$. One can associate this as

$$p_1(x) = \overbrace{x(x(\dots x)\dots )}^{2^k\text{ times}}.$$

this corresponds to a depth $2^k$ circuit (the circuit is a "straight line") to compute the degree $2^k$ polynomial. One can alternatively write this as a "full binary tree". First you compute $x^2 = x\cdot x$, then $x^4 = x^2\cdot x^2$ (computing a degree 4 polynomial in depth 2), then $x^{8} = x^4\cdot x^4$ (degree 8 in depth 3), etc.

Finally, note that depth is not always the right metric to target for efficiency. First, additions are typically "for free", so we only care about a notion of depth where we measure how many multiplications are performed. Sometimes we care about more esoteric measures though. For example in GSW, to compute $p(x)= x^{2^k}$, the "line graph" approach is better than the "full binary tree" approach. But in most settings (BGV, B/FV, CKKS), low "multiplicative depth" computations are more efficient.

cn flag
Could you elaborate why it's hard go compute $p(x) = x^{2^k}$ in GSW? Is it because it's hard to make a product between two LWE ciphertexts?
Mark avatar
ng flag
It isn't that it is hard to compute, it is that writing $p(x)$ as a depth $k$ circuit, which has the best noise growth properties for BGV and B/FV, leads to sub-optimal noise growth for GSW. In GSW, you instead want to leverage that multiplication has asymmetric noise growth. A relatively high ($2^k$) depth circuit has better noise growth properties, i.e. depth is the wrong metric to target for GSW.
纪老猴子 avatar
lt flag
Thank you, your answer help me a lot.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.