Думаю, многие уже знакомы с понятием гомоморфного шифрования и знают об открытии первой полностью гомоморфной криптосистемы (Fully homomorphic cryptosystem) Крэгом Джентри в 2009-ом году. Последние годы весь интернет полнится новостями по этой теме, преимущественно англоязычные ресурсы. А на русскоязычных сайтах по-прежнему не так много информации, особенно, касающейся применения этого новшества. В этой статье хотелось бы рассказать, как использование гомоморфного шифрования может быть полезно в различных областях.
Идея и история гомоморфизма достаточно просто и понятно описаны на хабре в следующих статьях: раз, два, поэтому здесь останавливаться на них не будем, а сразу перейдем к делу. Начнем, пожалуй, с самых простых примеров.
Облачные системы (cloud systems, cloud computing)
Облачные системы — удаленные системы хранения данных и сервисы, позволяющие производить обработку этих данных. Вещь интересная и получающая довольно широкое распространение. Конечно же, для защиты информации предоставляются определенные криптографические механизмы. Однако почти сразу обнаруживается один недостаток таких систем: для модификации удаленных данных необходима передача по сети секретного ключа, т.е. попросту его раскрытие, что ставит безопасность под угрозу
Представим себе следующую ситуацию: некий облачный сервер содержит информацию о наших доходах, данные с него периодически обрабатываются налоговым сервисом, высчитывая таким образом сумму налога. Но для выполнения подсчетов сервис должен иметь доступ к расшифрованной информации, что вынуждает нас передавать ему секретный ключ по каналам связи. Не проще ли было бы использовать средства, позволяющие оперировать зашифрованными данными так же, как и открытыми? Существуют ли такие средства? Ответ — да, и это — гомоморфное шифрование.
Электронное голосование (electronic voting)
Криптография нынче нашла широкое применение в системах голосования, отличными примерами того являются биткойны и слепые подписи. Но в этой части статьи, конечно же, речь пойдет о том, как гомоморфное шифрование может помочь в проведении процедуры коллективного выбора.
Пускай переда нами стоит задача выбора, например, лучшей статьи по криптографии на хабре. Имеется набор кандидатов, из которых формируется список, который включается в бюллетень. Инициатор голосования владеет криптосистемой, которая обладает гомоморфными свойствами относительно, например, операции сложения (предположим, что операции сложения и умножения на открытых текстах соответствует тем же операциям на шифртекстах), и распространяет среди избирателей открытый ключ вместе с бюллетенями. Итак, мы имеем:
— бюллетень как вектор (К1, К2, ..., Кn)
— открытый ключ — ОК
Тогда каждый из избирателей составляет вектор предпочтения — (П1, П2, ..., Пn), где каждое Пi ∈ {0, 1}, после чего шифрует каждый элемент из него и отправляет список зашифрованных нулей и единиц инициатору голосования. Последнему для подсчета голосов остается всего лишь сложить соответствующие элементы полученных массивов и произвести расшифровку. В силу гомоморфности криптосистемы инициатора индекс максимального элемента результирующего вектора и будет индексом победившего кандидата.
Это самая простая схема голосования с использованием гомоморфного шифрования, возможны, конечно, ее модификации. Попытки придраться сразу же рождают вопросы типа: а как обеспечить целостность передаваемых бюллетеней? (первым приходящим на ум решением этой проблемы есть подписывание голосов). Думаю, можно еще найти проблемные места, но не стоит на них останавливаться.
Тем не менее, описанная процедура позволяет поддерживать конфиденциальность выбора участников, довольно проста и может использоваться для организации голосования по сети, что представляет собой немалый плюс.
Поиск без раскрытия (private information retrieval)
Так сложилось, что человеку необходимо работать с информацией: уметь производить её поиск, обработку, усваивание, решать вопросы, связанные с хранением. К счастью, на сегодняшний день имеется много сервисов, упрощающих жизнь в этом отношении и помогающих преодолевать некоторые трудности. Однако они могут не всегда соответствовать требованиям клиентов. Например, не все поисковые системы на данный момент поддерживают приватный поиск — т.е. поиск, при котором поисковый сервер ничего не знает о том, какие запросы присылают ему пользователи. Хотя такая вещь очень бы понадобилась людям, желающим сохранить конфиденциальность своих интересов.
Самым тривиальным решением вышеописанной проблемы была бы передача всех данных с сервера пользователю. Тогда владелец базы точно не узнает, что именно нужно запрашивающему. Но а что, если данных много? Если их еще нужно шифровать? Сжимать? Появляются серьезные проблемы, связанные с временем и ресурсами. Но тут нам приходит на помощь гомоморфное шифрование.
Для простоты давайте предположим, что на каком-то сервере хранится n-битный вектор x, а клиенту необходимо узнать i-ый бит, да так, чтоб его запрос был конфиденциален. Идея очень проста, как и все гениальное. Пользователь отсылает серверу зашифрованный бинарный вектор, каждый бит которого — зашифрованный нуль (естественно, с помощью гомоморфного алгоритма), кроме i-го бита. На сервере тогда выполняется скалярное умножение полученного вектора на x. Результат передается клиенту, который просто расшифровывает пришедшие данные и получает ответ на свой запрос.
Источники
1) D. S. Maimut, A. Patrascu, E. Simion. Homomorphic encryption schemes and applications for secure digital world // JMEDS – 2012 — №4.
2) M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan Fully homomorphic encryption over the integers // In Proc. of Eurocrypt, volume 6110 of LNCS – 2010 – 28 p.
Автор: clex
