Ассоциативное смешивание хешей

Рассмотрим простой односвязный список в чисто функциональной обстановке. Его похвалы пели с горных вершин и будут продолжать петь. Здесь я расскажу об одной из его сильных сторон и о том, как ее можно распространить на более широкий класс чисто функциональных последовательностей, основанных на деревьях.

Проблема заключается в следующем: вы хотите проверить почти определенное структурное равенство за O (1) с помощью сильного хеширования. Если хеш-функция является структурно-рекурсивной, то есть hash (x: xs) = mix x (hash xs), тогда вы можете прозрачно кэшировать значения хеш-функции в списках и обновлять их в O (1) раз, когда элемент ограничен существующим списком. , Большинство алгоритмов хэширования списков структурно рекурсивны, поэтому этот подход в высшей степени применим на практике.

Но предположим, что вместо односвязных списков у вас есть древовидные последовательности, которые поддерживают конкатенацию двух последовательностей длины O (n) за O (log n) времени. Чтобы здесь работало кэширование хеша, функция смешивания хеша должна быть ассоциативной, чтобы уважать степени свободы дерева при представлении одной и той же линейной последовательности. Микшер должен взять хеш-значения поддеревьев и вычислить хеш-значение всего дерева.

Это было то место, где я был шесть месяцев назад, когда провел день, обдумывая и исследуя эту проблему. Кажется, в литературе не было уделено внимания структурам данных. Я сталкивался с алгоритмом хеширования Тиллиха-Земора из криптографии. Он основан на умножении матрицы 2x2 (которое является ассоциативным), где биты 0 и 1 соответствуют двум генераторам подалгебры с записями в поле Галуа.

У меня вопрос, что я пропустил? В литературе по криптографии и структурам данных должны быть статьи, которые мне не удалось найти в моем поиске. Будем весьма благодарны за любые комментарии по этой проблеме и возможные места для изучения.

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

ds.data-structures cr.crypto-security functional-programming hash-function Пер Вогсен
источник

Ответы:

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

Редактировать : в более ранней редакции этого ответа предлагалось использовать моноидную операцию над [ m ], но, как указал Пер в комментарии, желательно использовать групповую операцию.

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

Предполагая, что у вас уже есть хеш-функция для каждого элемента последовательности до конечного множества [ m ] = {1,…, m }, как насчет интерпретации каждого элемента из [ m ] как элемента в конечной группе G и использования групповая операция на G ? Вы можете использовать любое отображение от [ m ] до G , но желательно, чтобы отображение было инъективным, чтобы мы не теряли информацию в хэш-значении каждого элемента. Также желательно, чтобы группа не была коммутативной, чтобы хэш-функция могла уловить разницу в порядке элементов в последовательности.

Я не знаю много о конечных группах, которые допускают быстрые операции, но я предполагаю, что такие группы известны в теории кодирования. Используя симметричную группу порядка не менее m не так уж плохо.

Цуёси Ито
источник

Да, хэширование Тиллича-Земора также использует матричное умножение. То, что вы предлагаете, не может работать без дальнейших изменений а-ля Tillich-Zemor. Например, вы должны избегать единичных матриц или получить накопление в 0, разрушая хеш-статистику. Тиллих-Земор работает над полем Галуа; более ранняя версия их алгоритма имела проблемы, потому что они использовали производящий многочлен, который имел субоптимальную статистику, поэтому конкретное поле Галуа может быть очень важным.

Per Vognsen,

@Per: я вижу. Спасибо за объяснение. Тогда как насчет использования каких-либо конечных групп? Я изменил ответ на это.

Цуёси Ито

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

Per Vognsen

@Per: я не знаком с теорией групп, и я не могу понять, почему группы матриц над конечными полями лучше, чем симметричные группы в этом контексте. Можете ли вы уточнить это?

Цуёси Ито

Есть несколько причин. Во-первых, вы не можете эффективно вычислять в больших симметричных группах, и вам нужно, чтобы группы были порядка 2 ^ 128 для сопротивления столкновению. В отличие от этого, вы можете очень эффективно вычислять с помощью матриц над характеристическими 2-мя конечными полями, особенно если вы выбираете разреженный генераторный полином; это просто куча манипуляций.

Per Vognsen

Почти универсальное семейство хэш-функций

{h_{a} (\vec{x}) = \sum a^{i} x_{i} mod p : a \in Z_{p}}

$\{h_a(\vec{x}) = \sum a^i x_i \bmod p: a \in \mathbb{Z}_p\}$

$h_a(\vec{x}) + a^{|\vec{x}|}h_a(\vec{y}) = h_a(\vec{x} \circ \:\vec{y})$ $\circ$ $a^{|\vec{x}|}$ $O(1)$ $\mathbb{Z}_p$

$\vec{x} \neq \vec{y}$ $O(\min(|\vec{x}|,|\vec{y}|)/p)$

jbapple
источник

$n$ $n',n''$ $y',y''$ $n$ $y=H(y',y'')$ $H$ $O(1)$ $O(\lg n)$

$H(x_1,\dots,x_m)$ $x_1,\dots,x_m$ $m$

DW
источник