УДК 004.056:004.62
Оценка криптостойкости полностью гомоморфных
систем
c А.Е. Малинский
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Облачные вычисления являются одной из самых востребованных на текущий пе-
риод технологий на рынке информационных услуг. Однако безопасность облачных
вычислений опирается на доверие к поставщику облачных услуг. В отсутствии до-
верия данную задачу могут решить системы полностью гомоморфного шифрова-
ния. Эти системы позволяют производить операции над зашифрованными данными
без выполнения операции расшифрования [1]. Таким образом, поставщик облачных
услуг выполняет требуемые операции при сохранении конфиденциальности данных
клиента. В данной статье рассмотрены уязвимости, присущие полностью гомо-
морфным системам. В ходе исследования получены оценки по стойкости полностью
гомоморфных систем, а так же алгоритмы для дешифровки зашифрованных сооб-
щений для произвольных реализаций полностью гомоморфного шифрования. Алго-
ритм дешифровки зашифрованных сообщений позволил оценить сверху количество
гомоморфных систем. Данный результат указывает на отсутствие безопасного
полностью автоморфного шифрования.
Ключевые слова
:
облачные вычисления, гомоморфизм, криптография, шифрование.
Введение в полностью гомоморфное шифрование.
Пусть даны
два множества двоичных векторов
X
и
Y
. Без ограничения общности
положим, что
|
X
|
= 2
n
,
|
Y
|
= 2
m
,
n
≤
m
. Пусть
λ
(
x
1
, x
2
, . . . , x
i
)
— про-
извольная функция от
i
переменных, где
x
i
2
X
,
λ
(
x
1
, x
2
, . . . , x
i
)
2
X
.
Тогда полностью гомоморфное шифрование — это пара отображений
f
:
X
f
−→
Y,
y
=
f
(
x
)
(1)
f
−
1
:
Y
f
−
1
−−→
X, x
=
f
−
1
(
y
)
,
(2)
таких что
8
λ
(
x
1
, x
2
, . . . , x
i
)
, выполняются следующие условия:
f
−
1
(
f
(
λ
(
x
1
, x
2
, . . . , x
i
)))
≡
λ
(
x
1
, x
2
, . . . , x
i
)
(3)
9
λ
f
(
y
1
, y
2
, . . . , y
i
) :
λ
(
x
1
, x
2
, . . . , x
i
)
≡
f
−
1
(
λ
f
(
y
1
, y
2
, . . . , y
i
))
.
(4)
Уравнение (3) гарантирует, что при шифровании значения произ-
вольной функции и последующем расшифровании результат останется
неизменным. Уравнение (4) позволяет отображать произвольную опе-
рацию над множеством
X
в операцию над множеством
Y
.
Отметим, что по построению гомоморфное шифрование может
отображать лишь базисные операции, т.е. такие операции, через ко-
торые можно выразить все функции. Таким образом, условие отобра-
1
