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


Конструирование a псевдослучайной функции из случайного оракула



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

Конструирование a псевдослучайной функции из случайного оракула. Это 
такеже достаточно просто сконструировать псевдослучайную функцию в модели 
со случайным оракулом. Предположим, что Ain(n) = 2n и Aout(n) = n и определим
F (x) H(k||x),
где |k| = |x| = n. В Упражнении 5.11 вас попросили показать, что это псевдослу-
чайная функция, а именно, что для любого полиномиально-временного A веро-
ятность успехаA в следующем эксперименте - не более 1/2 плюс пренебрежимо 


197
малая функция:
1. Функция H и значения k ∈{0, 1}n и b ∈{0, 1} выбираются единообразно.
2. Если b = 0, злоумышленник A получает доступ к оракулу для Fk (•) = H(k»•). 
Если b = 1, тогда A получает доступ к случайной функции, преобразующей 
n-битные входные данные в n-битные выходные данные. (Эта случайная функ-
ция является независимой от H.)
3. A выводит бит br, и достигает успеха, если br = b.
На втором шаге, A может получить доступ к H в дополнение к оракулу функции, 
предоставленному ему экспериментом. (Псевдослучайная функция в модели со слу-
чайным оракулом должна быть неотличима от случайной функции, независимой от H.)
Интересный аспект всех вышеописанных утверждений заключается в том, что они 
не предполагают вычислительных допущений; они справедливы даже для вычисли-
тельно неограниченных злоумышленников, пока такие злоумышленники ограниче-
ны полиномиально большим количеством запросов оракулу. Этому нет аналогов в 
реальности, где, как мы убедились, вычислительные допущения необходимы. 
5.5.2 Работает ли метод случайного оракула ?
Схемы, разработанные в модели со случайным оракулом, внедряются на 
практике путем реализации H м некоторыми конкретными функциями. С меха-
ников модели со случайным оракулом позади нас, мы подходим к более фунда-
ментальному вопросу:
Что гарантируют доказательства защиты в модели со случай-
ным оракулом касательно защиты любой реальной реализации?
Вопрос не имеет определенного ответа: ведутся споры внутри криптографи-
ческого сообщества касательно того, как толковать доказательства в модели со 
случайным оракулом, и активная область исследования должна определить, что 
конкретно доказательство защиты в модели с случайным оракулом предполага-
ют по отношению к реальному миру. Мы можем только надеяться, что споры 
продолжат мотивировать обе стороны.


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




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

    Басты бет