Схема CKKS

Схема CKKS (Cheon-Kim-Kim-Song) — это криптографическая схема полностью гомоморфного шифрования (FHE), позволяющая выполнять произвольные вычисления (сложение и умножение) над зашифрованными данными с плавающей запятой (приближёнными числами). В отличие от более ранних схем FHE, работающих с целыми числами (например, BGV, BFV), CKKS специально спроектирована для обработки вещественных чисел, что делает её особенно пригодной для задач машинного обучения и обработки сигналов, где важна точность, но допустимы небольшие ошибки округления. Схема была предложена в 2016 году группой южнокорейских исследователей: Чон Хи-су, Ким Ан-до, Ким Мён-су и Сон Ён-су.

История

Предпосылки создания

До появления CKKS существовали схемы полностью гомоморфного шифрования, такие как BGV (Brakerski-Gentry-Vaikuntanathan, 2011) и BFV (Brakerski/Fan-Vercauteren, 2012), которые работали с целыми числами по модулю большого простого числа. Однако многие практические приложения, особенно в области машинного обучения (нейронные сети, линейная регрессия, SVM), оперируют вещественными числами с плавающей запятой. Попытки эмулировать вещественную арифметику на целочисленных схемах приводили к значительному росту размеров шифротекстов и вычислительной сложности.

Публикация и развитие

Схема CKKS была впервые представлена в 2016 году на конференции ASIACRYPT. Основная инновация заключалась в том, что шифротекст кодирует не точное значение, а его приближение с контролируемой ошибкой. Это позволило значительно повысить эффективность по сравнению с целочисленными схемами для задач, где допустима небольшая погрешность. В 2018 году была предложена модификация CKKS (часто называемая CKKS с «рескейлингом»), которая улучшила управление ростом шума при умножениях. Схема быстро стала одной из самых популярных в библиотеках FHE, таких как Microsoft SEAL, HElib, PALISADE и OpenFHE.

Криптографические основы

Кольцевая структура

CKKS основана на задаче обучения с ошибками над кольцами (Ring-LWE). Работа ведётся в кольце многочленов R = Z[X]/(X^N + 1), где N — степень многочлена (обычно степень двойки, например, 2^14 или 2^15). Каждый элемент кольца — это многочлен степени меньше N с целыми коэффициентами. Сообщение (вектор вещественных чисел) кодируется в многочлен, а затем шифруется.

Кодирование и декодирование

Ключевая особенность CKKS — это способ представления вещественных чисел. Вектор из N/2 комплексных чисел (или N/2 вещественных, если использовать симметрию) кодируется в многочлен с помощью обратного преобразования Фурье (точнее, канонического вложения). При декодировании выполняется прямое преобразование, и результат получается с некоторой ошибкой, которая контролируется параметрами схемы.

Уровни и рескейлинг

Для контроля роста шума при умножениях используется техника «рескейлинга» (rescaling). После каждого умножения шифротекст «сжимается» путём деления на некоторый модуль, что уменьшает как размер шифротекста, так и накопленный шум. Это позволяет выполнять ограниченное количество умножений (глубину вычислений), задаваемое числом уровней.

Принцип работы

Генерация ключей

• Секретный ключ (sk): случайный многочлен с малыми коэффициентами (обычно из распределения с ограниченной нормой).
• Открытый ключ (pk): пара многочленов, вычисленная на основе sk и случайной ошибки. Позволяет любому зашифровать данные.
• Оценочный ключ (evk): дополнительный ключ, необходимый для выполнения умножения. Генерируется из sk.

Шифрование

Открытый текст (вектор вещественных чисел) кодируется в многочлен m. Затем шифротекст c = (c0, c1) вычисляется как: c0 = a pk[0] + m + e, c1 = a pk[1] + e' где a — случайный многочлен, e, e' — малые шумы.

Декодирование

Для расшифровки владелец секретного ключа вычисляет m' = c0 + c1 * sk, а затем декодирует полученный многочлен обратно в вектор вещественных чисел. Результат будет приближённым, с ошибкой, зависящей от параметров.

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

