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