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


Устойчивые к коллизиям хэш-функции



Pdf көрінісі
бет196/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   192   193   194   195   196   197   198   199   ...   249
Криптография Катц

Устойчивые к коллизиям хэш-функции. В отличие от предыдущей главы, мы 
здесь не рассматриваем устойчивые к коллизиям хэш-функции. Причина заключает-
ся в том, что конструкции таких хэш-функций из односторонних функций неизвест-
ны и, на самом деле, имеются свидетельства, что такие конструкции невозможны. 
Мы обратимся к доказуемым конструкциям устойчивых к коллизиям хэш-функций, 
основанных на специфических теоретико-числовых допущениях , в разделе 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, чтобы она была односто-
ронней.


Достарыңызбен бөлісу:
1   ...   192   193   194   195   196   197   198   199   ...   249




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

    Басты бет