Apakah ada hash berkelanjutan?

Pertanyaan:

Bisakah ada hash (aman secara kriptografis) yang menjaga topologi informasi $\{0,1\}^{*}$ ?

Bisakah kita menambahkan predikat kedekatan yang dapat dihitung secara efisien yang diberikan $h_k(x)$ dan $h_k(y)$ (atau $y$ sendiri) memberi tahu kita jika $y$ adalah sangat dekat dengan $x$ (misalnya jarak Levenshtein atau jarak Hamming dari $x$ dan $y$ kurang dari konstanta tetap $c$ )?

Latar Belakang:

Dengan topologi informasi pada $\Sigma^*$ pada maksud saya ruang topologi dengan poin $\Sigma^*$ dan dengan basis $\{x\Sigma^* : x \in \Sigma^* \}$ .

Cara yang baik untuk berpikir tentang topologi adalah mempertimbangkan set terbuka sebagai properti dari poin yang dapat disetujui / diverifikasi (yaitu jika itu benar, itu dapat memverifikasi / mengamati bahwa itu benar). Dengan mengingat hal ini, set tertutup adalah properti yang dapat disangkal .

Sebuah fungsi $f:\Sigma^* \to \Sigma^*$ kontinu jika gambar terbalik set terbuka terbuka. Dalam kasus kami ini berarti untuk semua $y \in \Sigma^*$ ada $I \subseteq \Sigma^*$ seperti yang

f^{- 1} (y Σ^{*}) = ⋃_{x \in I} x Σ^{*} .

$f^{-1}(y\Sigma^*) = \bigcup_{x\in I} x\Sigma^*.$

Cara yang baik untuk memikirkan topologi informasi adalah melihatnya sebagai pohon string biner. Setiap subtree adalah set dasar terbuka (dan set terbuka lainnya dapat diperoleh dari mengambil gabungan set dasar terbuka).

Ini kadang-kadang disebut sebagai topologi informasi string karena setiap titik dalam $\Sigma^*$ dapat dianggap sebagai pendekatan terbatas pada string / urutan biner. $x$ kurang lebih $y$ iff $x$ adalah substring awal dari $y$ ( $x \sqsubseteq y$ ). Misalnya $0011\Sigma^*$ adalah perkiraan untuk $00110^*$ karena $0011 \subseteq 00110^*$ .

Dan untuk kontinuitas, jika kita mengambil urutan $\{x_i\}_i$ yang mendekati dan konvergen ke urutan biner $y$ (pikirkan $y$ sebagai cabang tak terbatas di pohon dan $x_i$ s sebagai poin pada cabang itu) lalu $\{f(x_i)\}$ konvergen ke $f(y)$ ,

f (y) = ⨆_{i} f (x_{i}) .

$f(y) = \bigsqcup_i f(x_i).$

complexity-theory cryptography hash string-metrics topology Kaveh
sumber

Saya lupa semua yang saya tahu tentang topologi. Mungkinkah membongkar apa artinya "mempertahankan topologi informasi" dalam istilah mandiri? Juga, ketika Anda mengatakan aman secara kriptografis, versi apa yang Anda maksud? Apakah maksud Anda "berperilaku seperti oracle acak", atau maksud Anda "satu arah dan tahan tabrakan"?

@ WD Saya menambahkan beberapa penjelasan, tetapi menulis yang menyebabkan saya memperhatikan bahwa pertanyaan pertama saya tidak jelas. Saya harus berpikir sedikit untuk memperjelasnya. Pertanyaan kedua sepertinya baik-baik saja.

Kaveh

Hashing sensitif-lokal mungkin relevan. en.wikipedia.org/wiki/Locality-sensitive_hashing

zenna

Jawaban:

Untuk fungsi hash kriptografi modern, tidak, tidak ada predikat kedekatan yang dapat dihitung secara efisien, dengan asumsi distribusi aktif $x$ memiliki entropi yang cukup. Intinya adalah bahwa fungsi hash ini dirancang untuk "tidak memiliki struktur", sehingga mereka tidak mengakui hal seperti ini.

