Схемы BGV и BFV для операций с целыми числами

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) — многоуровневая схема FHE, основанная на RLWE. Она поддерживает произвольное число операций сложения и умножения над упакованными целочисленными открытыми текстами. «Многоуровневая» означает, что схема обрабатывает схемы вычислений фиксированной глубины L без бутстрэппинга.

BGV и BFV кодируют открытые тексты как многочлены в Z_t[x]/(x^n+1), где t — небольшой модуль открытого текста (например, t=65537). Каждый многочлен кодирует n целочисленных значений — по одному на каждый коэффициент. Арифметические операции над шифротекстами выполняются одновременно над всеми n значениями — параллелизм SIMD.

BGV уменьшает шум с помощью переключения модуля: после каждого умножения модуль шифротекста q уменьшается с Q_L до Q_{L-1}. Это делит шум на Q_L/Q_{L-1}, удерживая его в пределах, допускающих расшифрование. Глубина схемы L соответствует L уровням модуля.

BFV (Brakerski/Fan-Vercauteren, 2012) похожа на BGV, но использует другую стратегию управления шумом: инвариантность масштаба. BFV не требует переключения модуля; вместо этого после умножения она изменяет масштаб шифротекста. Схему проще реализовать; она используется в Microsoft SEAL.

С помощью китайской теоремы об остатках над кольцом открытых текстов каждый шифротекст может содержать n/2 независимых целочисленных значений — слотов. Операция сложения шифротекстов складывает все n/2 пар параллельно. Умножение перемножает все пары. Пропускная способность: n/2 операций над целыми числами на одну операцию над шифротекстом.

После умножения двух шифротекстов степени 1 результат имеет степень 2 и состоит из 3 компонентов. Релинеаризация использует ключи вычислений для преобразования результата обратно к степени 1 ценой добавления шума. Этот этап требуется после каждого умножения.

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

Вращение шифротекста циклически сдвигает n/2 слотов открытого текста. Оно полезно для сведения суммы (накопления всех слотов в одном), умножения матрицы на вектор (вращения и накопления), свёрток (сдвига и умножения). Для этого требуются ключи Галуа — предварительно вычисленные ключи вращения.

BFV при n=8192: сложение занимает около 10 µs, умножение — около 5 мс (с релинеаризацией). Бутстрэппинг, если он необходим, занимает 30–60 секунд. Для пакета из 4096 целых чисел амортизированная стоимость одного умножения составляет около 1 µs на целое число. Это непрактично для работы в реальном времени, но подходит для автономной аналитики.

При выборе n и q SEAL рекомендует n=4096 для 128-битной безопасности при Q < 2^109; n=8192 — для более сложных схем. Стандарт HE (homomorphicencryption.org) содержит таблицы параметров. Всегда используйте рекомендуемые параметры: нестандартный выбор легко может снизить безопасность.

Запросы к зашифрованной базе данных (поиск записей без расшифрования). Конфиденциальный геномный анализ (вычисление статистики над зашифрованной DNA). Зашифрованное финансовое агрегирование (суммирование зашифрованных остатков на счетах без раскрытия данных отдельных клиентов). Безопасная оценка моделей.

BGV и BFV выполняют зашифрованные арифметические операции над целыми числами с использованием RLWE. Пакетное кодирование обеспечивает параллелизм SIMD. BGV использует переключение модуля, а BFV — инвариантность масштаба. Релинеаризация восстанавливает степень после умножения. Далее: CKKS для приближённых вычислений и машинного обучения.