[Перевод] Забудьте о гомоморфном шифровании: теперь у нас есть функциональное шифрование

b-dbxtbizpu1ox7keddccrw2kqy.jpeg

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

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

Давайте для начала определимся, что мы имеем в виду, говоря про ФШ. Совсем недавно, в 2010 году, Дэн Боне, Амит Сахай и Брент Уотерс формализовали понятие ФШ. Примерно ФШ можно описать так: это схема шифрования с публичным ключом, где разные ключи для расшифровки позволяют пользователю узнавать об определённых функциях зашифрованных данных.
Так, в схеме ФШ для функции F (·, ·) шифрователь с мастер-ключом генерирует ключ sk, позволяющий вычислять функцию F (k, ·) от зашированных данных так, что расшифровщик, зная зашифрованный текст c от данных x и ключа sk, способен вычислить F (k, x), не имея возможности узнать что-либо кроме результата вычисления функции по x.

ФШ против ПГШ


Если вы знакомы с концепцией ПГШ, интересно будет провести следующую параллель:

При помощи ПГШ можно вычислять любые функции от зашифрованных данных, не расшифровывая эти данные. Это интересная возможность делегирования вычислений третьим лицам, не имеющим доверия. Минус подхода состоит в том, что результат получается тоже зашифрованным, и для его расшифровки нужно отправлять его владельцу приватного ключа. Процесс ПГШ можно представить следующим образом, где E — схема шифрования, а F — функция, которую мы хотим вычислить от зашифрованных данных:

E (x_1), E (x_2), …, E (x_n) → E (F (x_1, x_2, · · ·, x_n))

С другой стороны, с ФШ результат напрямую доступен нам сразу после вычислений, то есть, нам доступно следующее:

E (x_1), E (x_2), · · ·, E (x_n) → F (x_1, x_2, · · ·, x_n)

В каком-то смысле, ФШ — это схема, одновременно рассчитывающая и расшифровывающая результат, без утечек приватного ключа и любой информации об x1, x2, · · ·, xn кроме самого результата вычисления.

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

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

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

Возвращаемся к ФШ


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

Хотя схемы ФШ ещё очень молоды, с 2010 года произошло много всего, и уже существует довольно много интересных схем, позволяющих делать такие вещи, которые 8 лет назад казались очень сложными. Дошло уже до того, что на определённых криптографических конференциях организовываются доклады по ФШ!

Давайте посмотрим на несколько различных типов схем ФШ. К примеру:

  • Функциональное шифрование со скалярным произведением (ФШСП), где открытый текст — это вектор, а зашифрованные данные вместе с ключом можно использовать для вычисления скалярного произведения этого вектора с другим. ФШСП есть несколько вариантов: на много клиентов, на много входов, децентрализованное, со скрытием функции, и т.п.
  • Шифрование на основе атрибутов (ШОА), где зашифрованные данные связываются с набором атрибутов и секретных ключей вместе с определёнными правилами, контролирующими, какой зашифрованный текст можно зашифровать, в зависимости от имеющихся у нас атрибутов.
  • ФШ «общего назначения», позволяющее вычислять функцию f любого вида от зашифрованных данных Enc (x).


Однако тут важно отметить, что хотя уже была проделана большая работа, концентрирующаяся на теоретических аспектах ФШ, чтобы развить эту область как можно сильнее, все ФШ общего назначения на сегодня слишком малоэффективны для практического использования. Это одна из тем исследований проекта FENTEC (европейской исследовательской программы Functional Encryption Technologies): доведение ФШ до практической применимости путём проектирования и внедрения практических схем, которые можно было бы использовать в индустриальных масштабах. В этом проекте не только разрабатываются новые схемы с более богатой функциональностью, но и специальные сопроцессоры, способные ещё сильнее ускорить требуемые вычисления — всё, чтобы приблизить теорию к практике. Подробнее об этом оборудовании можно почитать в посте в блоге проекта FENTEC.

Хотите использовать ФШ уже сегодня? Пожалуйста, используйте


Но что, если вы хотите использовать ФШ уже сегодня? С этим не должно быть проблем! В рамках проекта FENTEC команда из XLAB занята реализацией множества схем, разработанных партнёрскими университетами, в виде C-библиотеки CiFEr и Go-библиотеки GoFE.

Можно подробнее почитать о библиотеках в блоге FENTEC, или же отправиться прямо на Github и начать играться с библиотеками CiFEr и GoFE. Кстати, мы проверяли, они работают даже в браузере через WASM!

В Github-репозитории проекта есть даже несколько примеров:

  • Управление доступом к медицинским данным при помощи шифрования на основе атрибутов: github.com/fentec-project/Selective-Access-to-Clinical-Data
  • Как ФШ со скалярным произведением помогает создавать совершенно анонимную «тепловую карту» расположения пользователей: github.com/fentec-project/FE-anonymous-heatmap
  • Как квадратичное ФШ позволяет проводить машинное обучение на помощи зашифрованных данных, и вести оптическое распознавание рукописных цифр, не раскрывая самих этих цифр: github.com/fentec-project/neural-network-on-encrypted-data


Все ужасные подробности: что внутри у схемы ФШ


Среди уже реализованных схем можно найти множество схем под названием «функциональное шифрование со скалярным произведением». Но что означает это название? Его следует понимать буквально: эти схемы позволяют третьим лицам вычислять результат скалярного произведения двух векторов при помощи ФШ.

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

В данном случае центральный орган выдаёт «публичный мастер-ключ» mpk, а также расчётный ключ zy для данного вектора y. Затем любой, кому известен публичный ключ, может зашифровать вектор a, позволяя любым третьим лицам, имеющим у себя ключ zy, вычислить , имея Empk (a), и ничего не зная о самом векторе a.

Отметим, что в данной схеме ФШ вектор y, соответствующий вычислительному ключу zy, должен быть известен третьему лицу для вычисления скалярного произведения. То есть секретом остаётся только вектор a.

Что, если вы захотите, чтобы оба вектора, a и y оставались секретом, но при этом чтобы третьи лица могли вычислить их скалярное произведение?

К счастью, эта область исследований также совершила серьёзные прорывы в последние годы. Она известна под названием «ФШ со скрытием функций». По сути, схема шифрования скалярного произведения «скрывает функции», если ключи и зашифрованный текст не выдают дополнительной информации по поводу векторов a и y, кроме их скалярного произведения . В новых схемах с ФШ всё чаще встречается скрытие функций (1, 2, 3).

Подводя итоги


Хотя функциональное шифрование и появилось недавно, мы уже можем представить себе множество вариантов его использования в будущем. Особенно интересный — возможность передавать процесс принятия решений, основанный на сквозном шифровании данных, от систем бэкенда на некие шлюзовые системы в сложных сетях. Мы называем это «локальным принятием решений», и подобная возможность — это большой шаг в направлении создания безопасных сетей для «интернета вещей» и других сильно децентрализованных сетей, которые захотят внедрить сквозное шифрование, не слишком теряя способность принимать решения на уровне шлюзов.

Сейчас мы работаем над прототипом продукта, который, используя ФШ со скалярным произведением, способен обнаруживать движение в видеопотоке, идущем от камеры к бэкенд-системе, на уровне шлюза, с использованием т.н. «векторов движения», входящих в стандарт H.264/MPEG-4 AVC.

cb3f1287d2fdbc789f9679001b0312de.png
Визуализация векторов движения в кадре при кодировании H.264 открытого короткометражного мультфильма Big Buck Bunny

Обратите внимание, насколько вектора движения хороши как кандидаты для применения в схемах с ФШ со скалярным произведением — ведь скалярное произведение определяется на векторных пространствах! Мы всё ещё ищем наилучшие варианты методов определения движения, и надеемся получить полностью рабочий прототип, использующий ФШ для распознавания движения, к концу 2020 года.

© Habrahabr.ru