1. Сценарий
Предположим, что у нас есть источник, генерирующий одно случайное значение, скажем, в минуту. Итак, у нас есть случайное значение $x_1$ в $1$минута, $x_2$ в $2$ая минута, $\ldots$, $x_n$ в $n$й минуты и так далее.
Распределение значений $x_1, x_2, \ldots$ не является полностью равномерным случайным, а подчиняется следующему правилу: для любого $i\ge 1$, $x_i = (y_i, y_{i+1})$, куда, $y_i$ является уникальным идентификатором $x_i$, и $у_{я+1}$ уникальный идентификатор предстоящего $х_{я+1}$ что прибудет в следующую минуту.
Другими словами, в любой заданный $я$ая минута, текущая $x_i$, и следующий $x_{я+}$ известны, но тот, что после $х_{я+2}$ абсолютно неизвестно или случайно. Ниже приведен пример:
Минута 1: x_1 = (334234, 234829129)
Минута 2: x_2 = (234829129, 983220)
Минута 3: x_3 = (983220, 831231236347)
...
Минута n: x_n = (643532754, 3534611)
Один из способов хэшировать эти $n$ values, по порядку, заключается в хешировании каждого значения по мере его поступления, например. $h_1 = f(x_1)$, затем соедините его со следующим вновь прибывшим, например. $h_2 = f(x_2 \параллельно h_1)$.
Другими словами, хэш упорядоченного списка ввода в $n$ая минута определяется рекурсивно как $h_n = f(x_n \параллельно h_{n-1})$, с базовым случаем $h_1 = f(x_1)$.
Преимущество этого подхода в том, что для того, кто каким-то образом запускает этот процесс с самого начала, в каждую минуту и время выполнения, и пространство-время находятся в равновесии. $О(1)$, так как он может кешировать хэш предыдущей минуты.
Недостатком этого подхода является то, что для тех, кто не следил за процессом и хочет проверить, $h_n$ действительно является хэшем всей последовательности, ему придется начать с самого начала с $h_1$, и повторяйте всю цепочку до тех пор, пока $h_n$. По сути, этот процесс проверки займет $ О (п) $ пространство и $ О (п) $ время.
2. Червоточина
Было бы хорошо, если бы было возможно, чтобы в каждый $n$ много хешированных цепочек, мы можем обнаружить червоточина $w_n$ который имеет следующие свойства:
- Однажды $n$й хэш, $h_n$, законно рассчитывается $h_1$ следуя полной рекурсии ранее, только тогда червоточина $w_n$ становится обнаруженным. В противном случае нахождение $w_n$ практически невозможно.
- Для данного $h'_n$ хэш, который, как утверждается, $h_n$, червоточина может сократить проверку следующим образом:
$$
w_n(h_1, h'_n) = \begin{случаи}
1 & \text{если $h'_n = h_n$}\
0 & \текст{еще}\
\end{случаи}
$$
- Асимптотическое наихудшее время выполнения, а также асимптотическое наихудшее пространство для вычислений $w_n(h_1, h'_n)$ не хуже, чем $O(\log п)$. Если это возможно сделать в $О(1)$А еще лучше конечно.
Запись. Это отличается от прообраз атака хэш-функций. Разница заключается в следующем:
Атаки с прообразом позволяют злоумышленнику создать произвольный ввод, который дает желаемый целевой хэш.
Эта червоточина $w_n$ не позволяет подделывать любой произвольный ввод, а скорее показывает скрытый путь быстрого доступа, который работает только для связывания определенного ввода, который позволяет связать $h_n$ вернуться к $h_1$, и что единственный способ обнаружить такую червоточину — законно вычислить $h_n$ первый.
Может быть, мы можем назвать такую червоточину условной прообразной атакой, которая не приносит пользы противнику.
3. Вопрос
Известны ли такие червоточины для проверки или вообще возможны?
