安全存储的同态模约简

Question

我的问题非常类似于同态模，但我想给出一个在外包环境中执行操作的上下文。

是否有任何特定的同态密码方案可以同时进行模缩减和减法运算。

假设Enc(x)是x在同态加密后的密文，mod是模约简运算.

(Enc(x)-Enc(a))\ mod\ Enc(N) == (x-a)\ mod\ N

而x、a和N都是自然数。N大于x和a。

我知道mod可以转化为附加(+)和乘法(*)操作，这是HE支持的操作。但我不想让像Server这样的人接触到这样的因素。

例如

(6-5)\ mod\ 10 = 1+(0*10)=1，(4-5)\ mod\ 10 = -1+(1*10)=9

但是当分配一个Server时，这里的0和1这样的因素就会暴露出来。

因此，我想知道，是否有任何具体的HE方案可以直接进行模块缩减操作，或者有什么解决方案可以阻止Server不了解这些因素？

Answer 1

一般的解决方案是将N的比特长度固定为\ell，然后将a, x和N表示为\ell-dimensional二进制向量，并对每个比特进行加密(获取3\ell密文)，然后执行同态执行两个\ell-bit整数减法的电路和一个执行缩减(如@kelalaka的答案)的电路.

但是，如果N很小，那么您可以简单地使用一种方案，它的消息空间\mathcal M足够大，足以容纳x - a的可能值，也就是说，

[-N, N]\cap\mathbb{Z} \subset \mathcal M.

在这种情况下，减法不会“溢出”，您仍然可以通过简单的解密和自己执行模块缩减来恢复结果。

这或多或少相当于选择消息空间为\mathbb{Z}_N的同态加密方案，如果N较小，这也是一个简单的解决方案。

大多数方案都提供了二进制消息空间，但是它们可以很容易地扩展到\mathbb{Z}_N上而不是\mathbb{Z}_2上。