• Сложение: шифротексты складываются покомпонентно. Шум растёт линейно.
• Умножение: требует использования оценочного ключа и рескейлинга. Шум растёт квадратично, но рескейлинг его уменьшает.

Характеристики

Точность и шум

CKKS является приближённой схемой. Параметры (размер кольца N, модуль q, число уровней L) выбираются так, чтобы ошибка была меньше заданного порога. Типичная точность — 10–30 бит мантиссы, что достаточно для многих задач машинного обучения.

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

CKKS значительно быстрее целочисленных схем для задач с вещественными числами. Однако она всё ещё медленнее обычных вычислений (на несколько порядков). Основные затраты — умножения и рескейлинг, которые требуют быстрого преобразования Фурье (FFT). Для N=2^15 и глубины 10 умножений одно умножение шифротекстов может занимать десятки миллисекунд на современном CPU.

Безопасность

Безопасность CKKS основана на сложности задачи Ring-LWE, которая считается устойчивой к квантовым атакам (постквантовая криптография). Выбор параметров (размер кольца, модуль) должен соответствовать стандартным уровням безопасности (например, 128-битному).

Применение

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

CKKS является стандартом для гомоморфного машинного обучения. Она позволяет обучать модели на зашифрованных данных или выполнять предсказания, не раскрывая сами данные. Примеры:

• Линейная регрессия: вычисление взвешенной суммы.
• Нейронные сети: выполнение матричных умножений и активаций (например, ReLU, сигмоида) с использованием приближённых полиномов.
• Кластеризация: k-средних на зашифрованных данных.

Обработка сигналов

Фильтрация, преобразование Фурье, корреляция — все эти операции могут быть выполнены гомоморфно с помощью CKKS.

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

В сценариях, где несколько сторон предоставляют зашифрованные данные, а третья сторона выполняет вычисления, не видя данные (например, в медицинской аналитике или финансовых расчётах).

Ограничения и критика

Приближённость

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

Глубина вычислений

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

Размеры данных

Даже при сжатии шифротексты CKKS значительно больше открытых текстов (в сотни раз). Это увеличивает требования к памяти и пропускной способности сети.

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

Правильный выбор параметров (N, q, число уровней, распределение шума) требует глубокого понимания криптографии и численных методов. Неправильная настройка может привести к потере данных или к взлому.

Сравнение с другими схемами FHE

Библиотеки и реализации

• Microsoft SEAL: одна из самых популярных библиотек FHE, поддерживает CKKS (версия 3.0 и выше). Организация Microsoft признана в РФ «нежелательной»? На момент написания статьи Microsoft не внесена в реестр нежелательных организаций в РФ, но её продукты могут быть ограничены.
• HElib: библиотека IBM, поддерживает CKKS с версии 2.0.
• PALISADE / OpenFHE: открытая библиотека, активно развиваемая сообществом.
• HEAAN: оригинальная реализация авторов схемы, доступна на GitHub.

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

• Название «CKKS» образовано от первых букв фамилий авторов: Cheon, Kim, Kim, Song.
• Схема была удостоена награды за лучшую статью на ASIACRYPT 2016.
• В 2020 году была предложена модификация CKKS с поддержкой «бутстрэппинга» (bootstrapping), позволяющая выполнять неограниченное количество умножений, что снимает ограничение на глубину вычислений.
• CKKS используется в реальных проектах по конфиденциальному машинному обучению, например, в медицинских исследованиях (анализ геномных данных) и финансовых системах (кредитный скоринг).

Источники

• Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. Advances in Cryptology – ASIACRYPT 2017.
• Cheon, J. H., Han, K., Kim, A., Kim, M., & Song, Y. (2018). Bootstrapping for approximate homomorphic encryption. Advances in Cryptology – EUROCRYPT 2018.
• Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. STOC 2009.
• Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012). (Leveled) fully homomorphic encryption without bootstrapping. ITCS 2012.
• Fan, J., & Vercauteren, F. (2012). Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive.
• Microsoft SEAL documentation. (2020). Microsoft Research.
• OpenFHE documentation. (2022). OpenFHE Consortium.