SEAL密文中的消零槽

Question

我已经和SEAL库混了几天了，我有一个下面的问题。

我有一堆数据点X_1，.，x_N，n< poly_mod_deg类型'double‘，我使用批处理编码和CKKS sceheme来计算它们的平均值和方差。计算平均值很好，我喜欢结果，但我想以更有效的方式计算方差。

来解释我的意思：

在进行方差计算时，我有以下数据：

加密(X_1，x_2，x_3，.，x_n，0，.，0)和

加密(X_avg，x_avg，x_avg，.，x_平均) (*)

接下来，我计算它们之间的差异，得到如下内容：

加密(X_1-x_avg，x_2-x_avg，x_3-x_avg，.，x_氮-x_avg，-x_avg，-x_-x，._平均) (**)

然后我就会得到：

加密((x )_1-x_^2，(X)_2-x_^2，(X)_3-x_^2，.，(X)_氮-x_x_())(*)

然后用n个左转对n个值进行求和，并将结果除以n，最终得到方差。

这对于小n很好，但我希望在(*)或(**)或(*)处将无用的组件归零，这样在平方之后，我就可以得到以下内容：

加密((x )_1-x_^2，(X)_2-x_^2，(X)_3-x_^2，，(X)_氮-x_x_)^2，0，0，0)

我想要这样做，因为这样我就能够用log2(poly_deg/2)求和来计算它们的和，使用https://www.youtube.com/watch?v=XaYEHnaAg8M&t=47m29s中描述的技术，能以简单、安全、有效的方式实现它吗？

我曾尝试将(*)或(**)或(*)乘成1.0，1.0，.，1.0，0.0，.，0.0，其中除前n个分量外，所有组件都为零。它没有起作用，因为编译器抱怨“结果密文是透明的”，并中止了任务，而且我也不喜欢这个解决方案，因为它再使用一个乘法，希望这是过度的。

我越来越绝望了，我也试图从

加密(X_1，x_2，x_3，.，x_n，0，.，0)到

加密(X_avg，x_avg，x_avg，.，x_平均)。

我做了这样的事：

c_zero =加密(X_1，x_2，x_3，.，x_n，0，.，0)n+1；

N

(X_avg，x_avg，x_avg，.，x_平均)我= c_zero；

    i++；

但是我想这个东西不是这样的，因为打印出最后的二三十个值

加密(X_1，x_2，x_3，.，x_n，0，.，0)显示不重复。

在这一点上，这也可能意味着我总是要告诉“服务器端”加密的数据点在密文中的数量？这有多不安全？

我不想用代码来充实帖子，所以它就在这里：https://pastebin.com/Uy0wdgG9。还删除了代码中的注释，因为它们都是我的母语。抱歉的。

还有一个机会，来自海豹突击队的人看到这个:伟大的工作，有趣的东西！

Answer 1

作为一个警告，我从未与微软SEAL合作过。但以下几点可能仍然是有用的。

有限数据集(x_1,\dots, x_n)的方差公式可以编写为：

\sigma^2 = \frac{1}{n}\sum_{i = 1}^n(x_i - \mu)^2

其中：

\mu = \frac{1}{n}\sum_{i = 1}^n x_i

请注意，n\mu = \sum_{i = 1}^n x_i --我将在这两个表达式之间自由切换。

可以用代数方式将\sigma^2的表达式操作为以下表达式：

\sigma^2 = \frac{n\sum_{i = 1}^n x_i^2 - \sum_{i = 1}^n x_i}{n^2}

(检查这是一个相同的公式)！可以按以下方式更容易地计算此表达式。让\vec{x} = (x_1,x_2,\dots, x_n, 0,0,\dots,0)成为您的明文向量，其中我假设n是一个秘密参数(如果不是这样的话，事情会更容易一些，但不会太多)。让c成为\vec{x}的加密。

1. 通过旋转技巧计算密文向量c_{n\mu} =(n\mu, n\mu,\dots, n\mu) (您已经这样做了)
2. 正方形c坐标--得到带有“插槽”(x_1^2,\dots, x_n^2, 0^2,\dots, 0^2)的矢量c_{x_i^2}
3. 将你的旋转技巧应用于c_{x_i^2}，得到矢量c_{\sum_i x_i^2} = (\sum_i x_i^2, \sum_i x_i^2,\dots, \sum_i x_i^2)

现在，c_{n\mu}的任何时隙(它们都取值n\mu)、c_{\sum_i x_i^2}的任何时隙(都取值\sum_{i = 1}^n x_i^2)和N都足以通过公式计算方差：

\sigma^2 = \frac{n\sum_{i = 1}^n x_i^2 - n\mu}{n^2}

如果您可以将此计算推迟到解密(即使是N\to\infty，它应该保持相当高的效率，就像4个算术操作一样)，那么您应该这样做(而密文可以采用表单(c_{n\mu}[0], c_{\sum_i x_i^2}[0], c_N)，其中c_N是加密文本加密N)。否则，问题将归结为能够提取SEAL密文的(任何)“插槽”，这很可能在不执行更多乘法的情况下实现。

这导致了一些不同的情况：

• 如果N必须保密，而且不能推迟此计算，那么您必须清楚地计算乘法( c_N\times c_N )、c_N\times c_{\sum_i x_i^2} (可以并行完成，将乘法深度增加1)和c_N\times c_N除法，从而导致乘法深度3的计算(与通过密文加密(1,1,\dots,1,0,0,\dots,0)乘以零的“坏”情况相同)。
• 如果N可以是公共的，则只需计算标量乘法，就可以在(总)乘法深度1中完成。
• 如果您可以将计算推迟到解密，则可以再次以总乘法深度1完成整个计算(即使在保密N时也是如此)。

所有这些讨论都假设您希望最小化乘法深度。看起来您正在使用CKKS作为您的底层方案，我不记得它的复杂性是由乘法深度控制的，还是由更深奥的东西控制的(比如GSW计算乘法复杂性的方法)。不过，以下两点：

• 重写计算，使其在代数上完全相同，同时(希望)更简单地计算同态
• 将计算的(小)部分推迟，以便尽可能在客户端上执行

值得记住的是，作为优化事物的通用方法。