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 (которые равны).
Достарыңызбен бөлісу: