научная статья по теме РОГОВЫЕ СИСТЕМЫ ГОМОМОРФНОГО ШИФРОВАНИЯ И ЗАЩИТА ИНФОРМАЦИИ В ОБЛАЧНЫХ ВЫЧИСЛЕНИЯХ Математика

Текст научной статьи на тему «РОГОВЫЕ СИСТЕМЫ ГОМОМОРФНОГО ШИФРОВАНИЯ И ЗАЩИТА ИНФОРМАЦИИ В ОБЛАЧНЫХ ВЫЧИСЛЕНИЯХ»

ПРОГРАММИРОВАНИЕ, 2015, No 4, с. 47-51

— ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ —

УДК 004.421.6

ПОРОГОВЫЕ СИСТЕМЫ ГОМОМОРФНОГО ШИФРОВАНИЯ И ЗАЩИТА ИНФОРМАЦИИ В ОБЛАЧНЫХ ВЫЧИСЛЕНИЯХ

© 2015 г. Н. П. Варновский*, С. А. Мартишин**, М. В. Храпченко**, А. В. Шоку ров**

*Институт проблем информационной безопасности МГУ (ИПИБ МГУ)

119333 Мичуринский просп., 1 **Институт системного программирования FAH (ИСП FAH) 109004 г. Москва, ул. А. Солженицына, 25.

E-mail: barnaba.np@gmail.com, khrapm@gmail.com, mart@ispras.ru, shok@ispras.ru

Поступила в редакцию 15.12.2014

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

1. ВВЕДЕНИЕ

В предшествующей работе [1] нами была предложена модель облачных вычислений над конфиденциальными данными. От ранее изучавшихся моделей она отличается наличием специализированных криптосерверов. Предполагаемая стойкость системы базируется на дополнительном "физическом" предположении: существует некий порог, ограничивающий количество серверов, которые могут контролироваться противником.

В отличие от работы [1], рассматривающей общий случай, здесь мы исследуем только системы облачных вычислений, основанные на использовании пороговых гомоморфных криптосистем. Поэтому в разделе 2 описывается специальный вид нашей модели для этого частного случая.

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

В разделе 4 предлагается конструкция

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

Предложенная модификация позволяет построить систему облачных вычислений со следующими характеристиками:

• для перешифрования не требуется дополнительный открытый ключ;

ной процедуры открытого перешифрования, известной под названием "bootstrapping", используется протокол перешифрования, выполняемый криптосерверами;

ки зрения, наша система облачных вычисле-

ний над конфиденциальными данными допускает экспериментальную реализацию.

Далее в статье описываются общая конструкция системы, основные алгоритмы и протоколы. Вопросы стойкости анализируются в отдельной работе [3].

2. МОДЕЛЬ СИСТЕМЫ ОБЛАЧНЫХ ВЫЧИСЛЕНИЙ

С функциональной точки зрения, система облачных вычислений над конфиденциальными данными включает в себя следующие компоненты.

Участники: облако, центр аутентификации, криптосерверы, пользователи, клиенты.

Сеть связи: пользователи, клиенты и криптосерверы соединены (каждый) каналом связи с облаком. Центр аутентификации имеет канал связи с облаком, а также канал связи с каждым из криптосерверов. Кроме того, сеть связи между серверами представляет собой полный граф. Все каналы связи в нашей модели предполагаются защищенными.

На этапе инициализации серверы создают и публикуют открытый ключ пороговой не вполне гомоморфной криптосистемы (ТБНЕ). Пользователи шифруют свои конфиденциальные данные на этом ключе и размещают на облаке в зашифрованном виде.

Запросы на вычисления выдают клиенты. Клиент не обязательно должен быть пользователем (то есть может не иметь никаких данных на облаке). Центр аутентификации проверяет запрос и санкционирует его выполнение.

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

Кроме того, криптосерверы выполняют финальное дешифрование результата.

Подчеркнем, что в нашей модели противник пассивный. Это означает, что все участники следуют протоколу, но могут использовать полученную в ходе его выполнения информацию для нарушения конфиденциальности.

Противник может контролировать часть криптосерверов, но существует некоторый порог

