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) также должно быть
пренебрежимо малым.
Достарыңызбен бөлісу: