同态加密中电路的程度是多少？

Question

在BGV的论文中，我发现一个有趣的句子如下：

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.)"

作者认为BGV方案依赖于电路的深度，而以前的方案依赖于电路的程度，并且认为电路的程度可能比电路的深度大得多，那么在同态加密中，电路的深度和程度有什么区别呢？

Answer 1

深度和程度的区别取决于电路的拓扑结构。对于算术电路，给定任何多项式p(x)，有许多等效电路来计算它。每个电路对应于将p(x)中的操作关联的显式方式。对于一个基本的例子，考虑一下p(x_1,x_2,x_3) = x_1x_2+x_3x_2 + x_3.可以用各种方式编写，例如

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

或

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

它们定义了两种不同的电路(将它们显式地写下来可能很有用)，但对你的整个问题没有帮助--两者都有相同的深度(即3)。

p(x) = x^{2^k}是深度和程度发散的一个标准例子。你可以把这个联想成

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

这对应于深度2^k电路(电路是一条“直线”)来计算度2^k多项式。你也可以把它写成“完整的二叉树”。首先计算x^2 = x\cdot x，然后计算x^4 = x^2\cdot x^2 (计算深度2的4次多项式)，然后计算x^{8} = x^4\cdot x^4 (深度3的8次多项式)，等等。

最后，请注意，深度并不总是实现效率目标的正确标准。首先，加法通常是“免费的”，所以我们只关心深度的概念，在这里我们测量执行了多少乘法。然而，有时我们关心的是更深奥的措施。例如，在GSW中，要计算p(x)= x^{2^k}，“行图”方法比“完整二叉树”方法要好。但在大多数情况下(BGV，B/FV，CKKS)，低的“乘法深度”计算更有效。