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

Oto dwie rodziny funkcji skrótu na ciągach :$\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$

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 .$p$$x_i \in \mathbb{Z_p}$$h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$$a \in \mathbb{Z}_p$$\forall x \neq y, P_a(h^1_a(x) = h^1_a(y)) \leq m/p$

2. Dla $x_i \in \mathbb{Z}_{2^b}$ , $h^2_{\vec{a} = \langle a_0 a_1 a_2 \dots a_{m+1}\rangle}(\vec{x}) = (a_0 + \sum a_{i+1} x_i \bmod 2^{2b}) \div 2^b$ dla $a_i \in \mathbb{Z}_{2^{2b}}$ . Lemire i Kaser pokazali w „Silnie uniwersalnym haszowaniu strun jest szybkie”, że ta rodzina jest niezależna od 2. Oznacza to, że $\forall x \neq y, P_\vec{a}(h^2_\vec{a}(x) = h^2_\vec{a}(y)) = 2^{-b}$

$h^1$ używa tylko $\lg p$ bitów przestrzeni i bitów losowości, podczas gdy $h^2$ używa $2 b m + 2 b$ bity przestrzeni i bitów losowości. Z drugiej strony $h^2$ działa na $\mathbb{Z}_{2^{2b}}$ , co jest szybkie na rzeczywistych komputerach.

Chciałbym wiedzieć, jakie inne rodziny skrótów są prawie uniwersalne (jak $h^1$ ), ale działają na $\mathbb{Z}_{2^b}$ (jak $h^2$ ) 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)$ ?

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.$\mathbb{Z}_{2^b}$

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

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.$2^{130}-5$

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ł .$a_i$$i$$GF(2^b)$$2^b$