Выбор подходящего модуля plaintext_modulus

Есть ли хорошая стратегия выбора таких параметров, как plaintext_modulus? (кроме предположений и проверок, пока результат не станет правильным)

В частности, я экспериментирую с IntegerEncoder с BFV. Мое (потенциально ошибочное) понимание состоит в том, что plaintext_modulus - это нет, модуль для кодируемого целого числа, но модуль для каждого коэффициента в полиномиальном представлении.

При B = 2, похоже, эти коэффициенты будут просто 0 или 1. Однако после применения таких операций, как сложение и умножение, это явно не так. Есть ли хороший способ определить хорошую границу коэффициентов, чтобы выбрать plaintext_modulus?

1
0
119
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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 (PolyCRTBuilder в SEAL 2. *) ситуация прямо противоположная: каждый слот в векторе открытого текста является целым числом по модулю 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 |.

Более глубокий анализ роста коэффициентов в кодировщиках типа IntegerEncoder выполнен в https://eprint.iacr.org/2016/250 компанией Costache и другие., на которую вы, возможно, захотите взглянуть.

Другие вопросы по теме