Irisan Set Privat
Kenapa ini penting Perusahaan sering ingin tahu pelanggan mana yang mereka miliki bersama, untuk penawaran gabungan atau untuk mengukur apakah sebuah iklan berhasil. Cara mudahnya adalah dengan menukar daftar pelanggan, yang berarti email kamu masuk ke database perusahaan lain. Private Set Intersection memungkinkan mereka menemukan irisan tanpa kedua belah pihak harus menyerahkan daftarnya. Mengetahui cara kerjanya membuat kamu bisa membedakan privasi asli dari "kami hanya membagikan email yang di-hash".
Mengajar kriptografi, bukan keamanan: angka di lab modul ini cukup kecil untuk dibaca dan keacakannya menggunakan seed sehingga penilaian bisa diulang. Sistem nyata menggunakan library yang sudah diperiksa dan angka yang jauh lebih besar. Jangan pernah menyalin kode pengajaran ke dalam produk.
Masalahnya
A toko dan aplikasi masing-masing punya daftar email pelanggan. Mereka ingin email yang ada di both daftar, dan tidak ada yang lain: toko tidak boleh tahu pengguna lain dari aplikasi, dan aplikasi tidak boleh tahu pelanggan lain dari toko.
Irisan himpunan: item yang dimiliki oleh dua daftar yang sama. Private Set Intersection (PSI): cara bagi dua pihak untuk menghitungnya tanpa membocorkan hal lain tentang daftar mereka.
Mengapa "cukup hash saja" gagal
Hash: fungsi yang mengubah teks menjadi acakan dengan panjang tetap (SHA-256 adalah salah satu yang umum). Input yang sama selalu menghasilkan output yang sama, dan kamu tidak bisa menjalankannya secara terbalik secara langsung.
"Kita menukar email yang di-hash, jadi tidak ada yang melihat email aslinya" terdengar aman. Tapi email bisa ditebak. Siapa pun yang memegang daftar email yang mungkin bisa melakukan hash pada setiap tebakan dan mencari kecocokan, seperti mencoba setiap kunci pada gantungan kunci besar. Fungsi naive_reverse kamu akan melakukan hal itu tepat pada 200 email sintetis di dunia latihan. Hashing menyembunyikan data hanya jika input tidak bisa ditebak, dan email, nomor telepon, serta nama bisa ditebak.
Trik dua kunci
Ingat dari pelajaran matematika: memasang kunci rahasia a, lalu kunci rahasia b, hasilnya sama dengan b lalu a. Bayangkan setiap email sebagai sebuah kotak. Alice memasang kuncinya sendiri pada setiap kotaknya dan mengirimnya ke Bob. Bob menambahkan kuncinya dan mengirimnya kembali. Bob juga mengunci kotak miliknya sendiri dan mengirimnya ke Alice, yang kemudian menambahkan kuncinya. Sekarang setiap kotak punya kedua kunci, dan dua kotak dengan email yang sama di dalamnya terlihat identik, tidak peduli kunci mana yang dipasang duluan.
Dalam angka, dengan grup latihan dari watched.leg7a_privacy (P, hash_to_group, random_secret):
- Alice mengirim
blind(alice_items, a): setiap item di-hash ke dalam grup lalu dipangkatkan kea. - Bob menaikkan itu ke
b(reblind) dan mengirimnya kembali dengan urutan yang sama. - Bob mengirim
blind(bob_items, b). - Alice menaikkan nilai Bob ke
a. Setiap nilai kunci ganda miliknya yang muncul di set kunci ganda Bob adalah item bersama. Karena dia menjaga urutannya, dia tahu item mana yang merupakan masing-masing item tersebut.
Kenapa ini aman saat hashing gagal? Untuk menguji tebakan, kamu butuh kedua rahasia, dan setiap sisi menyimpan rahasianya masing-masing. Bob hanya melihat nilai Alice dengan rahasianya aktif, yang terlihat seperti angka acak.
Diffie-Hellman PSI: nama protokol ini, diambil dari ide pertukaran kunci tahun 1976 (dua pihak menggabungkan eksponen rahasia). Versi asli menggunakan kurva eliptik (jenis grup yang berbeda, dengan sifat "urutan tidak penting" yang sama dan angka yang jauh lebih pendek) serta hashing yang teliti.
Jawabannya adalah pengungkapan itu sendiri
Setiap PSI yang sempurna memberi tahu Alice bahwa orang tertentu adalah pelanggan Bob. Jika Bob adalah klinik atau penasihat utang, itu bersifat sensitif. Seringkali sebuah perusahaan hanya butuh berapa banyak pelanggan yang terbagi. Dalam PSI cardinality Bob mengacak balasannya di langkah 2, jadi Alice bisa menghitung kecocokan tapi tidak bisa tahu item mana yang mereka miliki. Minta yang paling sedikit yang menjawab pertanyaan tersebut.
Di bahasa lain
Langkah yang membingungkan di JavaScript dengan BigInt (menggunakan bantuan powMod seperti yang ada di pelajaran matematika):
const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));Dan di Go dengan math/big:
func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
out := make([]*big.Int, len(values))
for i, v := range values {
out[i] = new(big.Int).Exp(v, secret, p)
}
return out
}Untuk produk asli, gunakan library PSI yang sudah diaudit daripada menulis sendiri.
Ringkasan
- Email yang di-hash mudah dibalik dengan daftar tebakan, jadi "kita hanya membagikan hash" bukan privasi.
- Diffie-Hellman PSI mengunci ganda setiap item dengan dua rahasia yang urutannya tidak penting, jadi kecocokan muncul tanpa daftar mana pun terungkap.
- Menjaga urutan menunjukkan item mana yang cocok; mengacak (kardinalitas PSI) hanya menunjukkan jumlahnya.
- Irisan itu sendiri adalah data pribadi, jadi mintalah yang paling sedikit yang bisa menjawab pertanyaan.
Tulis lima fungsi. naive_reverse(hashes, candidates) mengembalikan daftar kandidat yang sudah diurutkan yang SHA-256 hex digest (hashlib.sha256(c.encode()).hexdigest()) ada di hashes. blind(items, secret) mengembalikan [pow(hash_to_group(x), secret, P) for x in items]. reblind(values, secret) memangkatkan setiap nilai ke secret modulo P, sambil menjaga urutannya. psi(alice_items, bob_items, a_secret, b_secret) mengikuti empat langkah pelajaran menggunakan blind dan reblind, dan mengembalikan daftar item Alice yang sudah diurutkan yang juga dimiliki Bob. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) melakukan hal yang sama tapi mengacak balasan Bob dengan rng.shuffle dan hanya mengembalikan jumlah item yang sama.
Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini
Latihan ini akan segera dibuka
Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.
Browser ini memblokir cookie untuk learn.floati.life, jadi pelajaran yang sudah kamu selesaikan di sini tidak bisa dibuka berurutan. Izinkan cookie untuk situs ini dan muat ulang.