Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| УТВЕРЖДЕНИЕ 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 (которые равны). жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|