fts encrypted
1.0.0
Catatan: Token mengacu pada token leksikal , bukan token kriptografi . Misalnya, seorang tokenizer dapat berubah 'belajar', 'belajar', 'belajar' semua menjadi token 'belajar'.
Jika Anda tidak memerlukan enkripsi, Tantivy lebih baik dalam segala hal.
Demo GUI dasar menggunakan Dioxus dan set email Enron tersedia di github saya di sini. Ini terutama untuk menunjukkan bahwa kecepatan pencarian layak untuk jenis kumpulan data yang terlihat disimpan di aplikasi sisi klien.
Ini masih merupakan pekerjaan yang sedang berlangsung. Tidak ada jaminan tentang perpustakaan ini atau ketergantungannya, dalam implementasi, secara konseptual atau sebaliknya, sedang dibuat. Tidak ada audit keamanan yang pernah dilakukan. Gunakan dengan risiko Anda sendiri.
Setiap kata kunci dalam pencarian atau indeks di -tokenized. Token dan nama tabel ini terjadi, hash dengan Blake2b-128 dan kemudian dienkripsi dengan AES-128-ECB sebelum disimpan atau digunakan untuk kueri.
Encrypt(Hash(token + table_name))
Mode ECB digunakan untuk enkripsi. ECB menyebabkan plaintext identik menjadi identik, tetapi ini bukan masalah untuk nilai -nilai unik seperti hash dari token dan nama tabel. Ini berarti token yang sama akan memiliki ciphertext yang berbeda jika terjadi pada tabel terpisah.
ID dokumen dienkripsi dengan AES-128-ECB. Ini kemudian dikaitkan dengan penghitung 32-bit.
Karena ID dokumen muncul berkali-kali dan jumlah ID dokumen jauh lebih kecil dari yang dapat disebutkan dengan 128-bit, ID dokumen dapat dikompresi.
Dengan asumsi 1.000 token / dokumen unik, biaya untuk menyimpan kejadian token dalam dokumen adalah:
| Dokumen | Tidak dioptimalkan | 32bit |
|---|---|---|
| 1000 | 16MB | 4MB |
| 10K | 160MB | 40MB |
| 50K | 800MB | 200MB |
| 100K | 1.6GB | 400MB |
| 250k | 4GB | 1GB |
| juta | 16GB | 4GB |
| miliar | 16TB | 4tb |
Perbedaan mewakili nilai dalam urutan sebagai perbedaan di antara mereka. Ini menciptakan nilai -nilai yang dapat diwakili dengan bit yang lebih sedikit, yang memungkinkan bitpacking yang lebih ketat.
Peti bitpacking digunakan untuk blok perbedaan dan bitpacking dari 128 bilangan bulat.
Perbedaan bekerja paling baik ketika nilai diurutkan, tetapi mempertahankan nilai yang diurutkan dan bitpacked akan membutuhkan pengkodean ulang semua nilai ketika entri keluar dari pesanan ditambahkan. Menggunakan pendekatan diamortisasi dengan kumpulan nilai di luar pesanan dapat mengurangi biaya perubahan dengan mengamortisasi mereka.
| Nomor Lapisan | Skema pengemasan | Penyortiran | Berbeda |
|---|---|---|---|
| 0 | None - 32bit (<128 ints) | Tidak ada | TIDAK |
| 1+ | Bitpacker4x (128 INTS) | Lapisan Amoung secara global di atas 0 | Ya |
Sekitar 9.000-10.000 email enron yang lebih pendek dikompresi dan ukuran FTS DB yang dihasilkan adalah 235MB menggunakan pengkodean 32-bit. Menggunakan bitpacking perbedaan dan berlapis diamortisasi mengubahnya menjadi 21MB.
Menghapus file adalah ... mahal ... amortisasi todo
Todo Explore. Sesuatu seperti Rocksdb memtable atau kereta luncur. Simpan perubahan dalam memori, lalu siram setiap 500 ms atau ketika batas memori tercapai.
Bucket mengurutkan kata dengan 3 atau 4 karakter pertama (bukan tokenized), kompres? dan mengenkripsi. Blokir enkripsi dengan sesuatu dengan difusi seperti CBC atau GCM (enkripsi terotenikasi). Ini berarti AutoComplete akan menendang setelah 3 atau 4 karakter. Ini masih dalam tahap konseptual.
Integritas data adalah opsional dengan hashing file database pada waktu tutup dan menyimpan versi hash yang dienkripsi.
Tidak ada difusi pada ID dokumen terenkripsi. Menambahkan difusi akan memerlukan ID dokumen enkripsi menggunakan IV yang dihasilkan secara acak. Ini juga akan membuat kompresi menjadi mustahil. Menyimpan IV akan menambahkan 128-bit per token dan pasangan dokumen (untuk AES CBC).
Berikut ini terlihat oleh penyerang tanpa kunci:
Dalam kasus indeks pada daftar pasien di kantor dokter, penyerang tanpa kunci dapat melihat jumlah pasien dan distribusi token yang digunakan dalam dokumen. Mereka tidak dapat melihat plaintext apa pun, seperti nama atau pengidentifikasi lainnya, dan mereka bahkan tidak dapat melihat ID dokumen dari pasien mana pun. Mereka dapat melihat apakah dua pasien berbagi token pencarian, tetapi tidak ada yang ada tentang siapa pasien atau informasi yang dibagikan.
Misalnya jika indeks pencarian hanya dibangun di atas nama di negara dengan nama belakang yang sama, seperti Vietnam, Anda dapat melakukan analisis frekuensi dan mencari tahu kemungkinan jumlah pasien dengan nama belakang Nguyen (38% dari populasi Vietnam). Ini bergantung pada Anda (distribusi nama keluarga) sebelumnya yang valid untuk dataset yang ada. Itu juga hanya akan efektif terhadap nama -nama umum, yang tidak mengidentifikasi dan tidak mungkin membedakan dokumen yang mengandung bahkan yang kedua dari nama keluarga paling umum di Vietnam (Tran sebesar 11% dan LE pada 10%).
Sekali lagi informasi ditambahkan ke dalam indeks pencarian, seperti usia, kampung halaman, alamat, deskripsi, dll., Kemampuan untuk melakukan analisis frekuensi hampir menghilang.
Salah satu kekhawatiran mungkin bukan repudiasi menyimpan set data unik, di mana analisis frekuensi set data plaintext besar yang diketahui dapat digunakan untuk menunjukkan bahwa tanpa keraguan, perangkat yang diberikan memiliki set data yang diindeks. Ini tampaknya hanya mempengaruhi pembangkang di negara -negara otoriter atau penjahat. Ini dapat dikurangi dengan enkripsi disk penuh saat perangkat mati.
Biarkan d1 menjadi dokumen dengan token t1 . Misalkan t2 menjadi token yang hash yang bertabrakan dengan t1 dan bukan token dari dokumen d1 .
Positif palsu, di mana hasil tambahan yang tidak terkait dimasukkan dalam hasil pencarian, dapat terjadi pada d1 jika pencarian berisi t2 dan bukan t1 .
Negatif palsu, jika hasil yang relevan dihilangkan dari hasil pencarian, hanya dapat terjadi jika salah satu token bertabrakan dihapus untuk dokumen. Ini akan menghasilkan token lain yang "dihapus" juga.
Positif atau negatif palsu hanya berlaku untuk dokumen yang memiliki salah satu token bertabrakan, ketika token bertabrakan lainnya hadir dalam permintaan pencarian. Ini membuat taruhan tabrakan seperti itu sangat rendah.
Risiko aktual dari tabrakan kecil yang lucu untuk hash 128bit (lihat masalah ulang tahun di Wikipedia).
Enkripsi 64 bit hanya menghasilkan beberapa megabyte penghematan ruang untuk indeks yang sangat besar. Bahasa Inggris memiliki sekitar 1.000.000 kata dan lebih sedikit token. 64 juta bit hanya 8MB. Mengingat distribusi tipe hukum kekuatan yang terlihat dalam bahasa, di mana seratus kata teratas dapat terdiri dari setengah frekuensi, penghematan yang sebenarnya akan jauh lebih sedikit.
