2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – lamba
    Commented Apr 9, 2023 at 7:35
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 10, 2023 at 1:53
  • 1
    $\begingroup$ Thank you, your answer help me a lot. $\endgroup$ Commented Apr 11, 2023 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.