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


Шаг t: Выберем универсальное значение для g(It), таким образом, определяя  It+1 и Irt+1. Шаги t + 1 до A − 1



Pdf көрінісі
бет105/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   101   102   103   104   105   106   107   108   ...   249
Криптография Катц

Шаг t: Выберем универсальное значение для g(It), таким образом, определяя 
It+1 и Irt+1.
Шаги t + 1 до A − 1 (если t < A − 1): Выбираем, в свою очередь, универсаль-
ные значения для каждого из g(It+1), g(It+2), . . . , g(IA−1), таким образом, опре-
деляя It+2, It+3, . . . , IA .
Шаги A до 2A − 2 (если t < A − 1): Выбираем, в свою очередь, универсальные 
значения для каждого из 
, таким образом, опре-
деляя 
.
Пусть Coll(k) будет фактом, что нетривиальная коллизия случается на шаге 
k. Тогда
используя Предположение A.9. Для k < t, мы заявляем, 
в действительности, если не случилось 
никакой нетривиальной коллизии на шаге k − 1, значение g(Ik ) выбирает-
ся единообразно на шаге k; нетривиальная коллизия случается, только если 
слечается так, что Ik+1 = g(Ik) ⊕ xk+1 равняется оному из {I1, . . . , Ik } (ко-
торые все разные, поскольку Coll(k − 1) не случилась). Согласно такому же 
рассуждению, мы имеем 
(здесь два зна-
чения It+1, Irt+1 для рассмотрения; обратите внимание, что они не могут рав-
няться друг другу). Наконец, аргументируя, как и ранее, для k > t мы имеем 


145
Уравнение (4.7), мы, таким образом, имеем 
Из Уравнения (4.6) мы получаем Pr[Coll] < q2A2 • 2−n = δ. Наконец, используя 
Уравнени (4.5) мы видим, что
как и утверждалось.
Мы теперь видим, что гладкость подразумевает теорему. Предположим, без 
потери обобщенности, что D всегда совершает q (разных) запросов, каждый из 
которых содержит максимум A блоков. D может выбиратьсвои запросы адап-
тивно (то есть в зависимости от ответов на рпедыдущие запросы), но набор 
запросов D должен быть беспрефиксным.
Дt ля разных X1, . . . , Xq ∈ ({0, 1}n)* и произвольных t1, . . . , tq ∈ {0, 1}n, 
определим, что α(X1, . . . , Xq ; t1, . . . , tq ) равно 1, если и только если D выводит 
1, при запросах X1, . . . , Xq и полчении ответов t1, . . . , tq . (Если, скажем, D не 
делает запрос X1 как свой первый запрос, тогда α(X1, . . . ; . . .) = 0.) Допуская, 
что X˙ = (X1, . . . , Xq ) и ˙t = (t1, . . . , tq ), мы, таким образом, имеем
где, выше, g выбирается единообразно из Funcn, а f выбирается единообразно 
из набора функций, преобразовывающих ({0, 1}n)* в {0, 1}n. Из этого следует
Симметричный аргумент для того, когда D выводит 0, завершает доказательство. 


Достарыңызбен бөлісу:
1   ...   101   102   103   104   105   106   107   108   ...   249




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

    Басты бет