Prawie uniwersalny skrót znaków w i sublinearnej przestrzeni

9

Oto dwie rodziny funkcji skrótu na ciągach :x=x0x1x2xm

  1. Dla prime i , dla \ in \ mathbb {Z} _p . Dietzfelbinger i in. pokazane w „Wielomianowe funkcje skrótu są niezawodne”, że \ forall x \ neq y, P_a (h ^ 1_a (x) = h ^ 1_a (y)) \ leq m / p .pxiZpha1(x)=aiximodpaZpxy,Pa(ha1(x)=ha1(y))m/p

  2. Dla xiZ2b , ha=a0a1a2am+12(x)=(a0+ai+1ximod22b)÷2b dla aiZ22b . Lemire i Kaser pokazali w „Silnie uniwersalnym haszowaniu strun jest szybkie”, że ta rodzina jest niezależna od 2. Oznacza to, że xy,Pa(ha2(x)=ha2(y))=2b

h1 używa tylko lgp bitów przestrzeni i bitów losowości, podczas gdy h2 używa 2bm+2b bity przestrzeni i bitów losowości. Z drugiej strony h2 działa na Z22b , co jest szybkie na rzeczywistych komputerach.

Chciałbym wiedzieć, jakie inne rodziny skrótów są prawie uniwersalne (jak h1 ), ale działają na Z2b (jak h2 ) i używają spacji o(m) i losowość.

Czy istnieje taka rodzina mieszająca? Czy jego członkowie mogą być oceniani w czasie O(m) ?

jbapple
źródło

Odpowiedzi:

5

Tak. „Nowe funkcje skrótu Wegmana i Cartera” oraz ich zastosowanie w uwierzytelnianiu i ustawianiu równości ( lustro ) pokazuje schemat spełniający podane wymagania (prawie uniwersalny, ponad , przestrzeń sublinearna i losowość, ocena liniowa czas) na podstawie niewielkiej liczby funkcji skrótu zaczerpniętych z silnie uniwersalnej rodziny.Z2b

Jest to czasami nazywane „mieszaniem drzew” i jest używane w „Badger - szybki i pewnie bezpieczny MAC” Boesgaarda i in .

jbapple
źródło
-1

Jeśli chcesz czegoś szybkiego i którego możesz użyć w praktyce, możesz zajrzeć do literatury kryptograficznej. Na przykład, poly1305 i UMAC są szybkie i istnieje wiele innych. Ponieważ 2-uniwersalne skróty są przydatne w kryptografii, kryptografowie zbadali wiele konstrukcji i znaleźli te, które są niezwykle wydajne.

Poly1305 działa jak twój pierwszy typ skrótu (nazywany hashem oceny wielomianowej ), działając modulo . Schemat pokazuje sprytne sztuczki, dzięki którym działa to bardzo szybko na nowoczesnym komputerze. Losowość jest niewielka: 128 bitów.21305

Jeśli chcesz zmniejszyć liczbę przypadkowości i nie przejmujesz się tak bardzo praktycznością, możesz spojrzeć na następujący artykuł badawczy:

  • Hashowanie i uwierzytelnianie oparte na LFSR. Hugo Krawczyk. CRYPTO 1994.

Krawczyk opisuje schemat redukcji losowości w zasadzie, pozwalając być tym rzędem macierzy Toeplitz. Jednak schemat Krawczyka działa na , a nie na arytmetyczny moduł .aiiGF(2b)2b

DW
źródło
1
Doceniam twoje referencje, ale ta odpowiedź nie odnosi się do pytania.
jbapple