Agregasi aman
Kenapa ini penting Sebuah aplikasi kebugaran ingin tahu total langkah yang dijalankan di sebuah kota; pembuat keyboard ingin tahu seberapa sering sebuah kata diketik di semua ponsel. Dalam setiap kasus perusahaan butuh satu angka dari banyak perangkat. Secure aggregation membiarkannya mempelajari total tersebut tanpa pernah melihat nilai dari satu orang pun, dan ini mengejutkan sederhana.
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.
Trik gaji
Tiga teman ingin tahu rata-rata gaji mereka tanpa ada yang membocorkan gaji masing-masing. Orang pertama menambahkan angka acak yang besar ke gajinya dan membisikkan hasilnya ke orang kedua. Dia menambahkan gajinya dan membisikkannya lagi. Orang ketiga menambahkan gajinya dan mengembalikannya. Orang pertama mengurangi angka acaknya, dan totalnya pun keluar. Setiap bisikan terlihat seperti angka acak bagi siapa pun yang mendengarnya.
Secure aggregation: menghitung total (atau rata-rata) dari nilai banyak orang sehingga tidak ada satu nilai pun yang terungkap ke siapa pun, termasuk ke server yang mengumpulkannya.
Additive secret sharing: membagi angka rahasia menjadi beberapa shares yang terlihat acak sendiri tapi jika dijumlahkan menjadi angka rahasia. Satu share saja, atau grup mana pun yang kehilangan setidaknya satu share, tidak akan mengungkap apa pun tentang rahasia tersebut.
Cara kerja shares
Untuk membagi angka 7,350 menjadi tiga bagian, pilih dua angka acak dan pilih angka ketiga supaya ketiganya berjumlah 7,350. Dengan aritmatika wrap-round (modulus M, di sini 2 pangkat 32, sedikit di atas 4 miliar), setiap bagian adalah angka acak seragam pada dirinya sendiri:
M = 2 ** 32
s1, s2 = 3919211450, 120775123 # random
s3 = (7350 - s1 - s2) % M # whatever makes it add up
print((s1 + s2 + s3) % M) # 7350
Kenapa pakai wrap round? Tanpa itu, sebuah share kadang bisa negatif atau terlalu dekat dengan secret. Dengan itu, setiap nilai share punya peluang yang sama apa pun secretnya, jadi satu share tidak membawa informasi apa pun.
Banyak perangkat, beberapa server
Sekarang setiap ponsel membagi jumlah langkahnya menjadi satu bagian per server dan mengirim bagian 1 ke server 1, bagian 2 ke server 2, dan seterusnya. Setiap server menjumlahkan bagian yang diterima. Total setiap server masih terlihat acak. Hanya saat total server digabungkan barulah total kota yang asli muncul. Selama server tidak mengumpulkan bagian mentah untuk satu ponsel, nilai tidak ada ponsel yang pernah terlihat.
Versi dunia nyata
Sistem yang digunakan untuk melatih model di banyak ponsel (dikenal sebagai federated learning) menggunakan varian yang lebih cerdas dengan satu server: pasangan perangkat menyepakati mask acak yang saling meniadakan saat semuanya dijumlahkan, ditambah langkah ekstra untuk menangani ponsel yang terputus di tengah jalan. Ide intinya adalah yang akan kamu bangun: potongan yang tampak acak yang hanya masuk akal jika digabungkan.
Apa yang tidak dilakukan oleh secure aggregation
Totalnya terungkap dengan tepat. Jika hanya dua orang yang berkontribusi dan satu orang tahu nilainya sendiri, mereka bisa menguranginya dan mengetahui nilai orang lain. Jika total itu sendiri sensitif, tambahkan noise differential privacy ke dalamnya juga. Kedua alat ini bekerja dengan baik bersamaan: agregasi menyembunyikan input, DP menyembunyikan efek setiap orang pada output.
Di bahasa lain
Splitting di JavaScript, menggunakan 32-bit wrap-round dengan >>> 0 dan sumber random aman browser:
function split(value, n) {
const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
shares.push((value - sum) >>> 0);
return shares;
}Dan di Rust, di mana wrapping_sub pada u32 melakukan wrap-round untukmu:
let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));Ringkasan
- Secure aggregation mengungkap total tapi tidak kontribusi tunggal.
- Additive secret sharing membagi sebuah nilai menjadi bagian acak yang jika dijumlahkan akan menghasilkan nilai tersebut, menggunakan aritmatika wrap-round.
- Setiap server hanya melihat bagian yang tampak acak; hanya total semua server bersama yang memberikan jawabannya.
- Totalnya sendiri terlihat jelas, jadi pasangkan dengan noise DP saat total tersebut bisa membahayakan seseorang.
Tulis tiga fungsi, menggunakan M (2 to the 32) dari dunia latihan. split(value, n, rng) mengembalikan daftar bagian n: n - 1 pertama dari rng.randrange(M), yang terakhir sama dengan (value - sum(shares)) % M. combine(shares) mengembalikan sum(shares) % M. aggregate(values, n_servers, rng) membagi setiap nilai dengan split, menambahkan bagian j ke dalam server_totals[j] (mod M), dan mengembalikan tuple (total, server_totals) di mana total = combine(server_totals).
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.