String hashing hampir universal dalam

Berikut adalah dua keluarga dari fungsi hash pada string $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$ :

1. $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. Untuk , untuk a_i \ in \ mathbb {Z} _ {2 ^ {2b}} . Lemire dan Kaser menunjukkan dalam "Hashing string yang sangat universal cepat" bahwa keluarga ini 2-independen. Ini menyiratkan bahwa \ forall x \ neq y, P_ \ vec {a} (h ^ 2_ \ vec {a} (x) = h ^ 2_ \ vec {a} (y)) = 2 ^ {- b} h 2 → a = ⟨ sebuah 0 a 1 a 2 ... a m + 1 ⟩ ( → x ) = ( a 0 + Σ a i + 1 x i mod 2 2 b ) ÷ 2 b a i ∈ Z 2 2 b ∀ x ≠ y , $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$$a_i \in \mathbb{Z}_{2^{2b}}$$\forall x \neq y, P_\vec{a}(h^2_\vec{a}(x) = h^2_\vec{a}(y)) = 2^{-b}$

$h^1$ hanya menggunakan $\lg p$ bit ruang dan bit keacakan, sedangkan $h^2$ menggunakan $2 b m + 2 b$ bit ruang dan bit keacakan. Di sisi lain, $h^2$ beroperasi lebih dari $\mathbb{Z}_{2^{2b}}$ , yang cepat di komputer yang sebenarnya.

Saya ingin tahu apa keluarga hash lain yang hampir universal (seperti $h^1$ ), tetapi beroperasi lebih dari $\mathbb{Z}_{2^b}$ (seperti $h^2$ ), dan menggunakan ruang $o(m)$ dan keserampangan.

Apakah keluarga hash seperti itu ada? Bisakah anggotanya dievaluasi dalam waktu $O(m)$ ?

Iya. Wegman dan Carter "Fungsi hash baru dan penggunaannya dalam otentikasi dan set kesetaraan" ( mirror ) menunjukkan skema yang memenuhi persyaratan yang dinyatakan (hampir universal, lebih dari , ruang sublinear dan keacakan, evaluasi linear waktu) berdasarkan sejumlah kecil fungsi hash yang diambil dari keluarga yang sangat universal.$\mathbb{Z}_{2^b}$

Ini kadang-kadang disebut "tree hashing", dan digunakan dalam "Badger - A Fast dan Terbukti Aman MAC" oleh Boesgaard et al .

Jika Anda menginginkan sesuatu yang cepat dan dapat Anda gunakan dalam praktik, Anda mungkin melihat literatur kriptografi. Misalnya, poly1305 dan UMAC cepat, dan ada banyak lainnya. Karena hash 2-universal berguna untuk kriptografi, kriptografi telah mempelajari banyak konstruksi dan menemukan konstruksi yang sangat efisien.

Poly1305 bekerja seperti tipe hash pertama Anda (disebut hash evaluasi polinomial ), yang bekerja modulo . Skema ini menunjukkan trik pintar untuk membuat ini berjalan sangat cepat di komputer modern. Jumlah keacakan kecil: 128 bit.$2^{130}-5$

Jika Anda ingin mengurangi jumlah keacakan dan tidak terlalu peduli tentang kepraktisan, Anda dapat melihat makalah penelitian berikut:

• Hashing dan Otentikasi berbasis LFSR. Hugo Krawczyk. CRYPTO 1994.

Krawczyk menjelaskan skema untuk mengurangi jumlah keacakan pada dasarnya dengan membiarkan menjadi baris ke- dari sebuah matriks Toeplitz. Namun, skema Krawczyk bekerja lebih dari , bukan modulo .$a_i$$i$$GF(2^b)$$2^b$