Гомоморфная и некоммутативная хеш-функция?

Question

Существует ли (или исследовалась/опубликована) некоммутативная гомоморфная хеш-функция?LtHashразработанная Facebook и реализованная на Github, это именно та функция, которую я ищу, но LtHash коммутирует, и я хотел бы знать, существует ли некоммутативный алгоритм хеширования.

Я поискал в Интернете и до сих пор не нашел никаких хеш-функций (или даже лучших реализаций), которые были бы гомоморфными и некоммутативными.

Answer 1

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

Чтобы сделать это с помощью LtHash, вы можете использовать первый блок и пары соседних блоков вместо пар блоков с индексами.

Например, LtHash[a,b,c,d,e]обычно было быsum([ h([0,a]), h([1,b]), h([2,c]), h([3,d]), h([4,e]) ])

Вместо этого вы можете использоватьsum([ h(a), h([a,b]), h([b,c]), h([c,d]), h([d,e]) ]).

Теперь вы можете объединять хэши, если знаете начальный и конечный блоки:

Hash([a,b,c,d,e,f])"="Hash([a,b,c]) + Hash([d,e,f]) + h([c,d]) - h(d)