193
и саму строку x назовем запросом , поданным оракулу . Предполагается, что
запросы оракулу должны быть частными, поэтому, если какая-то сторона опра-
шивает оракула по входному элементу x , то никто более не должен знать x или
даже знать, что эта сторона опрашивает оракула вообще. В этом есть смысл,
потому что обращения к оракулу соответствуют (в практической реализации)
местным вычислениям криптографической хэш-функции. Важным свойством
этой «коробки» является то, что она последовательна. То есть, если коробка
когда-либо выводила y на конкретный входной элемент x, тогда она всегда вы-
водит один и тот же ответ y после получения такого же входного элемента x
снова. Это
означает, что мы можем рассматривать коробку, как имплементацию
проработанной функции H; то есть мы определяем функцию H на основании
входных/выходных характеристик коробки. Для удобства мы, таким образом,
говорим «опрашивание H» вместо опраивания коробки. Никто не «знает» пол-
ной функции H (кроме самой коробки); в лучшем случае, все, что известно, - это
значения H по строкам, которые были открыто запрошены до сих пор.
Мы уже обсудили в Главе 3, что значит подбирать случайную функцию H. Мы
только напомним здесь, что существует два эквивалентных способа представить
себе единообразный подбор H: либо изобразить H, выбранную «одним махом»
единообразно из набора всех функций по какой-то определенной области или
диапазону, либо представить себе генерирующиеся выходные данные для H «на
лету», как будет необходимо. В частности, во втором случае мы можем рассма-
тривать функцию как такую, что была определена таблицей, которая изначально
пуста. Когда оракул получает запрос x , он поначалу проверяет, x = xi для какой-
либо пары (xi, yi) в таблице; если да - соответствующее значение yi возвращается.
Иначе универсальная строка y ∈{0, 1}A выбирается (для какой-либо специфи-
ческой A), возвращается ответ y ; и оракул сохраняет (x, y) в таблицу.
Вторая точ-
ка зрения часто концептуально более легкая обоснования и также более легкая в
техническом плане, если H определяется в бесконечной области (то есть {0, 1}*).
Когда мы определили псевдослучайные функции в Разделе 3.5.1, мы также
рассмотрели алгоритмы с доступом оракула к случайной функции. Во избе-
жание каких-либо заблуждений, мы отмечаем, что использование случайной
функции там очень отличается от использования случайной функции здесь. Там
случайная функция была использована в качестве способа определения, что это
значит для (конкретной) ключевой функции быть псевдослучайной. В модели
со случайным оракулом, наоборот, случайная функция сама по себе использу-
ется в качестве конструкции и должна быть каким-то образом реализована на
практике, если мы хотим конкретной реализации конструкции. Псевдослучай-
ная функция не является случайным оракулом, потому что она псевдослучайна
только при секретном ключе. Однако, в модели со случайным оракулом всем