однослотовые операции над полностью гомоморфным полиномом SIMD

Согласно с https://eprint.iacr.org/2011/133.pdf и многих других работах существует изоморфизм между пространством многочленов и его коэффициентами. Итак, по крайней мере в схеме BFV мы можем сделать:

$$p(x) = [a_1, a_2, ..., a_3]$$ $$\phi(p(x)) = [\phi(a_1), \phi(a_2), ..., \phi(a_3)]$$

Таким образом, применение одной операции к полиному аналогично применению ко всем элементам, вроде того, как SIMD работает на процессорах. Это также раздражает автоморфизм Галуа на некоторых схемах.

Теперь предположим, что я хочу работать только со вторым элементом, поэтому каким-то образом я нахожу способ извлечь его с помощью битовой маски и, таким образом, получаю:

$$p_2(x) = [0, \phi(a_2), ..., 0]$$

Теперь я могу оперировать $p_2(x)$ модифицировать $\фи(а_2)$ однако я хочу. Есть ли способ поставить его обратно на $р(х)$ с моими доработками? Я также думаю, что некоторые операции, которые я делаю на р_2(х) может сделать другие элементы ненулевыми, что также является проблемой.

Есть простой способ сделать это. В частности, вы уже упоминали, что у вас есть процедура извлечения битовой маски. Следовательно, учитывая $р(х)$, $p_2(x)$, и $p_2'(x)$ (ваши гомоморфные операции применены к $p_2$), позволять $p_3(x)$ быть результатом применения одной и той же битовой маски к $p_2'$. Тогда нетрудно убедиться, что

$$p(x) - p_2(x) + p_3(x)$$

дает вам желаемый результат.

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

• может ли быть достаточно извлечения одной битовой маски?
• Как можно эффективно применить извлечение битовой маски?

Если слот, который вы хотите вычислить, публичный, должно быть достаточно умножить на подходящий постоянный (с коэффициентами 0/1) многочлен, что дает мультипликативные накладные расходы, равные 1, для каждого извлечения битовой маски. Частные битовые маски кажутся менее эффективными --- я могу придумать что-то, что использует $ О (п) $ умножения (но, по крайней мере, имеет глубину 1), по сути, путем вычисления умножения (зашифрованного) логического значения 0/1 для каждого индекса, чтобы «выбрать» правильные индексы, а затем добавить все в конце.

Я не знаю, как вышеизложенное сравнивается с современным уровнем техники.

Стоит также отметить, что если ваши операции на $p_2(x)$ делать нет зависит от других координат $\фи(а_я)$ (но могут просто "переписать" их), можно удалить одну из (а именно первую) операцию извлечения битовой маски. Конечно, это зависит от конкретной функции, которую вы оцениваете.