Введение в современную криптографию


Ссылки и дополнительная литература



Pdf көрінісі
бет222/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   218   219   220   221   222   223   224   225   ...   249
Криптография Катц

Ссылки и дополнительная литература
Понятие односторонней функции впервые было предложено Диффи (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 показывает половину своих входных данных, но, тем не менее, 
является односторонней.
Докажите, что если существует односторонняя функция, то существует одно-
сторонняя функция, сохраняющая длину.


Достарыңызбен бөлісу:
1   ...   218   219   220   221   222   223   224   225   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет