Введение в современную криптографию
Инвертирующий эксперимент InvertA,Π(n)
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОПРЕДЕЛЕНИЕ 7.3
- Варианты односторонних функций
| Инвертирующий эксперимент InvertA,Π(n):
1. Gen(1n) выполняется, чтобы получить I, а затем выполняется Samp(I), чтобы получить однородные x ∈ DI . В конце вычисляется y := fI (x). 2. A при заданных I и y на входе выводит xr . 3. Выходные данные эксперимента - это 1, если fI (xr) = y. ОПРЕДЕЛЕНИЕ 7.3 Семейство функций/перестановок Π = (Gen, Samp, f ) является односторонним, если для всех вероятностных полиномиально-времен- ных алгоритмов A существует пренебрежимо малая функция negl, такая что Pr[InvertA,Π(n) = 1] ≤ negl(n). В этой главе мы работаем с односторонними функциями/перестановками в бесконечной области (как в Определении 7.1), но не работаем с семействами односторонних функций/перестановок. Это делается, в первую очередь, для удобства и существенно не влияет ни на какие результаты (см. упражнение 7.7). Варианты односторонних функций Односторонние функции интересны, только если они существуют. Мы не знаем, как доказать, что они обязательно существуют (это было бы большим прорывом в теории сложности), поэтому мы должны предположить или допустить их суще- ствование. Такое предположение основано на том, что некоторым естественным вычислительным проблемам было уделено больше внимания, но по-прежнему не имеется полиномиально-временного алгоритма для их решения. Возможно, наи- более известной из таких проблем является целочисленная факторизация, т.е. поиск простых множителей для большого целого числа. Очень просто перемножить два числа и найти их произведение, но сложно взять число и определить его множите- ли. Это подводит нас к тому, чтобы определить функцию fmult(x, y) = x • y. Если мы не накладываем никаких ограничений на длину x и y, то fmult несложно инверти- 270 ровать: с высокой вероятностью x • y будет четным, в этом случае (2, xy/2) является инверсией. Эта проблема может быть решена ограничением области fmult до про- стых чисел равной длины x и y. Мы вернемся к этой идее в разделе 8.2. Другой вариант односторонней функции, не опирающийся непосредственно на теорию чисел, основан на проблеме суммы подмножеств и определяется где каждое xi является n-битной строкой, интерпретируемой в качестве целого, а J - n-битной строкой, интерпретируемой как указанное подмножество от {1, . . . , n}. Ин- вертирование fss на выходе (x1, . . . , xn, y) требует нахождения подмножества Jr∈{1, . . . , n}, так чтобы ∑.j∈Jtxj=y mod 2 . Студенты, которые изучали N P-полноту, могут напомнить, что эта проблема N P-полная. Но даже P ƒ= N P не означает, что fss явля- ется односторонней: P ƒ= N P означает, что каждый полиномиально-временной ал- горитм не может решить проблему суммы подмножеств на, по меньшей мере, одном входе, поскольку для fss должна существовать односторонняя функция, необходимо, чтобы каждый полиномиально-временной алгоритм не мог решить проблему суммы подмножеств (по крайней мере, для определенных параметров) почти всегда. Таким образом, мы считаем, что описанная выше функция - это односторонняя функция, основанная на отсутствии известных алгоритмов, чтобы решить данную проблему даже при «небольшой» вероятности на случайных входах, а не только на основании того факта, что проблема является N P-полной. Показывая семейство перестановок, мы пришли к выводу, что они, как полагают, являются односторонними. Пусть Gen - это такой вероятностный полиномиально- временной алгоритм, что когда на входе 1n, выводит n-битное простое число p на- ряду со специальным элементом g∈{2, . . . , p − 1}. (Элемент g должен быть генера- тором Z*; см. раздел 8.3.3). Пусть Samp - это алгоритм который, при заданных p и g, выводит однородное целое число x∈{1, . . . , p − 1}. И, наконец, определим fp,g (x) = [gx mod p]. (Тот факт, что fp,g могут быть вычислены эффективно, следует из результатов в Приложении B.2.3). Можно показать, что эта функция является взаимно одно- значной и, следовательно, перестановкой. Предполагаемая трудность инверти- рования этой функции основана на сложности проблемы дискретного логариф- мирования; мы скажем об этом намного больше в разделе 8.3. Наконец, отметим, что очень эффективные односторонние функции могут быть получены из практических криптографических конструкций, таких как SHA-1 или AES в предположении, что они устойчивы к коллизиям или псевдос- лучайной перестановке, соответственно; см упражнения 7.4 и 7.5. (С технической точки зрения, они не могут соответствовать определению односторонности, по- 271 скольку имеют вход/выход фиксированной длины и, таким образом, мы не можем рассматривать их асимптотическое поведение. Тем не менее, вполне возможно предположить, что они являются односторонними в конкретном понимании). жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|