За пределами криптографии с открытым ключом: функциональное шифрование

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

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

Функциональное шифрование (FE), формально определённое Boneh, Sahai и Waters в 2011 году, обобщает IBE. В схеме FE центр управления ключами может создать функциональный ключ sk_f для любой функции f. Имея шифротекст Enc(x) и функциональный ключ sk_f, расшифровщик может вычислить f(x), но не узнаёт ничего об x, кроме того, что раскрывает f(x). Функция f может быть любой вычислимой функцией из класса, поддерживаемого схемой.

Функциональное шифрование для скалярного произведения позволяет расшифровщику, владеющему sk_y, вычислить скалярное произведение по шифротексту вектора x. Это обеспечивает конфиденциальный вывод в машинном обучении: можно зашифровать вектор признаков пользователя x, предоставить владельцу модели sk_y для его вектора весов y, и тот узнает только скалярное произведение (необработанный результат предсказания), не получая признаков пользователя. Существует несколько практических схем FE для скалярного произведения (ABDALLA и др., 2016).

FE для проверки равенства позволяет стороне проверить, совпадает ли зашифрованное значение с конкретным значением v, узнавая только, выполняется ли равенство. Это обеспечивает конфиденциальные запросы к базам данных: сервер хранит зашифрованные записи, а пользователь запрашивает записи, соответствующие определённым значениям, не раскрывая серверу ни содержание поиска, ни результаты, за исключением ответа «да» или «нет». В практических конструкциях используются билинейные спаривания.

Наиболее мощная форма FE поддерживает произвольные булевы или арифметические схемы в качестве функций. Расшифровщик с ключом sk_f для любой функции f, вычислимой за полиномиальное время, может вычислить f(x) по Enc(x). FE для произвольных схем была теоретически построена Garg, Gentry, Halevi, Raykova, Sahai и Waters (2013) с использованием мультлинейных отображений, однако существующие конструкции общего FE непрактичны из-за зависимости от несовершенных предположений о мультлинейных отображениях.

Обфускация неразличимости (iO) — наиболее мощный из известных криптографических примитивов, тесно связанный с функциональным шифрованием. Схема iO принимает схему C и создаёт её обфусцированную версию O(C), которая вычисляет ту же функцию, но не раскрывает ничего о C, кроме поведения на входах и выходах. Из iO следуют большинство известных криптографических примитивов, включая общее FE. Существуют конструкции-кандидаты на основе решёточных задач, но до практического применения им ещё далеко.

Шифрование на основе атрибутов (ABE) — практически реализуемая форма функционального шифрования, в которой функция f ограничена проверкой политики: f(x) = 1, если набор атрибутов x удовлетворяет политике, и 0 в противном случае. ABE обеспечивает детализированный контроль доступа, при котором права на расшифрование зависят от атрибутов пользователя. ABE — наиболее широко применяемая на практике форма функционального шифрования; её реализации используются в облачном хранилище, здравоохранении и интернете вещей.

История конструкций FE развивается от простых к более мощным: IBE (Boneh-Franklin, 2001) → FE для проверки равенства (различные конструкции 2005–2010 годов) → FE для скалярного произведения (ABDALLA, 2016) → FE для схем ограниченной глубины (на основе мультทлинейных отображений, 2013) → общее FE (предположительно следует из iO). Каждый следующий этап обеспечивает больше возможностей, но также становится более сложным и менее эффективным. На практике используется простейшая форма, обеспечивающая требуемую функциональность.

Безопасность FE определяется неразличимостью шифротекстов двух сообщений x0 и x1 даже при наличии ключей функций для произвольных функций f, если для всех запрошенных функций выполняется f(x0) = f(x1). Это гарантирует, что расшифровывающая сторона узнает в точности f(x) и больше ничего. Существуют два уровня безопасности: селективная безопасность (атакующая сторона фиксирует сообщения для проверки до того, как увидит открытый ключ) и адаптивная (полная безопасность на основе симуляции).

Общее FE пока непрактично, но FE для скалярного произведения и ABE уже можно применять на практике. К проблемам относятся необходимость доверенного центра управления ключами (единая точка отказа), сложность отзыва ключей, накладные расходы на операции спаривания и ограниченная стандартизация. Среди направлений исследований — FE с несколькими центрами управления (без единого доверенного центра), децентрализованная генерация ключей и FE для более крупных классов функций без мультilineарных отображений.

Чем функциональное шифрование отличается от традиционного шифрования с открытым ключом?

Функциональное шифрование (Boneh-Sahai-Waters, 2011) обобщает IBE, позволяя использовать ключи функций sk_f для вычисления f(x) из Enc(x) без полного раскрытия x. Существуют практические конструкции FE для скалярного произведения (вывод моделей машинного обучения с сохранением конфиденциальности) и проверки равенства. ABE — практически применяемый частный случай для проверки политик доступа. FE для общих схем требует мультilineарных отображений и непрактично. iO — наиболее мощный связанный с ним примитив. Главная задача — перейти от теории к эффективной практике.