Введение в современную криптографию
Устойчивые к коллизиям хэш-функции
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Замечание по поводу этой главы.
- 7.1 Односторонние функции
| Устойчивые к коллизиям хэш-функции. В отличие от предыдущей главы, мы
здесь не рассматриваем устойчивые к коллизиям хэш-функции. Причина заключает- ся в том, что конструкции таких хэш-функций из односторонних функций неизвест- ны и, на самом деле, имеются свидетельства, что такие конструкции невозможны. Мы обратимся к доказуемым конструкциям устойчивых к коллизиям хэш-функций, основанных на специфических теоретико-числовых допущениях , в разделе 8.4.2. Замечание по поводу этой главы. Материал в этой главе более современный, чем материал в остальной части этой книги. Данный материал не используется в явном виде где-нибудь еще и, при желании, эту главу можно пропустить. Сказав это, мы попытались представить материал таким образом, чтобы он был понят- ным (с трудом) способным студентам последнего курса или начинающим аспи- рантам. Мы призываем всех читателей внимательно изучить разделы 7.1 и 7.2, в которых вводятся односторонние функции, и представлен обзор остальной части этой главы. Мы считаем, что знакомство, по крайней мере, с некоторыми из тем, рассматриваемых здесь, достаточно важно, чтобы оправдать затраченные усилия. 7.1 Односторонние функции В этом разделе мы формально определим односторонние функции, а затем кра- тко обсудим некоторые варианты, которые согласно широко распространенному мнению, соответствуют этому определению. (Больше примеров предполагаемых односторонних функций мы увидим в главе 8). Далее мы введем понятие труд- ных предикатов, которое можно рассматривать как выделение в отдельный эле- мент сложности инвертирования односторонней функции, и которое будет ши- роко использоваться в конструкциях, рассматриваемых в следующих разделах. Определения Одностороннюю функцию f: {0, 1}* → {0, 1}* легко вычислить, но сложно инвертировать. Первое условие легко формализовать: мы просто потребуем, чтобы f можно было вычислить за полиномиальное время. Поскольку мы за- интересованы в создании криптографических схем, которые трудны для взлома вероятностного полиномиально-временного противника, за исключением пре- небрежимо малой вероятности, мы формализуем второе условие, потребовав, чтобы для любого вероятностного полиномиально-временного алгоритма было невозможно инвертировать f, т.е. найти прообраз данного значения y, за исклю- чением пренебрежимо малой вероятности. Технический вопрос заключается в том, что эта вероятность берется из эксперимента, в котором y генерируется за счет выбора однородного элемента x области f и затем задания y := f (x) (а не выбора y равномерно из диапазона f ). Причина этого должна стать понятной из 267 конструкций, которые мы увидим в остальной части главы. Пусть f : будет функцией {0, 1}* → {0, 1}*. Рассмотрим следующий экспе- римент, определенный для любого алгоритма A и любого значения f для пара- метра безопасности. Инвертирующий эксперимент InvertA,f (n) 1. Выберите однородные x ∈ {0, 1}n, и вычислите y := f (x). 2. A задано равным 1n , а y как вход и выходы xr . 3. Выход эксперимента определяется как 1, если f (xr) = y, и 0 в противном случае. Подчеркнем, что для A не нужно искать оригинальный прообраз x; для A до- статочно найти любое значение xr для которого f (xr) = y = f (x). Мы задаем па- раметр безопасности 1n для A на втором этапе, чтобы подчеркнуть, что A может действовать в течение полиномиального времени в параметре безопасности n независимо от длины y. Теперь определим, что это значит для функции f, чтобы она была односто- ронней. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|