Какие хеш-функции ортогональны друг другу?

Question

Я заинтересован в многоуровневой проверке и исправлении целостности данных. При использовании нескольких кодов с исправлением ошибок (они могут быть 2 кодами одного типа). У меня сложилось впечатление, что система, использующая 2 кода, достигла бы максимальной эффективности, если бы 2 используемых хэш-кода были ортогональны друг другу.

Есть ли список, какие коды ортогональны к чему? Или вам нужно использовать ту же функцию хеширования, но с другими параметрами или использованием?

Я ожидаю, что ecc первого уровня будет кодом Рида-Соломона, хотя на самом деле я не контролирую эту первую функцию, поэтому я не могу использовать один код с улучшенными возможностями.

Обратите внимание, что меня не интересует безопасность шифрования.

Изменить: это не дубликат

• Когда хеш-функции ортогональны друг другу? из-за этого, по существу, спрашивают, каково определение ортогональных хеш-функций. Я хочу примеры того, какие хэш-функции являются ортогональными.

Answer 1

Я не уверен, что можно даже перечислить все ортогональные хеш-функции. Тем не менее, вы попросили только несколько примеров, поэтому я постараюсь предоставить некоторые, а также некоторую интуицию относительно того, какие свойства, по-видимому, приводят к ортогональным хеш-функциям.

Из смежного вопроса эти две функции ортогональны друг другу:

Domain: Reals --> Codomain: Reals
f(x) = x + 1
g(x) = x + 2

Это довольно очевидный случай. Легче определить ортогональность, если хеш-функции (обе) являются идеальными хеш-функциями, такими как они. Обратите внимание, что термин "совершенный" подразумевается в математическом смысле, а не в том смысле, что их следует использовать в качестве хеш-функций.

Это более или менее тривиальный случай, когда совершенные хеш-функции удовлетворяют требованиям ортогональности. Всякий раз, когда функции инъективны, они являются совершенными хеш-функциями и, следовательно, ортогональны. Подобные примеры:

Domain: Integers --> Codomain: Integers
f(x) = 2x
g(x) = 3x

В предыдущем случае это инъективная функция, но не биективная, поскольку в кодомене существует ровно один элемент, сопоставляемый каждому элементу в области, но в кодомене есть много элементов, которые вообще не отображаются. Они все еще достаточны как для идеального хеширования, так и для ортогональности. (Обратите внимание, что если бы домен / кодомен были реальными, это было бы биекцией.)

Функции, которые не являются инъективными, более сложны для анализа. Однако всегда бывает так, что если одна функция инъективна, а другая нет, они не ортогональны:

Domain: Reals --> Codomain: Reals
f(x) = e^x // Injective -- every x produces a unique value
g(x) = x^2 // Not injective -- every number other than 0 can be produced by two different x's

Таким образом, одна хитрость заключается в том, чтобы знать, что одна функция инъективна, а другая нет. Но что, если ни один не является инъективным? В настоящее время я не знаю алгоритма для общего случая, который будет определять это, кроме грубой силы.

Domain: Naturals --> Codomain: Naturals
j(x) = ceil(sqrt(x))
k(x) = ceil(x / 2)

Ни одна из функций не является инъективной, в этом случае из-за наличия двух очевидных неинъективных функций: ceil а также abs в сочетании с ограниченным доменом. (На практике большинство хеш-функций не будет иметь домена более разрешающего, чем целые числа.) Проверка значений покажет, что j будет иметь неуникальные результаты, когда k не будет и наоборот

j(1) = ceil(sqrt(1)) = ceil(1) = 1
j(2) = ceil(sqrt(2)) = ceil(~1.41) = 2
k(1) = ceil(x / 2) = ceil(0.5) = 1
k(2) = ceil(x / 2) = ceil(1) = 1

Но как насчет этих функций?

Domain: Integers --> Codomain: Reals
m(x) = cos(x^3) % 117
n(x) = ceil(e^x)

В этих случаях ни одна из функций не является инъективной (из-за модуля и предела), но когда они сталкиваются? Что еще более важно, для каких наборов значений x они оба сталкиваются? На эти вопросы сложно ответить. Я подозреваю, что они не ортогональны, но без конкретного контрпримера я не уверен, что смогу доказать это.

Конечно, это не единственные хеш-функции, с которыми вы можете столкнуться. Итак, хитрость в определении ортогональности заключается в том, чтобы сначала убедиться, что они оба инъективны Если это так, они ортогональны. Во-вторых, посмотрите, является ли один из них инъективным. Если это так, они не являются ортогональными. В-третьих, посмотрите, можете ли вы увидеть фрагменты функции, из-за которых они не являются инъективными, посмотрите, можете ли вы определить ее период или особые случаи (например, x=0) и попробуйте создать контрпримеры. В-четвертых, посетите https://math.stackexchange.com/ и надеемся, что кто-то может сказать вам, где они нарушают ортогональность, или доказать, что они этого не делают.