选择合适的plaintext_modulus
Choosing a suitable plaintext_modulus
在plaintext_modulus
等参数的选择上,有什么好的策略吗? (除了猜测和检查直到输出看起来正确)
特别是,我正在试验 IntegerEncoder
和 BFV。我的(可能错误的)理解是 plaintext_modulus
不是 不是 被编码整数的模数,而是多项式表示中每个系数的模数。
当 B=2 时,这些系数看起来只是 0 或 1。但是,在应用加法和乘法等操作之后,情况显然不再如此。有没有一种好的方法可以确定系数的良好界限,以便选择 plaintext_modulus
?
My (potentially-wrong) understanding is that the plaintext_modulus is not the modulus for the integer being encoded, but the modulus for each coefficient in the polynomial representation.
这是使用IntegerEncoder
时的正确思路。但是请注意,当使用 BatchEncoder
(海豹突击队 2.* 中的PolyCRTBuilder
)时,情况恰恰相反:明文向量中的每个槽都是整数模 poly_modulus
.
With B=2, it looks like these coefficients will just be 0 or 1. However, after operations like add and multiply are applied, this clearly is no longer the case. Is there a good way to determine a good bound for the coefficients, in order to pick plaintext_modulus?
IntegerEncoder
的全部要点是新编码具有尽可能小的系数,延迟 plain_modulus
溢出并允许您使用更小的 plain_modulus
(意味着噪声增长更小)。 SEAL 2.* 有一个自动参数选择工具,可以对噪声增长和明文系数增长执行启发式上限估计,并且基本上完全按照您的要求进行。不幸的是,这些估计是在每个操作的基础上执行的,导致早期操作中的高估在计算的后期阶段爆炸。因此,除了最简单的计算之外,估计值不是很严格,而且在许多情况下,该工具提供的参数过大。
为了估计乘法中明文系数的增长,让我们考虑两个多项式 p(x) 和 q(x)。显然,乘积的度数正好等于 deg(p)+deg(q)---那部分很简单。如果|P|表示多项式P的无穷范数(最大系数的绝对值),则:
|p*q| <= min{deg(p)+1, deg(q)+1} * |p||q|。
实际上,SEAL 2.* 在这里更精确一些。它不使用度数,而是使用这些多项式中非零系数的数量。当多项式稀疏时,这会产生很大的不同,在这种情况下,交叉项的贡献要小得多,更好的界限是:
|p*q| <= min{#(non_zero_coeffs(p)), #(non_zero_coeffs(q))} * |p||q|。
Costache 等人 在 https://eprint.iacr.org/2016/250 中对 IntegerEncoder
类编码器中的系数增长进行了更深入的分析,您可能想看看在
在plaintext_modulus
等参数的选择上,有什么好的策略吗? (除了猜测和检查直到输出看起来正确)
特别是,我正在试验 IntegerEncoder
和 BFV。我的(可能错误的)理解是 plaintext_modulus
不是 不是 被编码整数的模数,而是多项式表示中每个系数的模数。
当 B=2 时,这些系数看起来只是 0 或 1。但是,在应用加法和乘法等操作之后,情况显然不再如此。有没有一种好的方法可以确定系数的良好界限,以便选择 plaintext_modulus
?
My (potentially-wrong) understanding is that the plaintext_modulus is not the modulus for the integer being encoded, but the modulus for each coefficient in the polynomial representation.
这是使用IntegerEncoder
时的正确思路。但是请注意,当使用 BatchEncoder
(海豹突击队 2.* 中的PolyCRTBuilder
)时,情况恰恰相反:明文向量中的每个槽都是整数模 poly_modulus
.
With B=2, it looks like these coefficients will just be 0 or 1. However, after operations like add and multiply are applied, this clearly is no longer the case. Is there a good way to determine a good bound for the coefficients, in order to pick plaintext_modulus?
IntegerEncoder
的全部要点是新编码具有尽可能小的系数,延迟 plain_modulus
溢出并允许您使用更小的 plain_modulus
(意味着噪声增长更小)。 SEAL 2.* 有一个自动参数选择工具,可以对噪声增长和明文系数增长执行启发式上限估计,并且基本上完全按照您的要求进行。不幸的是,这些估计是在每个操作的基础上执行的,导致早期操作中的高估在计算的后期阶段爆炸。因此,除了最简单的计算之外,估计值不是很严格,而且在许多情况下,该工具提供的参数过大。
为了估计乘法中明文系数的增长,让我们考虑两个多项式 p(x) 和 q(x)。显然,乘积的度数正好等于 deg(p)+deg(q)---那部分很简单。如果|P|表示多项式P的无穷范数(最大系数的绝对值),则:
|p*q| <= min{deg(p)+1, deg(q)+1} * |p||q|。
实际上,SEAL 2.* 在这里更精确一些。它不使用度数,而是使用这些多项式中非零系数的数量。当多项式稀疏时,这会产生很大的不同,在这种情况下,交叉项的贡献要小得多,更好的界限是:
|p*q| <= min{#(non_zero_coeffs(p)), #(non_zero_coeffs(q))} * |p||q|。
Costache 等人 在 https://eprint.iacr.org/2016/250 中对 IntegerEncoder
类编码器中的系数增长进行了更深入的分析,您可能想看看在