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



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

Подсказка: Используйте ключ длиной n2 и, используя гибридный 
аргумент, докажите, что ваша конструкция безопасна.
Докажите, что двухраундовая сеть Фейстеля, использующая псевдослучайные 
раундовые функции (как в выражении (7.15)), не является псевдослучайной.
Докажите, что трехраундовая сеть Фейстеля, использующая псевдослучайные 
раундовые функции (как в выражении (7.16)), не является строго псевдослучайной.
Подсказка: Это значительно труднее, чем в предыдущем упраж-
нении. Используйте отличительный признак, который делает два за-
проса к перестановке, и один запрос к ее инверсии.
Рассмотрим ключевую перестановку F * , определенную с помощью 
F* k (x) = FeistelFk ,Fk ,Fk (x).
(Обратите внимание, что в каждом раунде используется тот же самый ключ). 
Покажите, что F* не является псевдослучайной.
Пусть tt – псевдослучайный генератор с коэффициентом расширения A(n) = n 
+ 1. Докажите, что tt является односторонней функцией.
Пусть X , Y, Z – вероятностный ансамбль. Докажите, что если X ≡ Y и Y ≡ Z, то X ≡ Z.
Докажите теорему 7.32.
Пусть X = {Xn}n∈N и Y = {Yn}n∈N – вычислительно неразличимые вероятност-
ные ансамбли. Докажите, что для любого вероятностного полиномиально-временно-
го алгоритма A, ансамбли {A(Xn}n∈N и {A(Yn}n∈N вычислительно неразличимы.


307
Индекс общего обозначения
Общие обозначения:
• := называется детерминированным присвоением
• Если S – множество, то x ← S обозначает, что x выбирается равномерно из S
• Если A – случайный алгоритм, то y ← A(x) обозначает действующий A на 
входе x, с равномерной случайной лентой , и назначающий выход для y. Мы 
пишем y := A(x; r), чтобы обозначить действующий A на входе x , использую-
щий случайную ленту r , и назначающий выход для y
• ٨ обозначает логическое умножение (оператор И (AND))
• V обозначает логическое отрицание (оператор ИЛИ (OR))
• ⊕ обозначает исключающее ИЛИ (оператор XOR); этот оператор может 
быть применен к отдельным битам или целым строкам (в последнем случае 
оператор XOR действует поразрядно)
• {0, 1}n это множество всех битовых строк длиной n
• {0, 1}≤n то множество всех битовых строк длиной не более n
• {0, 1}* множество конечных битовых строк
• 0n (соотв., 1n) обозначает строку, составленную из n нулей (соотв., n единиц)
• ||x|| обозначает длину двоичного представления (положительного) целого числа x, 
записанного вместе с ведущим битом 1. Обратите внимание, что log x < ||x|| ≤ log x + 1
• |x| обозначает длину двоичной строки x (у которой могут быть ведущие 
нули), или абсолютное значение действительного числа x
• O(•), Θ(•), Ω(•), ω(•) см. приложение A.2
• 0x обозначает, что эти числа представлены в шестнадцатеричном коде
• x||y однозначную конкатенацию строк x и y («однозначная» означает, что x 
and y могут быть восстановлены из x||y)
• Pr[X] обозначает вероятность события X
• log x обозначает логарифм x по основанию 2


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




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

    Басты бет