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