Оценка криптостойкости полностью гомоморфных систем
3. Получаем
C
2
k
,
C
3
k
, . . . ,
C
k
−
1
k
,
C
k
k
образов всеми возможными сум-
мами
L
i
y
i
f
.
4. В результате получаем
2
k
образов
f
(0)
.
Обозначим множество всех найденных различных
f
(0)
как
Θ
. Тогда
i
-й бит открытого текста находится следующим образом:
f
−
1
(
y
)
∧
2
i
≡
(
0
,
если
y
∧
f
f
(2
i
)
2
Θ
1
,
иначе.
(10)
Данный способ позволяет получить максимально
2
k
образов
f
(0)
по
k
шифротекстам. Если данное множество велико, целесообразно
применение атаки с предвычислениями, а именно метод радужных
таблиц.
В качестве начального столбца необходимо выбрать
k
различных
начальных значений
f
(0)
. Функцию перехода выбираем как сумму те-
кущего элемента с подсуммой первого столбца. Выбирая длину строки
таблицы порядка
2
k
k
получаем уменьшение хранимого множества
Θ
до
2
k
элементов.
В случае неравномерной вероятности распределения образов фик-
сированного прообраза, атака аналогична, но возможно ее завершение
за меньшее время, т.к. существует такой образ
f
(0)
, вероятность перей-
ти в который после определенного количества операций
f
стремится
к нулю.
Анализ количества гомоморфизмов.
Алгоритм дешифрования
можно использовать для вычисления верхней оценки количества пол-
ностью гомоморфных систем.
Рассмотрим два случая.
1)
n
=
m
. Задавая одно отображение
x
f
−→
y
с помощью дешифро-
вания можно получить все образы
2
i
, что позволяет построить образ
y
произвольного
x
. Таким образом верхняя оценка количества полных
гомоморфизмов
|
X
f
−→
Y
| ≤
2
n
∙
2
m
= 2
n
+
m
.
(11)
2)
n < m
. Первым шагом находим по одному экземпляру всех
образов аналогично предыдущему случаю. Затем необходимо учесть
оставшиеся
2
m
−
2
n
образов. Образ может не иметь прообраза. Данная
задача аналогична распределению шаров в урны, причем урны могут
быть пустыми. Тогда верхняя оценка количества полных гомоморфных
систем:
|
X
f
−→
Y
| ≤
2
n
+
m
∙
(
n
+ 1)
2
m
−
2
n
.
(12)
3
