Введение в современную криптографию
Определения и доказателства в модели со случайным оракулом
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Определения и доказателства в модели со случайным оракулом
Определения модели со случайным оракулом немного отличаются от определений в стандартной модели, потому что области вероятности в каждом случае разные. В стандартной модели схема Π является защищенной, если для всех ppt злоумышлен- ников A вероятность какого-либо события - ниже определенного порога, когда такая вероятность берется посредством случайных выборов сторон, запускающих Π и вы- боровзлоумышленника A. Предполагая, что доверенные стороны, которые использу- ют Π на практике, делают случайный выбор в соответствии со схемой, удовлетворе- ние определения данного типа гарантирует защиту для использования Π на практике. В модели со случайным оракулом, наоборот, схема Π может опираться на оракула H. Как и ранее Π является защищенной, если для всех ppt злоумыш- ленников A вероятность какого-либо события - ниже определенного порога, но теперь эта вероятность берется посредством случайного выбора H, равно как и случайных выборов сторон, запускающих Π и выборов злоумышленника A. При использовании Π на практике, некоторый (его реализация) H должен быть фиксированный. К несчастью, защита Π не гарантируется для любого спец- ифического выбора H. Это показывает на одну из причин того, почему тяжело утверждать, что любая конкретная реализация оракула H детерминированной функцией дает защищенную схему. (Дополнительная техническая трудность состоит в том, что, когда конкретная функция H является фиксированной, зло- умышленнику A более не запрещено опрашивать H в качестве оракула, но он может увидеть и использовать код H во время своей атаки.) Доказательства в модели со случайным оракулом могут эксплуатировать тот факт, что H выбирается случайным образом, и что единственный способ вычис- лить H(x) - в открытую запросить x у H. Три особых свойства являются особенно полезными; мы вкратце набросаем их здесь и покажем несколько несколько их простых применений ниже и в следующем разделе, но стоит предупредить, что полное понимание скорее всего подождет до тех пор, пока мы не представим фор- мальные доказательства в модели со случайным оракулом в следующих главах. Первое полезное свойство модели со случайным оракулом - это: Если x не был запрошен у H, тогда значение H(x) является универсальным. На первый взгляд это может напоминать гарантию, обеспеченную псевдослучайным генератором, но на самом деле это сильнее. Если tt является псевдослучайным генератором, тогда tt(x) является псевдослучайным для наблюдателя, предпола- гающего, что x выбран единообразно случайным образом и является полностью неизвестным наблюдателю. Если H является случайным оракулом, однако, тогда 195 H(x) является истинно универсальным для наблюдателя, посколько наблюдатель не запрашивал x. Это истинно, даже если x является известным, или если x не является универсальным, но является трудноугадываемым. Например, если x - это n-битная строка, где первая половина x известна и вторая половина случайна, тогда tt(x) должно быть легко отличить от случайного, а H(x) - нет.) Оставшиеся два свойства относятся непосредственно к доказательствам по- средством редукции в модели со случайным оракулом. (Возможно, полезно бу- дет обратиться к Разделу 3.3.2.) В качестве части сведения случайный оракул, с которым взаимодействует злоумышленник A , должен быть симулирован. То есть: A будет подавать запросы и получать ответы от того, что он будет пред- ставлять как оракула, но редукция сама по себе должна теперь отвечать на дан- ные запросы. Оказывается, это дает много возможностей. Прежде всего: Если A запрашивает x у H, редукция видит этот запрос и узнает x. Это иногда называется «экстрагируемость». (Это не противоречит факту, упо- мянутому ранее, что запросы случайному оракулу являются «частными».) Хотя это является истинным в самой модели со случайным оракулом, здесь мы ис- пользуем A как подпрограммувнутри редукции, которая симулирует случайно- го оракула для A.) Наконец: Редукция может устанавливать значение H(x) (то есть ответ на запрос x) до значения своего выбора, поскольку это значение правильно распределено, то есть является универсальным. Это называется «программируемость». Не существует аналога экстрагируе- мости или программируемости, как только There is no counterpart to extractability or programmability once H is instantiated with any concrete function . жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|