如何在HElib中获得确切的插槽数？比如256,4096

Question

在同态加密库HElib (https://github.com/homenc/HElib)中，我们在生成密文之前设置了一组参数。例如：

m = 20191, p = 47, phi(m) = 19800
  ord(p) = 66
  normBnd = 1.62077
  polyNormBnd = 4.92719
  factors = [61 331]
  generator 2 has order (== Z_m^*) of 60
  generator 985 has order (== Z_m^*) of 5
r = 1
nslots = 300
hwt = 0
ctxtPrimes = [6,7,8,9,10,11,12,13,14]
specialPrimes = [15,16,17,18,19]
number of bits = 778

security level = 77.9265

最后，我们得到300个插槽的密文。但我想要有256个位置的密文。当我使用函数findM(/*k=*/80, /*nBits=*/500, /*c=*/2, /*p=*/47, /*d=*/1, /*s=*/256, /*chosen_m=*/0, /*verbose=*/true);时，无法获得适当的参数m来生成256个插槽。

那么，我应该如何选择参数来获得80/120位安全性，密文256/4096插槽。

Answer 1

你必须考虑以下几点：

1. 密文模块链(Q := q_1 \cdot ... \cdot q_\ell)的位长，它为应用程序提供了足够的乘法级别(在示例中使用的是778 )。
2. 最小m，它保证这样的Q比特长度的80位安全性。
3. 您需要m，以便\phi(m)可以被256整除(正如Chris在他的回答中所解释的)。
4. 您需要一个明文模p，使得\phi(m) / d = 256，其中d是p模m的乘法阶。

这四项实际上是相互依存和循环的(例如，增加m和p也减少了必须以同态方式操作的级别数，因此您可能不得不增加Q，这降低了安全性，因此您可能不得不增加m.)。但即便如此，最终还是不难找到参数。

例如，满足项目(3)的一种简单方法。就是选择

m = 512 \cdot k

为了一些k。特别是，m可以是两倍的幂。对于具有778位的80位安全性和模块化链，m = 512 \cdot 95或m = 2^{15}应该足够了(但是您必须验证它！)剩下的就是找到p。为此，您可以进行“蛮力”搜索。

例如，通过在SageMath细胞上运行以下Sage脚本，可以获得p = 193。

m = 512 * 95 
p = 3
NUMBER_OF_TRIES = 2**13
for _ in range(NUMBER_OF_TRIES):
    if 0 != m % p: # p divides m, skip
        d = Mod(p, m).multiplicative_order()
        if euler_phi(m) == d * 256:
            print("p = %d" % p)
            break
    p = next_prime(p)