Опубликовано в Schneier on Security[link1]
© Брюс Шнайер
Перевод © 2009 unknown[link2]

Прорыв в гомоморфном шифровании


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

Гомоморфные криптосистемы – это те, в которых математические операции над шифртекстом приводят к определённым эффектам над открытым текстом. Обычный симметричный шифр — DES, AES или какой-либо ещё — не является гомоморфным. Допустим мы имеем открытый текст P и мы зашифруем его с помощью AES, чтобы получить соответствующий шифртекст C. Если вы умножите этот шифртекст на 2, а затем расшифруете 2C, вы получите случайные данные вместо P. Если вы получите что-либо иное, наподобие 2P, это бы говорило о сильно неслучайных свойствах AES, так что больше бы никто не стал доверять его безопасности.

Алгоритм RSA отличается. Зашифруйте P для получения C и умножьте C на 2, а затем расшифруйте 2C — и вы получите 2P. Это гомоморфизм: при осуществлении некоторых математических операций над шифртекстом получается отражение этих операций в открытом тексте. Алгоритм RSA гомоморфен по отношению к умножению, такие вещи необходимо принимать во внимание при оценки безопасности систем защиты, использующих RSA.

В этом нет ничего нового. Гомоморфизм RSA был известен с 1970 годов и другие алгоритмы, являющиеся гомоморфными по отношению к сложению были известны с 1980-х годов. Но вот то что ускользало от криптографов – это полностью гомоморфная криптосистема: которая была бы гомоморфна и по сложению и по умножению и при этом всё ещё оставалась бы безопасной. И это то, что открыл исследователь из IBM Крэйг Джентри.

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

К сожалению — вы ведь уже знаете, что сейчас последует, правда? — Схема Джентри полностью непрактична. Она использует кое-что, называемое идеальной решёткой, как основу этой системы шифрования и оба параметра — и размер шифртекста, и сложность операций зашифрования и расшифрования растут с огромными значениями в зависимости от количества операций, которое вам необходимо выполнить над шифртекстом — и это количество нуждается в том, чтобы быть фиксированным. А конвертирование компьютерной программы, включая простейшую, в булеву цепь потребует огромного количества операций. И эта непрактичность не из тех, которые могут быть решены тонкими оптимизационными техниками или несколькими витками закона Мура; это врождённое ограничение алгоритма. В одной статье Джентри оценивает, что производительность одного поискового запроса в Google с зашифрованным словом — совершенно разумное простое применение алгоритма — потребует увеличения времени вычислений в триллион раз. Закон Мура предсказывает, что пройдёт 40 лет, прежде чем гомоморфный поиск станет также эффективен, как поиск сегодня, и я думаю, что это слишком оптимистично даже для такого простейшего примера.

Невзирая на это, пиар-машина IBM грузит всех этим открытием. Их пресс-релизы вынуждают озвучивать это, как если бы новая гомоморфная схема перепишет все принципы бизнеса вычислений: не только облачных вычислений, но "позволит создавать фильтры идентифицирующие спам, даже в зашифрованной почте или осуществлять защиту информации, содержащейся в электронных медицинских картах". Может быть, когда-нибудь, но не в моей жизни.

Ничто из этого никак не умаляет ничего из открытия Джентри. Образы полностью гомоморфной криптосистемы витали в головах криптографов в течении тридцати лет. Я никогда не ожидал увидеть ни одной. Пройдут годы, пока достаточное число криптографов изучит алгоритм и мы можем быть уверенными в какой-либо степени, что данная схема безопасна, но — отвратительно плохая с практической стороны дела — и это лишь удивительная часть работы.

Ссылки
[link1] http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html

[link2] https://www.pgpru.com/proekt/poljzovateli?profile=unknown