Рейтинг:2

Почему вентиль AND * в полностью гомоморфном шифровании, схема BFV?

флаг ru

Согласно с Представление функции в виде схемы FHE, вентиль И для зашифрованных данных FHE просто А*Б, в случае, если открытый текст имеет только 0 или же 1 коэффициенты.

Помните, что на схеме BFV FHE шифруются полиномы, и мы можем установить максимальное значение коэффициентов полинома. Итак, если мы установим максимальное значение на 1, то мы можем легко делать бинарные вентили.Например:

  1 + 0x^1 + 1x^2 + 0x^3
+ 0 + 1x^1 + 1x^2 + 0x^3
  ____________________
  1 + 1x^1 + 0x^2 + 0x^3

Так + по существу является вентилем ИЛИ для многочленов. Но я изо всех сил пытаюсь понять * как И, особенно потому, что умножение этих полиномов мод х^п +1, куда н - степень многочленов. Так что это не простое умножение.

Почему И = *?

kelalaka avatar
флаг in
Это действительно зависит от схемы FHE. Если вы используете постоянные полиномы, то они будут равны. Кто утверждал, что это умножение? Ответ, который вы связали, говорит о конкретных, которые зашифрованы одним битом.
флаг ru
@kelalaka каким будет постоянный многочлен? И схема должна быть BFV. Если не умножение, то что?
флаг cn
Умножение чисел, которые могут быть только 0 и 1, дает 1, если все они равны 1. Что ужасно похоже на «и».
флаг ru
@CodesInChaos, но это должно быть с учетом коэффициентов и полинома, а не для самих полиномов
Рейтинг:0
флаг ng

Во-первых, обратите внимание, что BFV традиционно формулируется в терминах арифметика схемы, а не логические. Например, исходная статья имеет пространство сообщений вида $R_t := \mathbb{Z}_t[x] / (\Phi_n(x))$, куда $\Phi_n$ это $n$й циклотомический полином (когда $n$ это степень двойки это просто $х^п+1$). Это относительно важно, поскольку фундаментальные строительные блоки арифметических схем нет ИЛИ и И, но (мод. $р$ вариант) XOR и AND, который немного отличается.

Что касается ваших проблем с умножением BFV, я думаю, что вы немного неправильно читаете спецификацию BFV. Обычно (скажем, в исходный документ) пространство сообщений указано как $R_t$, которое, как упоминалось ранее, является кольцом многочленов (когда $n$ является степенью 2) $\bмод х^n+1$. Итак, чтобы наша схема шифрования была полностью гомоморфной, нам нужно, чтобы мы могли выполнять сложение и умножение пространства сообщений по шифротекстам. Это умножение пространства сообщения равно $\bмод х^n+1$$\bмод т$, но что угодно), как вы указали. Это означает, что арифметика $\bмод х^n+1$ это то, что математически требуется для того, чтобы схема была полностью гомоморфной, поэтому ожидается, что продукт будет такой формы, и это не проблема.

Конечно, разработчики приложений могут не захотеть использовать эту «забавную арифметику». Это то, что дизайнеры библиотек должны решить позже. Например, один из способов "исправить" это (что довольно наивно --- я предполагаю, что есть лучшие решения) состоит в том, чтобы кодировать сообщения только в постоянные члены полиномов. Должно быть относительно просто увидеть, что это «забавное умножение» становится стандартным умножением, когда оно ограничено постоянными полиномами.

Есть и другие вещи, которые можно было бы сделать, например, можно было бы разрешить многочлены вида $m(x) = m_0+m_1x$ если вы знаете, что мультипликативная глубина схемы, которую вы оцениваете, не превышает $\log_2 п$, или в более общем смысле $m(x) = \sum_{i =0}^p m_i x^i$ если мультипликативная глубина не более $\log_{1+p} п$. Это просто потому, что с этой границей глубины нельзя получить многочлен степени $\geq п$, поэтому тот факт, что умножение может «зацикливаться», не имеет значения. Конечно, я уверен, что есть более умные идеи о том, что можно сделать, чтобы эмулировать «стандартную» арифметику с «забавной» арифметикой, которую мы получаем, но это действительно ортогонально пониманию BFV.