t такой, что их количество не превосходит t. Кроме того, противник может контролировать часть пользователей (и, следовательно, он знает их конфиденциальную информацию) и облако. Центр аутентификации противнику недоступен.

Протоколы и алгоритмы:

1. Протокол генерации ключей TSHE.

2. Протокол аутентификации запроса клиента.

3. Алгоритм шифрования TSHE.

4. Протокол дешифрования TSHE.

5. Алгоритм вычисления над зашифрованными данными.

6. Протокол перешифрования TSHE.

3. ПОРОГОВЫЕ СИСТЕМЫ ВПОЛНЕ ГОМОМОРФНОГО ШИФРОВАНИЯ

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

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

В работе [4] описывается TFHE, основанная на FHE ван Дейка и др. [5]. Конструкция этой TFHE весьма сложная и громоздкая. Достаточно сказать, что описание одного только протокола генерации ключей занимает в работе [4] десять страниц. Поэтому приводим только результаты анализа этой TFHE. В принципе, на ее основе можно было бы строить систему облачных вычислений в нашей модели. Но поскольку, как уже указывалось выше, на повестке дня только

вопрос о принципиальной реализуемости, необходима математически обоснованная стойкость конструкции. В работе [4] очень кратко и на неформальном уровне поясняется, почему предлагаемая TFHE должна быть стойкой.

Еще одна попытка создать TFHE предпринята в статье [2]. Конструкция этой криптосистемы также достаточно громоздкая, но ключевые идеи можно кратко пояснить.

Основные натуральные параметры схемы q, n, m являются функциями от параметра стойкости. Для целого числа ж обозначим через [x]q единственное целое число v £ [—|, |] такое, что x = v mod q. Секретный ключ s криптосистемы выбирается случайным образом из Z^ (вообще говоря, не обязательно относительно равномерного распределения).

Для открытого ключа выбирается случайная m х n матрица A над Zq и вычисляется вектор p = As + 2e. Здесь e — "небольшой шум", т.е. m

подходящего распределения. Открытый ключ pk определяется как пара (A,p).

Для шифрования однобитового открытого текста ß выбирается случайный вектор r из {0,1}m, и вычисляются a = rT ■ A и b = {r,p} + ß. Криптограмма определяется как пара c = (a, b).

Дешифрование криптограммы выполняется [b - {a, s}]q mod 2

До сих пор все описание соответствовало случаю FHE. Возможность преобразования этой криптосистемы в пороговую основывается на следующем простом наблюдении. Предположим,

A

нас имеется набор секретных ключей Si и набор соответствующих вторых компонентов pi открытых ключей. Тогда открытый ключ (A,p*), где p* = £ pi, соответствует секретному ключу

s* = £ Si.

Выполняя протокол генерации ключей, серверы совместно генерируют и публикуют случайную матрицу A. Затем г-й сервер выбирает свою

si

pi

что как и всегда в случае пороговых криптосистем, секретный ключ не известен никому.

В протоколе дешифрования каждый из серверов вычисляет и передает всем остальным серверам значение wi = {a, si} + 2ei5 где ei — опять

"небольшой шум". Открытый текст у вычисляется по формуле у = [b — £ wi] mod 2.

Такова, в кратком изложении, основная идея построения TFHE из работы [2]. Сам протокол из этой работы существенно сложнее. Так, в частности, описание протокола генерации ключей занимает две страницы. Анализ этой конструкции TFHE показывает, что основные трудности проистекают из двух источников.

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

В нашей модели облачных вычислений на этапе выполнения запроса облако может обращаться к серверам. Последние совместно "знают" секретный ключ. Поэтому необходимость в дополнительном открытом ключе отпадает.

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

В целом, анализ показывает, что криптосистема из работы [2] могла бы использоваться для организации облачных вычислений в нашей модели. Но опять возникает основная проблема — стойкость.

Авторы вообще не исследуют стойкость своей криптосистемы. Это обусловлено тем, что работа посвящена такому универсальному типу криптографических протоколов, как протоколы конфиденциальных вычислений. При этом TFHE используется в качестве примитивного протокола. Анализируется стойкость построенного протокола конфиденциальных вычислений. И здесь

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком