Функциональное шифрование

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

История и предпосылки

Проблема контроля доступа

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

Истоки и развитие

Концепция функционального шифрования была впервые формализована в 2005 году в работе Амита Сахая и Брента Уотерса (Amit Sahai, Brent Waters) как обобщение более ранних идей атрибутного шифрования (Attribute-Based Encryption, ABE) и шифрования с поиском (Searchable Encryption). В 2008 году Боно, Гарг, Сахай и Уотерс (Boneh, Garg, Sahai, Waters) представили первую общую конструкцию функционального шифрования, основанную на мультилинейных отображениях. Однако практические реализации долгое время оставались неэффективными.

Значительный прорыв произошёл в 2013 году, когда Гарг, Джентри, Халеви и Сахай (Garg, Gentry, Halevi, Sahai) построили первую схему функционального шифрования для всех полиномиальных функций, используя теорию решёток и гомоморфное шифрование. С тех пор исследования сосредоточены на повышении эффективности, снижении размера ключей и шифротекстов, а также на построении схем для конкретных классов функций.

Основные понятия и определения

Формальное определение

Функциональное шифрование (ФШ) — это схема шифрования, состоящая из четырёх алгоритмов:

1. Setup (1^λ, F) — алгоритм генерации параметров. На вход подаётся параметр безопасности λ и описание класса функций F. Выдаёт мастер-секретный ключ (MSK) и открытый ключ (PK).
2. Encrypt (PK, x) — алгоритм шифрования. На вход принимает открытый ключ PK и открытый текст x. Выдаёт шифротекст CT.
3. KeyGen (MSK, f) — алгоритм генерации ключа для функции. На вход принимает мастер-секретный ключ MSK и описание функции f ∈ F. Выдаёт ключ для функции SK_f.
4. Decrypt (SK_f, CT) — алгоритм расшифрования. На вход принимает ключ для функции SK_f и шифротекст CT. Выдаёт f(x) — результат применения функции f к открытому тексту x.

Свойства безопасности

• Семантическая безопасность: противник, не имеющий ключей для функций, не может получить никакой информации об открытом тексте x, кроме его длины.
• Безопасность от коллюзий (collusion resistance): даже если несколько злоумышленников объединят свои ключи SK_f1, SK_f2, ..., они не смогут вычислить f(x) для любой функции f, на которую у них нет отдельного ключа. Это ключевое свойство, отличающее ФШ от более простых схем.
• Индифферентность (indistinguishability): противник, имеющий ключи для некоторых функций, не может отличить шифротекст для x0 от шифротекста для x1, если f(x0) = f(x1) для всех функций f, на которые у него есть ключи.

Виды функционального шифрования

Шифрование на основе атрибутов (Attribute-Based Encryption, ABE)

Наиболее распространённый подкласс ФШ. В ABE шифротекст и ключ пользователя связаны с наборами атрибутов (например, «должность: директор», «отдел: финансы»). Расшифрование возможно, если набор атрибутов удовлетворяет заданному логическому условию (политике доступа).

• Шифрование с политикой на ключе (Key-Policy ABE, KP-ABE): политика доступа встраивается в ключ пользователя, а атрибуты — в шифротекст. Пользователь может расшифровать данные, если его политика выполняется для атрибутов шифротекста.
• Шифрование с политикой на шифротексте (Ciphertext-Policy ABE, CP-ABE): политика доступа встраивается в шифротекст, а атрибуты — в ключ пользователя. Это более интуитивная модель: владелец данных сам решает, кто может их прочитать.

Внутреннее функциональное шифрование (Inner-Product Encryption, IPE)

Позволяет вычислить скалярное произведение двух векторов: зашифрованного вектора x и вектора y, связанного с ключом. Результат — значение ⟨x, y⟩. IPE используется для построения схем проверки подлинности, поиска по зашифрованным данным и вычисления взвешенных сумм.

Шифрование с поиском (Searchable Encryption, SE)

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

Полное функциональное шифрование (Full Functional Encryption)

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

Применение

Облачные вычисления и базы данных

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

Управление доступом и конфиденциальность

В системах электронного здравоохранения ФШ позволяет врачу получить доступ только к тем медицинским записям пациента, которые относятся к его специальности, а не ко всей истории болезни. В корпоративных системах — предоставить сотруднику отдела кадров доступ к данным о зарплате, но не к коммерческой тайне.

Анализ данных и машинное обучение

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

Анонимные учётные записи и голосование

В системах электронного голосования ФШ позволяет проверить, что голос избирателя принадлежит определённому кандидату (функция проверки), не раскрывая сам голос.

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

Вычислительная сложность

Большинство практических схем ФШ, особенно для сложных функций, требуют значительных вычислительных ресурсов. Размер ключей и шифротекстов может быть очень большим (от нескольких килобайт до мегабайт), что ограничивает их применение в устройствах с ограниченными ресурсами (IoT, смарт-карты).

Ограниченность классов функций

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

Проблема управления ключами

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

Отсутствие стандартизации

На 2024 год функциональное шифрование не стандартизировано (в отличие от AES, RSA или ECC). Существуют научные прототипы и библиотеки (например, библиотека от IBM на основе CP-ABE), но нет широко принятых промышленных стандартов. Это затрудняет внедрение в коммерческие продукты.

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

• Термин «функциональное шифрование» ввёл в 2005 году Амит Сахай, который в 2018 году получил премию Гёделя за работы по криптографии.
• Первая общая конструкция ФШ для всех функций была построена только в 2013 году, через 8 лет после формализации понятия.
• Некоторые схемы ФШ основаны на математических проблемах, которые считаются устойчивыми к квантовым атакам (например, на решётках), что делает их потенциально квантово-устойчивыми.
• В 2020 году группа исследователей из Массачусетского технологического института (MIT) продемонстрировала прототип системы ФШ для анализа медицинских данных, который работал в 1000 раз быстрее предыдущих аналогов.

Источники

1. Sahai, A., & Waters, B. (2005). Fuzzy identity-based encryption. Advances in Cryptology – EUROCRYPT 2005.
2. Boneh, D., Garg, S., Sahai, A., & Waters, B. (2008). Functional encryption: definitions and challenges. Theory of Cryptography Conference (TCC).
3. Garg, S., Gentry, C., Halevi, S., & Sahai, A. (2013). Attribute-based encryption for circuits from multilinear maps. Advances in Cryptology – CRYPTO 2013.
4. Katz, J., & Lindell, Y. (2014). Introduction to Modern Cryptography (2nd ed.). CRC Press. (Глава 12: Functional Encryption).
5. Boneh, D., & Shoup, V. (2023). A Graduate Course in Applied Cryptography. (Раздел 9: Functional Encryption).