Введение в современную криптографию


РИС. 7.3: Трехраундовая сеть Фейстеля, используемая для построения псев- дослучайной перестановки из псевдослучайной функции. ДОКАЗАТЕЛЬСТВО



Pdf көрінісі
бет216/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   212   213   214   215   216   217   218   219   ...   249
Криптография Катц

РИС. 7.3: Трехраундовая сеть Фейстеля, используемая для построения псев-
дослучайной перестановки из псевдослучайной функции.
ДОКАЗАТЕЛЬСТВО В стандартном способе мы можем заменить псевдос-
лучайные функции, используемые при построении F (3), функциями, выбран-
ными равномерно наугад. Псевдослучайность F предполагает, что функция 
имеет лишь пренебрежимо малое влияние на выход любого вероятностного 
полиномиально-временного отличительного признака, взаимодействующего с 
F (3) в качестве прогноза. Оставляем детали в качестве упражнения.
Пусть D – вероятностный полиномиально-временной отличительный признак.
В оставшейся части доказательства покажем, что следующее пренебрежимо мало:
где первая вероятность берется по равномерному и независимому выбору f1, f2, 
f3 из Funcn, а вторая вероятность берется по равномерному выбору π из Perm2n.
Зафиксируем некоторое значение для параметра безопасности n, и пусть q = q(n) 
обозначает полином верхней границы количества запросов прогноза, сделанных 
D. Без потери общности, предположим, что D никогда не делает один и тот же за-
прос прогноза дважды. Сосредоточив внимание на взаимодействии D с Feistelf1 
,f2,f3 (•), допустим, что (Li0 , Ri0 ) обозначает i-й запрос, который D делает по 
своему прогнозу, и допустим, что (Li3 , Ri3 ), (Li1 , Ri1 ), и (Li2 , Ri2 ) обозначает 
промежуточные значения после раундов 1, 2 и 3, соответственно, являющиеся ре-
зультатом этого запроса. (См. рис. 7.3). Обратите внимание, что D выбирает (Li0 
, Ri0 )и видит результат Li3 , Ri3 ), но прямо не видит (Li1 , Ri1 ) или (Li2 , Ri2).
Мы говорим, что имеется коллизия при R1, если Ri1 = Rj1 для некоторого 
отдельного i, j. Сначала докажем, что коллизия при R1 возникает лишь с прене-
брежимо малой вероятностью. Рассмотрим любое фиксированное, отдельное i, 
j. Если Ri1 = Rj1, то Li0 ƒ= Lj0 , но тогда


297
Если R0i ƒ= R0i, то f1(R0i ) и f1(R0i ) являются равномерными и независимы-
ми, таким образом,
Учет границы объединения по всем отдельным i, j показывает, что вероятность 
коллизии при R1 не более q2/2n.
Скажем, существует коллизия при R2, если R2i = R2i для некоторого отдель-
ного i, j. Докажем, что обусловленная отсутствием коллизии при R1, вероят-
ность коллизии при R2 пренебрежимо мала. Проведем анализ, как указано 
выше: рассмотрим любое фиксированное i, j и отметим, что если отсутствует 
коллизия при R1, то R1i ƒ=R1i . Таким образом, f2(R1i ) и f2(R1i ) являются 
равномерными и независимыми, и поэтому
(Обратите внимание, что f2 независимо от f1, что облегчает указанное выше 
вычисление). Учет границы объединения по всем отдельным i, j дает
Pr[коллизии при R2 | отсутствие коллизии при R1] ≤ q2/2n.
Обратите внимание, что L3i=R2i=L1i ⊕f2(R1i); таким образом, обусловлено отсут-
ствие какой-либо коллизии при R1, все значения L1, . . . , Lq независимы и равно-
мерно распределены в {0, 1}n. Если дополнительно выдвинуть условие для события 
отсутствия коллизии при R2, то значения L1, . . . , Lq равномерно распределены среди 
всех последовательностей q различных значений в {0, 1}n. Аналогично, Ri = Li ⊕ 
f3(Ri ); таким образом, обусловлено отсутствие коллизии при R2, все значения R1, . . 
. , Rq равномерно распределены в {0, 1}n, а также независимы друг от друга L1, . . . , Lq 
. Подведем итог: при запросе F (3) (с равномерными раундовыми функциями) на се-
рии q различных входов, кроме как с пренебрежимо малой вероятностью, выходные 
значения (L1, R1), . . . , (Lq, Rq ) распределены так, что {Li } являются равномерными 
и независимыми, но различными, n-битными значениями, и {Ri } являются равно-
мерными и независимыми n-битными значениями. В противоположность этому, при 
запросе случайной перестановки на серии q различных входов, выходные значения 
(L1, R1), . . . , (Lq, Rq ) равномерные и независимые, но различные 2n-битные значе-
ния. Лучшая отличительная атака для D, состоит в том, чтобы догадаться, что он вза-
имодействует со случайной перестановкой, если Li= Lj для некоторого отдельного i, 
j. Но данное событие возникает с пренебрежимо малой вероятностью, в этом случае. 
Это можно превратить в формальное доказательство.
F(3) не является строгой псевдослучайной перестановкой, что будет пред-
ложено вам продемонстрировать в упражнении 7.17. К счастью, добавление 
четвертого раунда дает в результате, строгую псевдослучайную перестановку.
Детали приведены в виде конструкции 7.24.


298


Достарыңызбен бөлісу:
1   ...   212   213   214   215   216   217   218   219   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет