Pencampuran hash asosiatif

Pertimbangkan daftar yang hanya terhubung sendiri dalam pengaturan fungsional murni. Pujiannya telah dinyanyikan dari puncak gunung dan akan terus dinyanyikan. Di sini saya akan membahas satu di antara banyak kekuatannya dan pertanyaan tentang bagaimana ia dapat diperluas ke kelas yang lebih luas dari rangkaian fungsional murni berdasarkan pohon.

Masalahnya adalah sebagai berikut: Anda ingin menguji kesetaraan struktural yang hampir pasti dalam waktu O (1) dengan hashing yang kuat. Jika fungsi hash secara struktural bersifat rekursif, yaitu hash (x: xs) = mix x (hash xs), maka Anda dapat secara tembolok meng-cache nilai hash pada daftar dan memperbaruinya dalam waktu O (1) ketika sebuah elemen dimasukkan ke dalam daftar yang ada . Sebagian besar algoritma untuk daftar hashing secara struktural bersifat rekursif, sehingga pendekatan ini sangat dapat digunakan dalam praktiknya.

Tetapi anggaplah alih-alih daftar yang terhubung secara tunggal Anda memiliki urutan berbasis pohon yang mendukung gabungan dua urutan panjang O (n) dalam waktu O (log n). Agar caching hash berfungsi di sini, fungsi pencampuran hash harus asosiatif untuk menghormati derajat kebebasan yang dimiliki pohon dalam merepresentasikan urutan linier yang sama. Mixer harus mengambil nilai hash dari sub pohon dan menghitung nilai hash dari seluruh pohon.

Di sinilah saya enam bulan lalu ketika saya menghabiskan satu hari untuk merenungkan dan meneliti masalah ini. Tampaknya tidak mendapat perhatian dalam literatur tentang struktur data. Saya memang menemukan algoritma hashing Tillich-Zemor dari kriptografi. Ini bergantung pada perkalian matriks 2x2 (yang asosiatif) di mana bit 0 dan 1 sesuai dengan dua generator subalgebra dengan entri dalam bidang Galois.

Pertanyaan saya adalah, apa yang saya lewatkan? Pasti ada makalah yang relevan dalam literatur tentang kriptografi dan struktur data yang gagal saya temukan dalam pencarian saya. Setiap komentar tentang masalah ini dan tempat yang mungkin untuk dijelajahi akan sangat dihargai.

Sunting: Saya tertarik dengan pertanyaan ini tentang ujung spektrum yang lembut dan kuat secara kriptografis. Di sisi yang lebih lunak dapat digunakan untuk tabel hash di mana tabrakan harus dihindari tetapi tidak menimbulkan bencana. Di sisi yang lebih kuat dapat digunakan untuk pengujian kesetaraan.

ds.data-structures cr.crypto-security functional-programming hash-function Per Vognsen
sumber

Jawaban:

Ditambahkan : Setelah membaca komentar Per, saya pikir jawaban ini hanyalah variasi (buruk) dari algoritma hashing Tillich-Zemor yang telah disebutkan dalam pertanyaan. Saya menarik jawaban ini, tetapi saya meninggalkannya berharap itu (dan komentar) dapat informatif bagi beberapa pembaca.

Sunting : Revisi sebelumnya atas jawaban ini menyarankan untuk menggunakan operasi monoid pada [ m ], tetapi seperti yang ditunjukkan Per dalam komentar, diinginkan untuk menggunakan operasi grup.

Jawaban ini adalah tentang membangun fungsi hash untuk tabel hash yang mudah diimplementasikan. Jaminan kualitas yang dapat dibuktikan tidak diharapkan.

Dengan asumsi bahwa Anda sudah memiliki fungsi hash untuk setiap elemen dari suatu urutan ke himpunan berhingga [ m ] = {1,…, m }, bagaimana menafsirkan setiap elemen [ m ] sebagai elemen dalam grup hingga G dan menggunakan operasi grup pada G ? Anda dapat menggunakan pemetaan apa pun dari [ m ] hingga G , tetapi pemetaan tersebut diharapkan bersifat injeksi agar kami tidak kehilangan informasi dalam nilai hash setiap elemen. Juga diinginkan bahwa grup tidak komutatif sehingga fungsi hash dapat menangkap perbedaan urutan elemen-elemen dalam suatu urutan.

