Возражения против модели со случайным оракулом

198
значение H(x) является «полностью случайным», если x не был явно запрошен. Ана-
лог должен был бы потребовать, чтобы Hˆ (x) была случайной (или псевдослучай-
ной), если Hˆ не был явно подсчитан по x. Как мы должны толковать то на практике? 
Даже не очень ясно, что означает «явно вычислить» Hˆ : что если злоумышленник 
знает какой-то легкий путь для вычисления Hˆ, который не требует запуска реального 
кода для Hˆ ? Кроме того, Hˆ (x), возможно, не может быть случайным (или даже 
псевдослучайным), поскольку после того, как злоумышленник узнает описание Hˆ, 
значение этой функции по всем входным данным будет тут же определено.
Ограничения модели со случайным оракулом становятся более понятными после 
того, как мы исследуем доказательные методы, представленные ранее. Вспомним, 
что одним из доказательных методов является использование факта, что редукция 
может «увидеть» запросы, которые злоумышленник A совершает случайному ора-
кулу. Если мы заменим случайный оракул определенной хэш-функцией Hˆ, это бу-
дет означать, что мы должны обеспечить описание Hˆ злоумышленнику в начале 
эксперимента. Но затем A сможет вычислить Hˆсамостоятельно без выполнения 
каких-либо явных запросов, и поэтому редукция больше не будет иметь возмож-
ность «видеть» запросы, выполняемые A. (Фактически, как было ранее отмечено, 
понятие о злоумышленнике A, выполняющим явные вычисления Hˆ может не быть 
истинным и определенно не может быть формально определенным.) Аналогичным 
образом, доказательства защиты защиты в модели со случаным оракулом позволя-
ют редукции выбирать выходные данные H на свое усмотрение, что-то, что просто 
невозможно, когда используется конкретная функция. 
Даже если мы пожелаем игнорировать, вышеописанные теоретические про-
блемы, практическая проблема будет в том, что мы на данный момент не имеем 
полного понимания того, что означает для конкретной хэш-функции быть «до-
статочно хорошей» при реализации случайного оракула. Для больше конкретики 
скажем, мы хотим реализовать случайного оракула с использованием некоторой 
соответствующей модификации HA-1 (SHA-1 - это криптографическая хэш-
функция, рассматриваемая в Разделе 6.3.3). Если для какой-то определенной схе-
мы Π должно быть обосновано предположить, что Π является защищенной при 
реализации с использованием SHA-1, намного менее обосновано предполагать, 
что SHA-1 сможет занять место случайного оракула в каждой схеме, разрабо-
танной по модели со случайным оракулом. Действительно, как мы уже говорили 
ранее, мы знаем, что SHA-1 не является случайным оракулом. И не очень-то и 
сложно разработать схему, которая является защищенной внутри модели со слу-
чайным оракулом, но незащищенную, когда SHA-1 заменяет случайного оракула.
Мы настаиваем, что предположение о том, что форма «SHA-1 действует как 
случайный оракул» качественно отличается от предположения «SHA-1 явля-
ется стойкой к коллизиям» или «AES является псевдослучайной функцией». 

199
Проблема заключается частично в том факте, что не существует удовлетвори-
тельного объяснения тому, что означает первое утверждение в то время, как у 
нас имеются определения для двух последних утверждений.
Из-за этого использование модели со случайным оракулом для доказательства схе-
мы качественно отличается от, например, представления нового криптографическо-
го допущения для того, чтобы доказать, что схема защищена в стандартной модели. 
Таким образом, доказательства защиты в модели со случайным оракулом являются 
менее удовлетворительны, чем доказательства защиты в стандартной модели.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: