А.Е. Малинский
жения всех возможных функций и отображение базисных функций
являются эквивалентными.
Анализ защищенности полностью гомоморфных систем.
В свя-
зи с тем что полностью гомоморфное шифрование отображает любую
функцию
λ
на пространство
Y
, оно отображает в том числе и:
1. Побитная сумма по модулю 2:
x
1
x
2
f
−→
y
1
f
y
2
2. Побитная конъюнкция:
x
1
∧
x
2
f
−→
y
1
∧
f
y
2
3. Побитное отрицание:
¬
x
1
f
−→ ¬
f
y
1
4. Битовый сдвиг:
x
1
1
f
−→
y
1
f
1
Отметим, что битовый сдвиг является единственной рассматриваемой
функцией, которая связывает разряды векторов между собой.
Предположим, что был осуществлен перехват шифротекста
y
. Тогда
нетрудно заметить, что
f
(0) =
y
f
y
(5)
f
(2
n
−
1) =
y
∨
f
¬
f
y
(6)
f
(2
0
) = (
f
(2
n
−
1)
f
n
−
1)
(7)
f
(2
i
) = (
f
(2
n
−
1)
f
n
−
i
−
1)
f
(
f
(2
n
−
1)
f
n
−
i
)
, i >
0
(8)
В том случае, если
|
X
| ≡ |
Y
|
, т.е.
n
≡
m
,
i
-й бит открытого текста
находится следующим образом:
f
−
1
(
y
)
∧
2
i
≡
(
0
,
если
y
∧
f
f
(2
i
)
≡
f
(0)
1
,
иначе.
(9)
Таким образом, не имея ключа шифрования возможно получение
открытого текста. Количество гомоморфных операций для получения
образов
2
i
равно
ω
f
+
ω
¬
f
+
ω
∨
f
+
ω
f
= (1+
n
−
1)+1+1+(
n
−
1) = 2
n
+
+1
. Проверка бит затрачивает
n
гомоморфных операций и
n
обычных
операций сравнения.
Если
n > m
, необходимо доработать предыдущий метод: количе-
ство образов для каждого прообраза может быть более одного.
Если вероятность получения образа фиксированного прообра-
за равномерно распределена, то можем выполнить полный перебор
образов
f
(0)
следующим путем.
1. Перехватываем
k
шифротекстов.
2. Получаем
k
новых образов
f
(0) =
y
k
f
y
k
.
2
