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

188
y, H(y), . . . , H(t−1)(y) и проверяет, является ли H(t−j−1)(SPi) прообразом y для 
каждого i, j так, чтобы H(j)(y) = EPi. Это гарантирует нахождение прообраза, 
пока y находится в коллекции значений (не включая начальные точки), сгенериро-
ванных во время предварительной обработки. Проблема сейчас в том, что время 
работы алгоритма может увеличиться, так как каждое ложное срабатывание вы-
зывает дополнительные O(t) хэш-определений. Можно показать, что прогнози-
руемое количество ложных страбатываний - O(st2/N ). (В последовательности y, 
H(y), . . . , H(t−1)(y) имеются t значений, и в таблице - максимум st разных точек. 
Рассматривая H как случайную функцию, вероятность того, что какая-либо точка 
в последовательности равняется какой-либо точке в таблице - 1/N . Прогнозируе-
мое число ложных срабатываний, таким образом, t•st•1/N = st2/N.) Следователь-
но, пока st2 ≈ N, в чем мы убедимся по другим причинам ниже, прогнозируемое 
число ложных срабатываний будет постоянным, и обращение с ложными сраба-
тываниями потребует только O(t) дополнительных хэш-вычислений.
Учитывая вышеописанное изменение, вероятность инвертирования y = H(x) - это 
как минимум вероятность того, что x находится в коллекции точек (не включая ко-
нечные точки), сгенерированные во время предварительной обработки. Мы сейчас 
снижаем границу этой вероятности, захватив произвольность процесса предвари-
тельной обработки, равно как и единообразный выбор x, рассматривая H как случай-
ную функцию в анализе. Для начала вычислим прогнозируемое число разных точек в 
таблице. Рассмотрим, что случится, когда будет сгенерирована строка i таблицы. На-
чальная точка SPi универсальна и в таблице уже максимум (i − 1) • t разных точек (не 
включая конечные точки), потому ветроятность того, что SPi «новая» (то есть не рав-
ная любому из предыдущих значений) равняется как минимум 1 − (i − 1) • t/N. Какова 
вероятность того, что H(SPi) новая? Если SPi не новая, то H(SPi) почта наверное тоже. 
С другой стороны, если SPi новая, тогда H(SPi) является универсальной (потому что 
мы рассматриваем H как случайную функцию) и поэтому новой с вероятностью как 
минимум 1 − ((i − 1) • t + 1)/N . (теперь у нас есть дополнительная точка SPi.) Таким 
образом, вероятность того, что H(SPi) новая - как минимум
Pr [SPi is new] • Pr [H(SPi) is new | SPi is new]
Продолжая идти этим путем, вероятность того, что H(t−1)(SPi) новая - как 
минимум

189
На что тут следует обратить внимание, так это когда it2 ≤ N/2, вероятность 
этого как минимум 1/2; с другой стороны, так как it2 > N , вероятность доволь-
но мала. Рассматривая последнюю строку, когда i = s, это ознаает, что мы не 
получим значительного дополнительного покрытия, если st2 > N . Хорошим 
условием для параметров, таким образом, будет st2 = N/2. Учитывая это, про-
гнозируемое число разных точек в таблице
Вероятность того, что x «покрыто» - как минимум 
Это дает слабый компромисс времени/пространства, в котором мы можем 
использовать больше пространства (и, соответственно, меньше времени) за 
счет уменьшающейся вероятности инвертирования y. Но мы можем сделать 
лучше путем генерирования T = 4t «независимых таблиц» (Это увеличит как 
пространство, так и время на коэффициент T .) Пока мы можем рассматривать 
вероятности нахождения x в каждой из связанных таблиц как независимую, ве-
роятность того, что как минимум одна из этих таблиц содержит x - 
1 − Pr[no table contains x] = 
Единственный оставшийся вопрос - это как сгенерировать независимую та-
блицу. (обратите внимание, что генерирование таблицы точно так же, как и ра-
нее, - это то же самое, что и добавлять s дополнительных строк к нашей первона-
чальной таблице, что, как мы могли наблюдать, не очень помогает.) Мы можем 
это сделать для такой таблицы i путем применения какой-то функции Fi после 
каждого вычисления H, где F1, . . . , FT все разные. (Хорошим выбором могла 
бы быть установка Fi(x) = x ⊕ ci для какой-то фиксированной константы ci , 
которая разная в каждой таблице.) Пусть Hi Fi ◦ H, то есть Hi(x) = Fi(H(x)).
Затем для таблицы i мы снова подбираем s случайных начальных точек, но для 
каждой такой точки мы теперь вычисляем Hi(SP ), H(2)(SP ), и так далее. По по-
лучении значения y = H(x) для инвертирования, атакующий сначала вычисляет 
yr = Fi(y) и затем проверяет, отвечают ли какие-либо из yr, Hi(yr), . . . , H(t−1)
(yr) конечной точке в таблице i; это повторяется для i = 1, . . . , T . (дальнейшие 
детали мы опускаем.) В то время, как тяжело аргементировать независимость 
формально, данный подход приводит к хорошим результатам на практике.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: