Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Отличительный признак 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) также должно быть пренебрежимо малым. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|