Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Подсказка: Пусть f будет односторонней функцией и p(•) полино-
мом, так что |f (x)| ≤ p(|x|). (Обоснуйте существование такого p). Опреде- лите f r(x) f (x)||10p(|x|)−|f (x)|. Модифицируйте далее f r, чтобы полу- чить функцию, сохраняющую длину, которая остается односторонней. Пусть (Gen, H) – устойчивая к коллизиям функция хэширования, где H ото- бражает строки длины 2n в строки длины n. Докажите, что семейство функций 305 (Gen, Samp, H) является односторонним (см. определение 7.3), где Samp – три- виальный алгоритм, который отбирает равномерную строку длиной 2n. Подсказка: Выбор равномерного x ∈ {0, 1}2n и поиск инверсии y = Hs(x) не гарантирует коллизии. Однако это дает коллизию в большую часть времени. Пусть F –(сохраняющая длину) псевдослучайная перестановка. (a) Покажите, что функция f (x, y) = Fx(y) не является односторонней. (b) Покажите, что функция f (y) = F0n (y) (где n = |y|) не является односторонней. (c) Докажите, что функция f (x) = Fx(0n) (где n = |x|) является односторонней. Пусть f – сохраняющая длину односторонняя функция, а hc – трудный пре- дикат f . Определите tt как tt(x) = f (x)||hc(x). tt обязательно представляет собой псевдослучайный генератор? Докажите свой ответ. Докажите, что односторонние функции существуют тогда и только тогда, ког- да существуют семейства односторонних функций. Обсудите, почему доказа- тельство ваше, не переносится на случай односторонних перестановок. Пусть f – односторонняя функция. Является ли g(x) f (f (x)) обязательно односторонней функцией? А что можно сказать о gr(x) f (x)||f (f (x))? До- кажите свои ответы. Пусть Π = (Gen, Samp, f ) – семейство функций. Функция hc:{0, 1}* →{0, 1} явля- ется трудным предикатом Π, если он является эффективно вычисляемым и если для каждого ppt алгоритма A существует пренебрежимо малая функция negl, такая что Докажите версию теоремы Голдрейха-Левина для этого задания, а именно, если семейство односторонних функций Π (соотв., перестановок) существует, то тогда существует семейство односторонних функций Πr (соотв., перестано- вок) и трудный предикат hc of Πr. Покажите построение псевдослучайного генератора из семейства односторон- них перестановок. Можно использовать результат предыдущего упражнения. Это упражнение предназначено для студентов, которые прошли курс теории сложности или другим образом ознакомились с NP полнотой. (a) Покажите, что существование односторонних функций подразумевает P ƒ= N P. (b) Допустим, что P ƒ= N P. Покажите, что существует функция f , такая что: (1) может быть вычислена в течение полиномиального времени, (2) ее трудно инвертировать в худшем случае (т.е., для всего вероятностного полиномиально-вре- менного A, Prx←{0,1}n [f (A(f (x))) = f (x)] ƒ= 1), но (3) не является односторонней. 306 Пусть x ∈{0, 1}n и обозначим x = x1 • • • xn. Докажите, что если существует односторонняя функция, то существует односторонняя функция f, такая что для каждого i существует алгоритм Ai, такой что (Это упраждение показывает, что невозможно утверждать, что каждая односторон- няя функция скрывает, по меньшей мере, один специфический бит входных данных). Покажите, что если односторонняя функция f имеет трудный предикат, то f является односторонней. Покажите, что если конструкция 7.21 изменяется естественным способом так, что Fk (x) определено для каждой непустой строки x, длиной не более n, то эта конструкция не длиннее псевдослучайной функции. Докажите, что если существует псевдослучайная функция такая, что исполь- зование ключа длиной n, отображает n-битные входы одноразрядных выходов, то существует псевдослучайная функция, которая отображает n-битные входы n-битных выходов. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|