Схема BGV

Схема BGV — это криптографическая конструкция полностью гомоморфного шифрования (FHE), предложенная в 2011 году Звикой Бракерски, Крейгом Джентри и Вайкунтанураманом Вайкунтанатаном (Vaikuntanathan). Она позволяет выполнять произвольные вычисления над зашифрованными данными без их расшифровки, что делает её одной из основополагающих схем в области гомоморфного шифрования. BGV основана на решётчатых криптосистемах и использует технику «бустрапинга» (bootstraping) для обеспечения неограниченной глубины вычислений.

История

Развитие гомоморфного шифрования началось с пионерской работы Крейга Джентри в 2009 году, который впервые предложил полностью гомоморфную схему, основанную на идеальных решётках. Однако его конструкция была крайне неэффективной для практического применения. В 2011 году Бракерски, Джентри и Вайкунтанатан представили схему BGV, которая значительно улучшила производительность за счёт использования обучения с ошибками (Learning With Errors, LWE) и его кольцевого варианта (Ring-LWE). В 2012 году те же авторы совместно с Адитьей Ачарья опубликовали реализацию библиотеки HELib, которая стала одной из первых практических реализаций FHE.

Основные принципы

Гомоморфное шифрование

Гомоморфное шифрование позволяет выполнять операции над зашифрованными данными так, что результат расшифровки соответствует результату тех же операций, выполненных над открытыми данными. Формально, для схемы шифрования (Enc, Dec) с операциями ⊕ и ⊗ над шифротекстами должно выполняться:

• Dec(Enc(a) ⊕ Enc(b)) = a + b
• Dec(Enc(a) ⊗ Enc(b)) = a × b

Схема BGV поддерживает как сложение, так и умножение, что позволяет реализовать любые булевы или арифметические схемы.

Решётчатая криптография

BGV основана на сложности задачи LWE, которая считается устойчивой к атакам с использованием квантовых компьютеров. В схеме используются кольцевые многочлены над кольцом R = Z[x]/(f(x)), где f(x) — обычно круговой многочлен. Секретный ключ представляет собой случайный многочлен с малыми коэффициентами, а шифротекст — пару многочленов, один из которых содержит «шум».

Управление шумом

Ключевая проблема всех гомоморфных схем — накопление шума при выполнении операций. Каждое умножение значительно увеличивает шум, и при превышении определённого порога расшифровка становится невозможной. BGV решает эту проблему с помощью двух механизмов:

• Модульная редукция (modulus switching): уменьшение размера модуля шифротекста для снижения шума.
• Бустрапинг (bootstraping): повторное шифрование шифротекста с использованием секретного ключа, что позволяет «обнулить» шум и продолжить вычисления.

Устройство схемы

Параметры

Схема BGV задаётся набором параметров:

• q — модуль шифрования (большое целое число, обычно степень двойки).
• n — размерность решётки (степень кольцевого многочлена).
• σ — стандартное отклонение распределения ошибок (обычно около 3.2).
• t — модуль открытого текста (обычно небольшое простое число, например 2).

Ключи

• Секретный ключ (sk): многочлен s ∈ R с коэффициентами из множества {-1, 0, 1}.
• Открытый ключ (pk): пара (a, b), где a — случайный многочлен, а b = a·s + 2e (e — малый шумовой многочлен).

Шифрование

Для шифрования сообщения m ∈ R_t (открытый текст) выбирается случайный многочлен r с малыми коэффициентами, и вычисляется шифротекст:

• c0 = b·r + m + 2e1
• c1 = a·r + 2e2

где e1, e2 — малые шумовые многочлены.

Дешифрование

Расшифровка выполняется как:

• m = (c0 + c1·s) mod q mod 2

Гомоморфные операции

• Сложение: (c0+c0', c1+c1') — даёт шифротекст суммы.
• Умножение: требует тензорного произведения шифротекстов, что увеличивает размерность. Для уменьшения размерности используется процедура релинеаризации (relinearization), которая преобразует тройку (c0, c1, c2) обратно в пару (c0', c1').

Применение

Конфиденциальные вычисления

BGV позволяет выполнять вычисления над зашифрованными данными без их раскрытия. Это востребовано в:

• Медицине: анализ медицинских записей без доступа к личным данным пациентов.
• Финансах: обработка транзакций и кредитных историй без раскрытия конфиденциальной информации.
• Облачных вычислениях: выполнение запросов к зашифрованным базам данных.

Машинное обучение

Схема BGV используется для обучения нейронных сетей на зашифрованных данных, что позволяет сохранять конфиденциальность как обучающих данных, так и модели. В 2018 году исследователи из Microsoft Research продемонстрировали обучение простой нейронной сети на зашифрованных данных с использованием BGV.

Электронное голосование

BGV может применяться для подсчёта голосов без расшифровки отдельных бюллетеней, что обеспечивает тайну голосования и проверяемость результатов.

Критика и ограничения

Производительность

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

Размер шифротекста

При выполнении гомоморфных умножений размер шифротекста может увеличиваться, что требует дополнительной памяти и пропускной способности сети. Хотя релинеаризация частично решает эту проблему, она также добавляет вычислительные накладные расходы.

Сложность реализации

Правильная реализация BGV требует глубокого понимания решётчатой криптографии и теории чисел. Ошибки в выборе параметров могут привести к уязвимостям или неработоспособности схемы.

Реализации

HELib

Библиотека HELib, разработанная авторами BGV, является одной из наиболее известных реализаций. Она поддерживает как BGV, так и другие схемы FHE, и включает оптимизации для работы с кольцевыми многочленами.

SEAL

Библиотека Microsoft SEAL (Simple Encrypted Arithmetic Library) реализует схему BGV и её вариант CKKS (для приближённых вычислений). SEAL широко используется в академических исследованиях и промышленных проектах.

PALISADE

Библиотека PALISADE (ныне OpenFHE) включает реализацию BGV с поддержкой многопартийных вычислений и бустрапинга.

Интересные факты

• Схема BGV названа по первым буквам фамилий её авторов: Бракерски, Джентри, Вайкунтанатан.
• В 2012 году работа по BGV получила награду «Best Paper Award» на конференции CRYPTO.
• BGV является одной из немногих схем FHE, которая была реализована в аппаратном обеспечении (FPGA) для ускорения вычислений.
• В 2020 году исследователи из IBM продемонстрировали выполнение гомоморфного умножения на BGV за 0.1 секунды на стандартном процессоре, что значительно быстрее ранних реализаций.

Источники

• Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2011). Fully Homomorphic Encryption without Bootstrapping. Cryptology ePrint Archive.
• Gentry, C. (2009). Fully Homomorphic Encryption Using Ideal Lattices. STOC 2009.
• Halevi, S., & Shoup, V. (2014). Algorithms in HElib. CRYPTO 2014.
• Microsoft Research. (2015). SEAL: Simple Encrypted Arithmetic Library.
• OpenFHE. (2021). PALISADE: A Lattice-based Cryptography Library.