Dalam istilah teknis, fungsi hash kriptografi modern berperilaku "seperti oracle acak". Untuk oracle acak, tidak ada predikat kedekatan seperti itu: yang terbaik yang dapat Anda lakukan adalah membalikkan fungsi hash dan kemudian menghitung semua string dekat dan hash mereka. Akibatnya, tidak ada cara untuk melakukan ini untuk fungsi hash kriptografi modern.

Secara heuristik, memang memungkinkan untuk merancang fungsi hash khusus yang mengakui predikat kedekatan yang efisien, dan yang (kira-kira) "seaman mungkin" mengingat fakta ini. Mari kita asumsikan string yang akan kita hash memiliki panjang yang tetap. Misalkan kita memiliki kode koreksi kesalahan yang baik, dan biarkan $D$ menjadi algoritma decoding (sehingga memetakan bit-string ke codeword terdekat, jika bisa).

Untuk mendapatkan skema yang sederhana namun tidak sempurna, bayangkan mendefinisikan $h(x) = \text{SHA256}(D(x))$ . Jika $x,y$ adalah dua string acak yang cukup dekat, maka ada kemungkinan yang layak $h(x)=h(y)$ . Jika $x,y$ tidak dekat, kalau begitu $h(x)$ tidak akan terlihat seperti $h(y)$ , dan kami tidak akan mendapatkan informasi di luar fakta itu $x,y$ tidak dekat. Ini sederhana. Namun, itu juga tidak sempurna. Ada banyak pasangan $x,y$ yang dekat tetapi dari mana kita tidak dapat mendeteksi fakta ini $h(x),h(y)$ (misalnya, karena fungsi decoding $D$ gagal).

Secara heuristik, tampak mungkin untuk meningkatkan konstruksi ini. Pada waktu desain, pilih bit-string acak $r_1,\dots,r_k$ . Sekarang, tentukan fungsi hash berikut:

h (x) = (SHA256 (D (x \oplus r_{1}), \dots, SHA256 (D (x \oplus r_{k})) .

$h(x) = (\text{SHA256}(D(x \oplus r_1), \dots, \text{SHA256}(D(x \oplus r_k)).$

Sekarang jika $x,y$ cukup dekat, kemungkinan ada $i$ seperti yang $D(x \oplus r_i) = D(y \oplus r_i)$ , dan dengan demikian $h(x)_i = h(y)_i$ . Ini langsung menyarankan predikat kedekatan: jika $h(x)$ cocok $h(y)$ di salah satu nya $k$ komponen, lalu $x,y$ dekat; jika tidak, simpulkan bahwa mereka tidak dekat.

Jika Anda juga menginginkan tabrakan, konstruksi sederhana adalah sebagai berikut: biarkan $h_1(\cdot)$ menjadi fungsi hash dengan predikat kedekatan; kemudian $h(x) = (h_1(x), \text{SHA256}(x))$ tahan benturan (setiap tabrakan untuk ini juga merupakan tabrakan untuk SHA256) dan memiliki kedekatan kedekatan (cukup gunakan kedekatan kedekatan untuk $h_1$ ). Anda bisa membiarkannya $h_1(\cdot)$ menjadi fungsi hash yang didefinisikan di atas.

Ini semua untuk jarak Hamming. Edit jarak mungkin secara signifikan lebih sulit.

Dalam membuat konstruksi di atas, saya terinspirasi oleh makalah berikut:

Ari Juels, Martin Wattenberg. Skema Komitmen Fuzzy .

Ari Juels, Madhi Sudhan. Skema Vault Fuzzy . Desain, Kode, dan Kriptografi 38 (2): 237-257, 2006.

Kebetulan: dalam kriptografi, fungsi hash tidak dikunci. Jika Anda menginginkan sesuatu yang penting, Anda mungkin ingin melihat fungsi pseudorandom.

DW
sumber