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
скольку имеют вход/выход фиксированной длины и, таким образом, мы не можем
рассматривать их асимптотическое поведение. Тем не менее, вполне возможно
предположить, что они являются односторонними в конкретном понимании).
Достарыңызбен бөлісу: