Сохранение префикса хеш-функции

Question

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

1. f() принимает битовые строки переменной длины в качестве входных и выходных битовых строк;
2. предполагать a а также b битовые строки и a подстрока b, затем f(a) также подстрока f(b);
3. длина строки выходного бита должна быть меньше строки входного бита.

Любая идея?

Answer 1

Не будет такой хеш-функции, которая соответствует вашему критерию.

Предположим, у вас есть такая хэш-функция Hash, которая сохраняет префикс, тогда ответьте на следующие вопросы:

(1) Хэш("а") =? Это может быть что угодно, верно?

(2) Как насчет Hash("xa")=? чтобы сохранить префикс, он должен быть |Hash("xa")-Hash("a")| + Хэш("а")

(3) Как насчет Hash("yxa")=? аналогично (2), это должно быть |Hash("yxa")-Hash("xa")| + |Хэш("xa")-Хэш("a")| + Hash("a") Таким образом, хэш всегда будет иметь большую длину, чем оригинал.