Почти универсальное хеширование строк

9

Вот два семейства хеш-функций на строках x=x0x1x2xm:

  1. За p премьер и xiZp, ha1(x)=aiximodpдля . Dietzfelbinger et al. в «Полиномиальные хеш-функции что .aZpxy,Pa(ha1(x)=ha1(y))m/p

  2. Для , для . Лемир и Казер показали в «Сильно универсальном быстром хешировании строк», что это семейство 2-независимое. Это означает, чтоxiZ2bha=a0a1a2am+12(x)=(a0+ai+1ximod22b)÷2baiZ22bxy,Pa(ha2(x)=ha2(y))=2b

h1 использует только битов пространства и битов случайности, в то время как использует битов пространства и битов случайности. С другой стороны, работает над , что быстро на реальных компьютерах.lgph22bm+2bh2Z22b

Я хотел бы знать, какие другие хеш-семейства почти универсальны (например, ), но работают над (например, ) и используют пространство и хаотичность.h1Z2bh2o(m)

Существует ли такая хэш-семья? Могут ли его члены оцениваться за раз?O(m)

jbapple
источник

Ответы:

5

Да. Вегман и Картер «Новые хеш-функции и их использование в аутентификации и установлении равенства» ( зеркало ) показывают схему, отвечающую заявленным требованиям (почти универсальную, более , сублинейное пространство и случайность, линейная оценка время) на основе небольшого числа хэш-функций, взятых из сильно универсального семейства.Z2b

Это иногда называют «хешированием дерева», и оно используется в «Badger - быстрый и надежно защищенный MAC» Boesgaard et al .

jbapple
источник
-1

Если вы хотите что-то быстрое и что вы можете использовать на практике, вы можете посмотреть криптографическую литературу. Например, poly1305 и UMAC работают быстро, и есть много других. Поскольку 2-универсальные хэши полезны для криптографии, криптографы изучили множество конструкций и нашли чрезвычайно эффективные.

Poly1305 работает как ваш первый тип хеша (называемый хеш полиномиальной оценки ), работая по модулю . Схема показывает хитрые приемы, чтобы сделать это очень быстро на современном компьютере. Количество случайности невелико: 128 бит.21305

Если вы хотите уменьшить количество случайностей и не особенно заботитесь о практичности, вы можете взглянуть на следующую исследовательскую работу:

  • Хеширование и аутентификация на основе LFSR. Хьюго Кравчик. КРИПТО 1994.

Кравчик описывает схему уменьшения количества случайностей в основном, позволяя быть й строкой матрицы Тёплица. Однако схема Кравчика работает над , а не по арифметике по модулю .aiiGF(2b)2b

DW
источник
1
Я ценю ваши отзывы, но этот ответ не касается вопроса.
Jbapple