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



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

Отличительный признак A:
A задан в качестве входной 2n • t(n)-битной строки w1|| • • • ||wt(n).
1. Выберем равномерное j ∈ {0, . . . , n − 1}. В дальнейшем A (неявно) поддер-
живает двоичное дерево высоты n, с n-битными значениями (подмножества) 
внутренних узлов на высоте j + 1 и ниже.
2. Запустим D(1n). Когда D делает запрос прогноза x = x1 • • • xn, обратите 
внимание на префикс x1 • • • xj . Есть два случая:


294
• Если D до сих пор никогда не делал запроса с этим префиксом, то используйте x1 
• • • xj, чтобы достичь узла v на j-м уровне дерева. Возьмем следующую неиспользуе-
мую 2n-битную строку w и зададим значение левого дочернего элемента узла v левой 
половине w , а значение правого дочернего элемента v правой половине w.
• Если D ранее делал запрос с префиксом x1 • • • xj, то узлу x1 • • • xj+1 уже 
было присвоено значение.
Используя значение у узла x1 • • • xj+1, вычислим значение у концевого элемен-
та в соответствии с x1 • • • xn, как в конструкции 7.21, и возвратим это значение D.
3. Когда выполнение D завершено, выведем бит, возвращенный D.
A действует в течение полиномиального времени. Очень важно, что в этом 
случае A не нужно сохранять все двоичное дерево экспоненциального разме-
ра. Вместо этого оно «заполняется» значениями не более 2t(n) узлов в дереве. 
Пусть A выбирает j = j*. Заметим, что:
1. Если вход A является равномерной 2n • t(n)-битной строкой, то ответы, ко-
торые она дает D распределены точно так же, как если бы D взаимодействовало 
с функцией, выбранной из распределения Hj +1. Это справедливо, поскольку 
значения узлов на уровне дерева j* + 1 равномерны и независимы.
2. Если вход A состоит из t(n) псевдослучайных строк, т.е. wi = tt(si) для равно-
мерного начального числа si, то ответы, которые он дает D распределены точно 
так же, как если бы D взаимодействовало с функцией, выбранной из распре-
деления Hj. Это справедливо, поскольку значения узлов на уровне j* дерева (а 
именно, s-значения) равномерны и независимы. (Эти s-значения неизвестны 
для A, но это не имеет никакого значения).
Действуя, как и раньше, можно показать, что
Ранее мы показали, что выражение (7.14) должно быть пренебрежимо ма-
лым. Сказанное выше подразумевает, что выражение (7.13) также должно быть 
пренебрежимо малым.


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




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

    Басты бет