Усечение в гомоморфном шифровании

Question

Как реализовать усечение в библиотеках гомоморфного шифрования, таких как HELib или SEAL, когда не допускается операция деления?

У меня есть два числа с плавающей точкой a=2.3,b=1.5, которые я масштабирую до целых чисел с точностью до 2 цифр. Следовательно, мой кодировщик выглядит в основном так: encode(x)=x*10^2. Предполагая, что enc(x) является функцией шифрования, тогда enc(encode(a))=enc(230) и enc(encode(b))=enc(150).

После умножения мы получаем огромное значение a*b=enc(23*15)=enc(34500), потому что коэффициенты масштабирования тоже умножаются. Это означает, что мои входные данные растут экспоненциально, если я не могу усечь результат, так что trunate(enc(34500))=truncate(enc(345)).

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

Answer 1

Возможно, но сложно выполнить такое усечение в схемах BFV и BGV, и вряд ли приведет к приемлемой производительности в большинстве случаев использования. Эта проблема во многом связана со сложностью начальной загрузки упомянутых схем; для получения более подробной информации см. https://eprint.iacr.org/2018/067 и https://eprint.iacr.org/2014/873.

С другой стороны, в схеме CKKS намного проще добиться усечения (см. https://eprint.iacr.org/2016/421), где это естественная операция. Однако недостатком схемы CKKS является то, что все вычисления дают только приблизительно правильные результаты, которые могут не соответствовать вашим ожиданиям.