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