Отличительные криптографические свойства: сопротивление укрытию и столкновению

Question

Я видел из Другой вопрос следующих определений, которые несколько разъясняют:

Столкновение сопротивления:

Дано: х и ч (х)

Трудно найти: y, отличный от x и такой, что h (y) = h (x).

Скрытие:

Дано: h (r | x), где r | x - конкатенация r и x

Секрет: х и крайне маловероятно и случайно выбранный г

Трудно найти: y такой, что h (y) = h (r | x). где r | x - конкатенация r и x

Это отличается от сопротивления столкновению тем, что не имеет значения, у или нет y = r | x.

Мой вопрос:

Означает ли это, что любая хеш-функция h (x) не скрывается, если нет секретного r, то есть хеш-функция h(x), а не h(r|x)? где r | x - конкатенация r и x

Пример:

Скажем, я делаю простую хеш-функцию h(x) = g^x mod(n), где g - генератор для группы. Хеш должен быть устойчивым к коллизиям с p(x_1 != x_2, h(x_1) = h(x_2)) = 1/(2^(n/2)), но я думаю, что он тоже скрывается?

Answer 1

Hashfunctions может предлагать сопротивление столкновению

Обязательства должны быть скрыты.

В отличие от распространенного мнения, эти примитивы не одинаковы!

Строго говоря, вещь, которую вы рассматриваете как хеш-функцию, не может обеспечить сопротивление коллизиям: всегда есть коллизии. Пространство ввода в теории бесконечно, но функция всегда производит вывод фиксированной длины. Терминология на самом деле должна быть «H случайным образом взят из семейства устойчивых к столкновениям функций». Однако на практике мы просто назовем эту функцию устойчивой к столкновениям и проигнорируем, что технически это не так.

Обязательство должно предлагать два свойства: скрытие и переплет. Связывание означает, что вы можете открыть его только для одного значения (именно здесь возникает отношение к сопротивлению столкновению). Сокрытие означает, что невозможно узнать что-либо об элементе, который содержится в нем. Вот почему безопасное обязательство ДОЛЖНО использовать случайность (или существительные, но после того, как все сказано и сделано, они сводятся к одному и тому же). Представьте себе любую хеш-функцию, какой бы идеальной она ни была: вы можете использовать случайный оракул, если хотите. Если я дам вам хэш H(m) значения m, вы можете вычислить H(0), сравнить результат и узнать, является ли m = 0, то есть он не скрывается.

Именно поэтому g^x не является схемой скрытых обязательств. Будет ли это связывание, зависит от того, что вы разрешите в качестве пространства сообщений: если вы разрешите все целые числа, то простая атака y = x*phi(n) приведет к H(y)=H(x). работает. Если вы определите его как ℤ_p, где p - групповой порядок, то он будет полностью обязательным, так как является теоретико-информационной устойчивой к односторонним действиям. (Поскольку пространство сообщений и пространство назначения имеют одинаковый размер, на этот раз одна функция МОЖЕТ быть действительно устойчивой к столкновениям!)