Saya tidak tahu banyak tentang grup hingga yang memungkinkan operasi cepat, tapi saya kira kelompok seperti itu dikenal dalam teori pengkodean. Menggunakan grup urutan simetris setidaknya m mungkin tidak terlalu buruk.

Tsuyoshi Ito
sumber

Ya, hashing Tillich-Zemor juga menggunakan perkalian matriks. Apa yang Anda sarankan tidak dapat bekerja tanpa modifikasi lebih lanjut ala Tillich-Zemor. Misalnya, Anda harus menghindari matriks singular atau Anda mendapatkan akumulasi pada 0, merusak statistik hash. Tillich-Zemor bekerja di ladang Galois; versi sebelumnya dari algoritma mereka memiliki masalah karena mereka menggunakan polinomial pembangkit yang memiliki statistik suboptimal, sehingga bidang Galois tertentu bisa sangat penting.

Per Vognsen

@ Per: Begitu. Terima kasih atas penjelasannya. Lalu bagaimana dengan menggunakan grup yang terbatas? Saya memodifikasi jawaban untuk ini.

Tsuyoshi Ito

Saya setuju. Cara terbaik untuk menghasilkan keluarga kelompok tak terbatas adalah dengan kelompok matriks di atas bidang terbatas (lih. Teorema klasifikasi untuk kelompok sederhana terbatas), sehingga tampaknya algoritma bentuk ini akan dari jenis Tillich-Zemor.

Per Vognsen

@ Per: Saya tidak terbiasa dengan teori grup, dan saya tidak bisa melihat mengapa kelompok matriks lebih dari bidang yang terbatas lebih baik daripada kelompok simetris dalam konteks ini. Bisakah Anda menguraikannya?

Tsuyoshi Ito

Ada beberapa alasan. Untuk satu, Anda tidak dapat menghitung secara efisien dalam kelompok simetris besar, dan Anda perlu kelompok berada di urutan 2 ^ 128 untuk resistensi tabrakan. Sebaliknya, Anda dapat menghitung dengan matriks lebih dari 2 bidang terbatas hingga karakteristik sangat efisien, terutama jika Anda memilih generator polinomial jarang; itu hanya sekelompok manipulasi bit.

Per Vognsen

Keluarga fungsi hash yang hampir universal

{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\}$

memiliki properti yang bagus di sini: , di mana " " menunjukkan penggabungan. Jika Anda cache pada akar setiap pohon kedua nilai hash dan, Anda dapat menghitung hash dari gabungan dari dua pohon di operasi pada . $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$

Ini asosiatif dan cukup cepat. Probabilitas tabrakan adalah . Lihat CLRS atau Dietzfelbinger et al. Dalam "Fungsi Polinomial Hash Handal". $\vec{x} \neq \vec{y}$ $O(\min(|\vec{x}|,|\vec{y}|)/p)$

jbapple
sumber

Salah satu solusinya adalah dengan menggunakan hashing Merkle. Gunakan struktur data pohon biner abadi / persisten. Beri anotasi pada setiap simpul daun dengan hash data yang terkandung di dalam daun itu. Beri anotasi pada setiap simpul internal dengan hash hash pada kedua anaknya. Dengan kata lain, jika adalah simpul internal dengan anak-anak , dan mereka telah dijelaskan dengan nilai hash $n$ $n',n''$ , maka Anda harus membuat anotasi simpul internal dengan nilai hash , di mana $y',y''$ $n$ $y=H(y',y'')$ $H$ adalah fungsi hash. Ini menambahkan hanya kerja ekstra per node yang dibuat untuk semua operasi pohon. Misalnya, Anda dapat mendukung penggabungan dua pohon dalam waktu . $O(1)$ $O(\lg n)$

Pendekatan lain adalah dengan menggunakan hash komutatif, asosiatif. Beri label akar pohon dengan $H(x_1,\dots,x_m)$ $x_1,\dots,x_m$ $m$

DW
sumber