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

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 является то, что все вычисления дают только приблизительно правильные результаты, которые могут не соответствовать вашим ожиданиям.