Ссылки и дополнительная литература
Понятие односторонней функции впервые было предложено Диффи (Diffie)
и Хеллменом (Hellman) [58] и позднее формализовано Яо (Yao) [179]. Труд-
ные предикаты были введены Блумом (Blum) и Микали (Micali) [37], а факт
существования трудного предиката для каждой односторонней функции был
доказан Голдрейхом (Goldreich) и Левином (Levin) [79]. Первая конструкция
псевдослучайного генератора (при специфическом теоретико-числовом пред-
положении трудности) была дана Блумом (Blum) и Микали (Micali) [37]. По-
строение псевдослучайного генератора из любой односторонней перестановки,
было приведено Яо (Yao) [179], а тот результат, что псевдослучайные генерато-
ры могут быть построены из односторонней функции, был показан Хостадом и
др. (H°astad et al.) [85]. Псевдослучайные функции были определены и постро-
ены Голдрейхом (Goldreich), Голдвассером (Goldwasser) и Микали (Micali) [78],
а их расширение до (строгой) псевдослучайной перестановки показали Люби
(Luby) и Ракофф (Rackoff) [116]. Тот факт, что односторонние функции явля-
ются необходимым допущением для большей части криптографии с закрытым
ключом, было показано в [93]. Доказательсто теоремы 7.29 взято из работы [72].
На наше представление сильно повлияла книга Голдрейха (Goldreich) [75],
которую мы настоятельно рекомендуем тем, кто заинтересован в более подроб-
ном изучении темы данной главы.
Упражнения
Докажите, что если существует односторонняя функция, то существует одно-
сторонняя функция f, такая что f (0n) = 0n для каждого n. Обратите внимание,
что для бесконечного множества значений y, легко вычислить f −1(y). Почему
это не противоречит односторонности?
Докажите, что если f является односторонней функцией, то функция g, определен-
ная с помощью g(x1, x2) (f (x1), x2), где |x1| = |x2|, также односторонняя функция.
Заметим, что g показывает половину своих входных данных, но, тем не менее,
является односторонней.
Докажите, что если существует односторонняя функция, то существует одно-
сторонняя функция, сохраняющая длину.
Достарыңызбен бөлісу: |