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 . (дальнейшие
детали мы опускаем.) В то время, как тяжело аргементировать независимость
формально, данный подход приводит к хорошим результатам на практике.
Достарыңызбен бөлісу: