Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Компания IBM опубликовала на GitHub исходный код набора инструментов FHE для Linux. Утилиты работают на платформах IBM Z и x86, поддерживаются Ubuntu, Fedora и CentOS.
Полностью гомоморфное шифрование (FHE) долгое время считалось чем-то вроде чаши святого Грааля в криптографии. Задача действительно казалась нереальной. Тип шифрования FHE предполагает манипуляции зашифрованными данными третьей стороной без возможности расшифровки самих данных или результата манипуляций.
Как такое возможно?
В качестве простого примера представьте, что у вас есть набор электронных писем, и вы хотите использовать сторонний спам-фильтр, чтобы проверить, являются ли они спамом. Спам-фильтр работает на сервере, потому что разработчик старается сохранить конфиденциальность своего алгоритма: либо скрывает исходный код, либо спам-фильтр зависит от очень большой базы данных, которую они не хотят раскрывать публично, так как это облегчает атаку, либо и то, и другое. Неважно, главное, что спам-фильтр в любом случае работает на сервере — и вы никак не можете запустить его у себя. Что делать в такой ситуации? Вы тоже заботитесь о конфиденциальности своих данных и не хотите передавать третьим лицам содержание электронных писем в открытом, незашифрованном виде. Здесь на выручку приходит полностью гомоморфное шифрование:
Таким образом, сервис хранит в секрете алгоритм, а вы храните в секрете свои данные. Но FHE позволяет успешно применять алгоритм на этих данных, так что ни одна сторона на узнаёт секреты другой.
Полностью гомоморфное шифрование имеет множество применений, в том числе и в блокчейне, где сервер может манипулировать зашифрованными данными клиента без раскрытия содержимого информации. То есть сервер может выполнять запросы клиента, не зная, что он запросил.
Другие варианты применения гомоморфного шифрования:
- Более эффективные протоколы скрытых адресов и более общие решения масштабируемости для протоколов сохранения конфиденциальности, которые сегодня требуют от каждого пользователя лично сканировал весь блокчейн на предмет входящих транзакций.
- Обмен данными с сохранением конфиденциальности, которые позволяют пользователям выполнять некоторые конкретные облачные вычисления над своими данными, сохраняя при этом полный и единоличный контроль над ними.
- Как компонент более мощных криптографических примитивов, таких как более эффективные протоколы конфиденциальных вычислений (двусторонняя версия иллюстрируется классической задачей миллионеров, в которой два миллионера хотят выяснить, кто из них богаче, не разглашая точную сумму своего благосостояния).
Вообще, существуют различные виды гомоморфного шифрования, некоторые более мощные, чем другие. Они отличаются тем, какие операции можно произвести с зашифрованными данными.
Частично гомоморфное шифрование позволяет произвести только одну операцию с зашифрованными данными: либо сложение, либо умножение
Отчасти гомоморфное шифрование (somewhat homomorphic) полноценно работает только на ограниченном наборе данных.
Наконец, полностью гомоморфное шифрование позволяет неограниченные операции сложения и умножения на любом массиве данных.
Реализовать частичное гомоморфное шифрование довольно легко: например, умножение реализовано в RSA:
, , так что
Эллиптические кривые предлагают аналогичный вариант со сложением. А вот реализовать одновременно и сложение, и умножение гораздо сложнее. Поиски такой схемы продолжались с 1978 года, когда Ривест, Адлеман и Дертузос сформулировали задачу и ввели термин «гомоморфное шифрование». В течение 30 лет существование полностью гомоморфных систем не было доказано, а сам Ривест решил, что идея не подлежит реализации.
Серьёзный прорыв произошёл только в 2009 году после публикации кандидатской диссертации стэнфордского аспиранта Крейга Джентри. Он описал возможную конструкцию полностью гомоморфной криптосистемы на идеальных решётках. В диссертации он также предложил инновационную идею бутстраппинга. Этот трюк превращает схему частичного FHE в схему полностью гомоморфного шифрования. Метод бутстраппинга изображён на диаграмме ниже. Если вкратце, то здесь биты секретного ключа шифруются публичным ключом в гомоморфной схеме и публикуются как «бустрапперский ключ», что позволяет исполнить гомоморфное шифрование на перешифрованном шифротексте, в котором шум уменьшается до размеров исходного. То есть мы «освежаем» шифротекст, как бы стирая ошибку старого ключа.
Проще выражаясь, процедура расшифровки сама по себе является вычислением, поэтому может быть реализована как гомоморфная схема, которая принимает на входе биты шифротекста и биты секретного ключа.
Криптографическая схема Джентри стала серьёзным прорывом, но вводила новую ошибку, которая не зависит от количества ошибки в исходном шифровании. Сам автор описал сложное решение проблемы, но более удачной стала доработанная схема Бракерски и Вайкунтанатана, предложенная в 2011 году (схема получила название BGV (Бракерски-Гентри-Вайкунтанатан). В 2013 году IBM выпустила свободную криптографическую библиотеку HELib с поддержкой гомоморфного шифрования и схемы BGV. В январе 2020 года вышла версия HELib 1.0.0.
В 2013 году Джентри снова заявил о себе. С соавторами Сахаи и Уотерсом и представил схему полного гомоморфного шифрования третьего поколения — схему GSW (Gentry, Sahai, Waters), которая опять использует криптографию на решётках и бустраппинг.
За годы разработки на базе HELib создан полноценный набор инструментов с интегрированными образцами для IDE, которые работают сразу «из коробки».
Ранее IBM уже выпустила инструменты полностью гомоморфного шифрования для MacOS и iOS. В перспективе обещает опубликовать исходный код версии для Android.
Версия для Linux выпущена скорее в демонстрационных целях и работает на базе данных с европейскими странами и их столицами (второй пример для финансовой отрасли представляет собой распознавание фрода нейросетью на зашифрованной базе анонимных транзакций). До практического применения гомоморфного шифрования пока дело не дошло. По оценке самого Джентри в 2009 году, например, обработка поискового запроса в Google в случае, если текст зашифрован, потребует примерно в триллион раз больше вычислений. Тем не менее, сделанные IBM оптимизации позволили существенно повысить производительность библиотеки, так что через несколько лет или десятилетий, она вполне может найти широкое применение в веб-приложениях. IBM заявляет, что уже сейчас библиотеку можно запускать на мейнфреймах IBM Z.
