Быстрая полностью гомоморфная арифметическая схема? BFV = медленная загрузка, TFHE = медленная арифметика

Схема BFV хороша для представления множества целых чисел внутри многочлена, и мы даже можем относительно быстро оперировать с ними по отдельности. Однако загрузка на BFV невозможна, так что ни одна библиотека даже не реализует ее.

С другой стороны, такие схемы, как TFHE, имеют очень быструю загрузку, но работают на вентилях. Эта статья — самая новая, которую я смог найти, в которой найден способ кодирования целых чисел на торе: https://www.mdpi.com/2078-2489/12/8/297 но для умножения 4-битного целого числа требуется 0,9 секунды, что слишком много.На BFV я могу не только одновременно умножать лоты, но умножение занимает гораздо меньше времени (около 80 мс на одном ядре), а значение коэффициента (модуля открытого текста) может достигать более 1 миллиона. Я даже могу закодировать 64-битное число в форме RNS и умножить его в BFV на это единственное полиномиальное умножение 80 мс.

Итак, есть ли лучшая схема, которая выполняет быструю загрузку и работает с представлениями целых чисел размером в слово, а не двоичными? (или, может быть, тот, который кодирует в двоичном формате, но каким-то образом делает арифметику быстрой).

Существуют более эффективные реализации TFHE, чем та, которую вы цитируете. В частности, компания Зама имеет реализацию, которую они называют Конкретный, который включает в себя

• код Rust с открытым исходным кодом, который также упакован в ржавый «ящик», и
• ан интеграция с (частью) Numpy.

Есть некоторые бенчмарки кода Rust от ~ 2 лет назад, где они требуют ~ 30 мс для умножения. К сожалению, из этого документа мне не совсем ясно, сколько битов сообщения они требуют для эталона. Я считаю, что это $\geq 5$, а может быть только $5$. В любом случае, это, конечно, намного быстрее, чем ~ 0,9 с для 4-битного умножения.

Обратите внимание, что вы все равно потеряете качества SIMD-типа BFV. Несмотря на это, вы можете оказаться (практически) быстрее, поскольку похоже, что Concrete имеет бэкэнд с ускорением на GPU (вышеупомянутые тесты были до того, как этот бэкэнд появился), поэтому можно было бы получить аналогичную степень параллелизма, обратившись к этому.

Тем не менее, при условии, что я правильно интерпретирую тесты, это > 30-кратное ускорение по сравнению с тем, что вы цитируете (до того, как делать что-либо, связанное с графическим процессором, что теперь возможно), поэтому, вероятно, представляет интерес.

Что касается начальной загрузки BFV, криптосистема BGV имеет схожие характеристики с BFV (они обе представляют собой схемы «быстрой арифметики с SIMD + медленная начальная загрузка») и Тесты HElib содержат пример кода для начальной загрузки BGV, который может вас заинтересовать.