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


Более подробно о модели со случайным оракулом



Pdf көрінісі
бет141/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   137   138   139   140   141   142   143   144   ...   249
Криптография Катц

5.5.1 Более подробно о модели со случайным оракулом 
Перед тем, как продолжить, давайте определим, что же собой представляет 
модель со случайным оракулом. Хорошим способом представить себе модель 
со случайным оракулом будет следующий: «Оракул» - это просто коробка, кото-
рая принимает бинарную строку в качестве входного элемента и возвращает би-
нарную строку в качестве выходного элемента. Что происходит внутри коробки 
- неизвестно и непостижимо. Все, доверенные стороны, равно как и злоумыш-
ленник, могут взаимодействовать с коробкой, и такое взаимодействие состоит 
из подачи бинарной строки x в качестве входного жлемента и получения бинар-
ной строки y в качестве выходного; мы назовем это опрашивание оракула по x 


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, мы также 
рассмотрели алгоритмы с доступом оракула к случайной функции. Во избе-
жание каких-либо заблуждений, мы отмечаем, что использование случайной 
функции там очень отличается от использования случайной функции здесь. Там 
случайная функция была использована в качестве способа определения, что это 
значит для (конкретной) ключевой функции быть псевдослучайной. В модели 
со случайным оракулом, наоборот, случайная функция сама по себе использу-
ется в качестве конструкции и должна быть каким-то образом реализована на 
практике, если мы хотим конкретной реализации конструкции. Псевдослучай-
ная функция не является случайным оракулом, потому что она псевдослучайна 
только при секретном ключе. Однако, в модели со случайным оракулом всем 


194
сторонам необходимо иметь возможность вычислять функцию; таким образом, 
там может и не быть секретного ключа. 


Достарыңызбен бөлісу:
1   ...   137   138   139   140   141   142   143   144   ...   249




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

    Басты бет