Это также стоит отметить, что ваш комментарий

но это нужно по коэффициентам и по многочлену, а не по самим полиномам

похоже, вы ищете идею каноническое вложение. В частности, примерно десять лет назад было замечено, что если нам нужен тип данных, подобный массиву, $[a_0,\dots,a_n]$ с которыми можно выполнять (по слотам) арифметические операции, то коэффициенты полиномов действительно являются довольно плохим выбором. Это связано с тем, что (среди прочего) естественная операция умножения многочленов не приводит к умножению лежащих в основе коэффициентов, а свертка их. В частности, есть такое

$$(a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2) = a_0b_0+(a_0b_1+b_0a_1)x + (a_0b_2+a_1b_1+a_2b_0)x^2+(a_1b_2+a_2b_1) x^3+a_2b_2x ^4$$

В частности, никто не восстанавливает продукт $a_1b_1$. Это можно исправить, (по существу) обратившись к версии преобразования Фурье, поскольку преобразование Фурье обычно можно записать как изоморфизм

$$\mathcal{F} : (R, +,\times)\to (R, +,\ast)$$

например он «меняет местами» свертки с (по коэффициенту) умножением. Это означает, что если мы вместо этого закодируем сообщение в «каноническом вложении» (или, что то же самое, мы закодируем «преобразование Фурье» сообщения), то свертки станут поэлементным умножением (в нашем пространстве сообщений).

Однако я не верю, что первоначальная статья BFV делает это, что в зависимости от того, что вы читаете для спецификации BFV, может привести к путанице. Но я считаю, что это относительно распространенная оптимизация, и ее можно рассматривать как «просто» другую кодировку сообщений (есть и другие преимущества использования канонического встраивания, так что вы захотите повторно проанализировать протокол с точки зрения этого).

флаг ru
не могли бы вы указать мне документ с информацией об этом каноническом встраивании в BFV?
Mark avatar
флаг ng
@GuerlandoOCs Похоже, [эта статья] (https://eprint.iacr.org/2015/889.pdf) включает анализ BFV (который они просто называют FV) с точки зрения канонического встраивания, но, возможно, это не так. всеобъемлющим, как можно было бы надеяться.BFV очень похож на BGV, который имеет гораздо более четкое изложение, доступное через [Проектирование и внедрение Helib] Халеви и Шупа (https://eprint.iacr.org/2020/1481.pdf), что делает «SIMD-подобным «структура вполне очевидна (включая информацию не только о том, как получить покомпонентные операции, но и о том, как «обменять» данные между разными «слотами»)
Рейтинг:0
флаг ru

Логический элемент И представляет умножение в поле коэффициентов, которое в данном случае является двоичным полем двух элементов 0 и 1. Точно так же для этого поля сложение действует так же, как вентиль XOR.

Если мы знаем, как складывать и умножать с коэффициентами, мы можем распространить это на сложение и умножение многочленов, используя свойства арифметики. В случае сложения это просто включает сопоставление коэффициентов и сложение. В случае умножения нам нужно использовать распределительный закон. В вашем примере, написав # для XOR и & для AND, мы должны соединить коэффициенты, чьи мономы, чьи мощности в сумме дают одно и то же значение

(1 + 0x^1 + 1x^2 + 0x^3)*(0 + 1x^1 + 1x^2 +0x^3)

= (1&0) + (1&1 # 0&0)x^1 + (1&1 # 0&1 # 1&0)x^2 + (1&0 # 0&1 # 1&1 # 0&0)x^3 +

+ (0&0 # 1&1 # 0&1)x^4 + (1&0 # 0&1)x^5 + (0&0)x^6

= 0 + 1x^1 + 1x^2 + 1x^3 + 1x^4 + 0x^5 + 0x^6

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.