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