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



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

УТВЕРЖДЕНИЕ 4.15 CBCg является (q, A, δ)-гладкой, потому что δ = q2A2 • 2−n.
ДОКАКАЗАТЕЛЬСТВО Для любых X ∈ ({0, 1}n)*, при X = x1, . . . и xi ∈ 
{0, 1}n, пусть Cg (X) обозначает набор входных данных, по которым g высчиты-
вается во время расчета CBCg (X); то есть, еслиX ∈ ({0, 1}n)m , тогда
Cg (X) 
(x1, CBCg (x1) ⊕ x2, . . . , CBCg (x1, . . . , xm−1) ⊕ xm) .
Для X ∈ ({0, 1}n)m и Xr ∈ ({0, 1}n)m , при Cg (X) = (I1, . . . , Im) и
Cg (Xr) = (Ir , . . . , Ir ), скажем, существует нетривиальная коллизия в X , если 
Ii = Ij для 1 mt некоторых i ƒ= j, а также скажем, что существует нетривиальная 
коллизия между X и Xr , если Ii = Ir , но (x1, . . . , xi) ƒ= (xr , . . . , xr ) (в этом по-
следнем случае i может равняться j). Скажем, j 1 j что существует нетривиаль-
ная коллизия в P , если существует нетривиальная коллизия в некоторых X∈ P 
или между некоторыми парами строк X, Xr ∈ P . Пусть Coll будет фактом, что 


143
существует нетривиальная коллизия в P .
Докажем утверждение в два этапа. Во-первых, мы покажем, что обусловлен-
ная тем, что в P нет тривиальной коллизии, вероятность того, что CBCg (Xi) = ti 
для всех i ровно 2−nq . Затем мы покажем, что вероятность того, что существует 
нетривиальная коллизия в P менее чем δ = q2A2 • 2−n.
Рассмотрим, выбирая универсальную g , посредством выбора, одного за дру-
гим, универсальных значений для выходных параметров g касательно разных 
входных параметров. Определение того, существует ли нетривиальная колли-
зия между вумя строками X, Xr ∈ P , может быть выполнено для начала путем 
выбора значений для g(I1) и g(Ir ) (если Ir = I1, эти значения идентичны), а затем 
выбора 11 значений для g(I2) и g(Ir ) (обратите внимание, что I2 = g(I1) ⊕ x2 и 
Ir = g(Ir ) ⊕ xr определяются после того, как g(I1), g(Ir ) были зафиксированы),
и продолжая в том же духе, пока мы не выберем значения для g(Im−1) и g(Ir). В 
частности, значения g(Im), g(Ir ) не обязательно выбирать для того, чтобы опре-
делить, существует ли нетривиальная коллизия между X и Xr. Продолжая дан-
ную цепочку рассуждений, можно определить, случается ли Coll при выборе 
значений g по всем, кроме последних, записей каждого из Cg (X1), . . . , Cg (Xq ).
Предположим, что Coll не случилась после фиксирования значений g касатель-
но разных входных данных, как описано выше. Рассмотрим последние записи в 
каждом из Cg (X1), . . . , Cg (Xq). Эти записи все разные (это и так было понятно 
из факта, что Coll не случилась), и мы заявляем, что значение g по каждой из тез 
точек все еще не было зафиксировано. В действительности, единственным спо-
собом, которым значение g могло бы быть уже зафиксировано по любой из тех 
точек, стало бы условие, если последняя запись Im некоторых Cg (X) равна непо-
следней записи Ij некоторых Cg (Xr). Но поскольку Coll не случилась, это может 
только случиться, если X ƒ= Xr и (xr , . . . , xr ) = (x1, . . . , xm). Но тогда X стала бы 
1 префиксом Xr, нарушающим предположение, что P является беспрефиксной.
Так как g является случайной функцией, вышесказанное означает, что CBCg 
(X1), . . . , CBCg (Xq ) являются универсальными и независимыми от других, равно 
как и все другие значения g , которые уже были зафиксированы. (Это потому что 
CBCg (Xi) является значением g , после вычисления при последней записи Cg (Xi), 
входной значение отличается от всех других входных данных, при которых g уже 
была зафиксирована.) Таким образом, для любых t1, . . . , tq ∈ {0, 1}n мы имеем:
Далее мы покажем, что cCcoull случается с высокой вероятностью верхней гра-
ницы Pr[Coll]. Для разных Xi, Xj ∈ P , пусть Colli,j обозначает факт, что существу-
ет нетривиальная коллизия в X или Xr, или нетривиальная коллизия между X и 
Xr. Мы имеем Coll = Vi,jColli,j , и поэтому граница объединения дает


144
Фиксируя разные X = Xi и Xr = Xj в P , мы сейчас ограничиваем Colli,j. Как 
будет видно из анализа, вероятность максимизируется, когда X и Xr вместе как 
можно дольше, и, таким образом, мы предполагаем, что каждая из них A блоков 
в длину. Пусть X = (x1, . . . , xA ) и Xr = (xr , . . . , xr ), и пусть t будет наибольшим 
целым числом так, 1 A чтобы (x1, . . . , xt) = (xr , . . . , xr ). (Обратите внимание, что 
t < A или X = Xr.) Мы предполагаем, что 1 t t > 0, но анализ, приведенный ниже, 
может быть с легкостью изменен, давая при этом такой же результат, если t = 0.
Мы продолжаем, пусть I1, I2, . . . (соотвественно, Ir , Ir , . . .) обозначают вход-
ные данные 1 2 в g во время процесса вычисления CBCg (X) (соответственно, 
CBCg (Xr)); обратите внимание, что (Ir , . . . , Ir) = (I1, . . . , It). Рассмотрим выбор 
g посредством выбора универсальных значений для 1t выходных данных g, 
одного за одним. Мы сделаем это за 2A − 2 шагов следующим образом:
Шаги 1 через t − 1 (если t > 1): На каждом шаге i, выбираем универсальное 
значение для g(Ii), таким образом, определяя Ii+1 и Iri+1 (которые равны).


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




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

    Басты бет