Pada tahun 1997, ketika para peneliti medis Massachusetts mulai menyediakan akses ke catatan medis pejabat, pemerintah menghapus nama-nama pasien, alamat mereka, dan nomor jaminan sosial dari daftar. William Weld, saat itu Gubernur, meyakinkan publik bahwa tidak mungkin mengembalikan identitas dengan membuat janji.

Beberapa hari kemudian sebuah surat tiba di kantor Weld yang dikirim oleh seorang mahasiswa dari Massachusetts Institute of Technology. Kutipan dari kartu medis gubernur terlampir dalam amplop.

Meskipun pengidentifikasi yang jelas telah dihapus, para pejabat memutuskan untuk meninggalkan tanggal lahir, jenis kelamin dan kode pos (kode ZIP). Setelah membandingkan data ini dengan rekaman suara, Latanya Sweeney dapat menghitung rekam medis Weld.

Pekerjaan Sweeney dan terobosan lain dalam privasi selama 15 tahun terakhir meningkatkan kekhawatiran keamanan untuk data yang diduga anonim.

"Kami menemukan bahwa intuisi orang tentang data mana yang dianggap pribadi tidak berfungsi dengan baik," kata Frank McSherry dari Microsoft Research Silicon Valley. "Komputer terus meningkatkan kemampuan mereka untuk mengekstraksi data individual dari berbagai informasi yang dianggap aman oleh orang awam."

Mempelajari sejarah medis Anda dapat membantu Anda menemukan gen yang bertanggung jawab atas risiko penyakit Alzheimer, mengurangi jumlah kesalahan di rumah sakit, atau menemukan obat terbaik untuk penyakit. Satu-satunya pertanyaan adalah bagaimana cara mendapatkan semua data ini tanpa memberikan informasi pribadi? Sebuah studi sepuluh tahun tentang topik ini sudah mendekati solusi universal.

Pendekatan ini disebut "privasi diferensial", dan memungkinkan Anda untuk mempublikasikan data sambil melindungi informasi pribadi. Algoritma diferensiasi data memungkinkan peneliti untuk merumuskan permintaan apa pun ke database yang berisi informasi sensitif dan menerima jawaban "kabur" sedemikian rupa sehingga tidak mengungkapkan data pribadi apa pun - bahkan keberadaan data orang tertentu dalam database ini.

"Idenya adalah Anda dapat membiarkan data Anda digunakan tanpa risiko," kata Cynthia Dvork dari Microsoft Research Silicon Valley. Dvork memperkenalkan konsep privasi diferensial (RP) pada 2005 dengan bantuan McSherry, Cobby Nissim, dan Adam Smith.

Metode ini memiliki hak untuk "penolakan yang masuk akal," kata Avrim Blum dari Universitas Carnegie Mellon. “Jika saya ingin berpura-pura bahwa informasi pribadi saya berbeda dari apa yang sebenarnya saya miliki, saya dapat melakukannya. Output dari mekanisme RP dalam praktiknya tidak akan banyak berbeda, tidak peduli apakah itu termasuk saya yang asli atau yang palsu - jadi saya bisa menolak semua yang saya inginkan. ”

Tingkat privasi yang sedemikian tinggi tampaknya tidak mungkin tercapai. Dan pada kenyataannya, tidak ada algoritma RP yang berguna yang akan menghasilkan hasil yang sama persis ketika Anda memberikan data nyata atau fiktif Anda. Tetapi Anda dapat mengizinkan algoritme untuk menghasilkan data yang hampir identik. Tingkat perbedaan dikalibrasi dan mewakili kuantifikasi privasi. Orang atau komunitas dapat memutuskan nilai parameter mana yang sesuai dengan tingkat kehilangan privasi yang dapat diterima, dan kemudian memilih algoritma yang sesuai.

Pakar privasi telah mengembangkan beragam algoritme RP untuk memproses data yang berbeda dan menjawab berbagai pertanyaan tentangnya. Sebagian besar pekerjaan sulit bagi orang-orang yang bukan ahli dalam bidang untuk memahami, oleh karena itu, para ilmuwan sedang mengembangkan bahasa komputer standar yang akan memungkinkan tidak hanya para ahli untuk mempublikasikan data sensitif dengan cara RP, hanya dengan menulis program sederhana. "RP adalah teknologi yang menjanjikan dan sangat menarik," kata Aaron Roth, seorang spesialis ilmu komputer di University of Pennsylvania.

Komite Sensus OnTheMap menggunakan privasi diferensial dengan menerbitkan data tetapi tidak mengungkapkan informasi pribadi

Jarum di tumpukan jerami

Tampaknya untuk mengatasi masalah privasi Anda hanya perlu merilis data umum terkait dengan kelompok besar orang. Tetapi bahkan pendekatan ini penuh dengan pelanggaran terhadap integritas data pribadi.

Misalkan Anda perlu mencari tahu apakah penulisnya menderita diabetes, dan Anda tahu bahwa data saya ada di database. Satu dapat mengurangi hasil dari dua pertanyaan: "Berapa banyak orang yang menderita diabetes dalam database" dan "Berapa banyak orang dalam database, dengan nama selain Eric Clarreich, menderita diabetes."

Kombinasi dari dua pertanyaan ini melanggar privasi saya. Tetapi tidak selalu jelas kombinasi pertanyaan tertentu mana yang dapat melanggar privasi. Menemukan kombinasi seperti itu adalah tugas NP-complete, yaitu, algoritma komputer yang efektif untuk melacak "serangan" seperti itu tidak ada.

Pada 2008, para peneliti menunjukkan bahaya mempublikasikan informasi agregat yang diperoleh dari riset genetika umum - salah satu alat utama untuk menemukan ketergantungan diabetes pada gen. Studi-studi ini melibatkan decoding gen dari kelompok uji dari 100 menjadi 1000 pasien dengan penyakit yang sama, diikuti dengan menghitung frekuensi rata-rata dengan mana salah satu dari 100.000 mutasi terjadi. Jika salah satu mutasi terjadi pada kelompok lebih sering, itu tercatat berpotensi terkait dengan penyakit.

Sebuah tim peneliti yang dipimpin oleh Niels Homer, yang adalah seorang mahasiswa pascasarjana di University of California pada waktu itu, menunjukkan bahwa dalam banyak kasus, mengetahui genom pasien, Anda dapat mengetahui apakah dia adalah bagian dari kelompok pengujian genom. Setelah itu, asosiasi lembaga medis mencabut keputusan bahwa data yang diperoleh dalam studi genetik harus dipublikasikan.

Para peneliti membuat kesimpulan yang bahkan lebih mengejutkan pada 2011 - adalah mungkin untuk mengekstrak informasi pribadi tentang pembelian, dipandu oleh sistem pemberi rekomendasi dengan Amazon, yang memberikan hasil seperti "yang membeli dan juga membeli B dan C". Dengan mengamati perubahan dalam rekomendasi dan membandingkannya dengan ulasan yang dilakukan orang tentang barang yang dibeli, dalam beberapa kasus, peneliti dapat mengatakan bahwa pembeli tertentu membeli barang tertentu pada hari tertentu - bahkan sebelum ia memposting ulasan barang tersebut.

Dalam semua kasus, tindakan privasi tampak memadai, asalkan tidak cukup. Tetapi sudah pada saat ini pendekatan baru untuk melindungi privasi sedang dipersiapkan, diperoleh dengan mencari jawaban untuk pertanyaan utama: apa artinya melindungi privasi?

Privasi dua dunia

Jika peneliti memeriksa basis data pasien dan menemukan hubungan antara merokok dan beberapa bentuk kanker, privasi diferensial tidak akan melindungi seseorang yang merokok di tempat umum dari label orang yang memiliki risiko lebih tinggi jatuh sakit. Tetapi jika merokok adalah rahasia seseorang, disembunyikan di pangkalan, RP akan melindunginya.

"Perbedaan" berarti mempertimbangkan perbedaan dua dunia: di salah satu dunia Anda mengizinkan Anda untuk memasukkan data pribadi Anda ke dalam basis data, dan di dunia lain Anda tidak memperbolehkannya. Kedua dunia tidak akan sepenuhnya identik, tetapi mereka dapat dibuat semirip mungkin, dan hampir mustahil untuk membedakan keduanya. Ini adalah tujuan dari RP.

RP berfokus pada algoritme yang mengeluarkan data, menerima kueri ke database, dan mengeluarkan jawaban - tidak tepat, tetapi dimodifikasi secara acak. Jika Anda mengajukan pertanyaan yang sama pada dua pangkalan yang hanya berbeda dalam data untuk satu orang, Anda pada dasarnya akan mendapatkan jawaban yang sama.

Representasi RP dari lokasi pengguna yang mencari kata "cricket" di mesin pencari

Lebih tepatnya, untuk setiap jawaban yang mungkin, probabilitas penerimaannya harus sama untuk kedua basis data; rasio kedua probabilitas ini harus dibatasi pada angka R yang dekat dengan persatuan. Semakin dekat R ke 1, semakin sulit bagi seorang penyerang untuk mengetahui apakah ia menerima informasi dari basis A atau dari basis B, dan semakin banyak orang yang dilindungi X akan menjadi. memahami data apa yang merujuk pada X. Para

peneliti RP biasanya berbicara tentang logaritma R, dan menyatakannya dengan Ɛ. Parameter ini menghitung kebocoran data pribadi. Semakin dekat Ɛ ke nol, semakin baik algoritma melindungi privasi.

Untuk memahami bagaimana algoritma RP dapat dibangun, mari kita lihat contoh paling sederhana dari algoritma semacam itu. Dia menggunakan skenario di mana si penanya hanya bisa melakukan pertanyaan kuantitatif. Misalnya: "berapa banyak orang dalam database yang memiliki properti C?"

Misalkan jawaban nyata untuk salah satu pertanyaan adalah 157. Algoritma RP akan menambahkan "noise" ke dalamnya - sebelum mengeluarkan jawaban, tambahkan atau kurangi angka acak. Akibatnya, kita mendapatkan 153, 159, atau 292. Penanya mengetahui distribusi probabilitas yang digunakan oleh algoritma, jadi dia tahu tentang seberapa terdistorsi hasil nyata (jika tidak, pengembalian akan sama sekali tidak berguna). Tetapi nomor acak macam apa yang ditambahkan pada jawabannya, dia tidak tahu.

Formula distribusi harus dipilih dengan cermat. Untuk memahami distribusi mana yang menjamin privasi, mari kita bayangkan bahwa penanya yang gigih mencoba mencari tahu apakah saya ada di database. Dia bertanya: "Berapa banyak orang bernama Eric Clarreich yang ada di database?" Misalkan dia menerima jawaban 100. Karena nama ini langka, dia menyadari bahwa jawabannya sebenarnya 0 atau 1. Dia memiliki dua kemungkinan:

A) jawabannya adalah 0, dan algoritma menambahkan 100 sebagai derau;
B) jawabannya adalah 1, dan algoritme yang ditambahkan 99

Kemungkinan memilih 100 dan 99 harus sama. Maka si penanya tidak dapat membedakan antara dua kasus ini. Lebih tepatnya, rasio kedua probabilitas ini tidak boleh melebihi R. yang telah ditentukan sebelumnya. Dan kondisi seperti itu harus dipertahankan tidak hanya untuk pasangan 100 dan 99, tetapi juga untuk dua angka berurutan.

Properti ini memiliki distribusi Laplace. Puncak tajamnya jatuh ke nol, dan kemudian grafik secara bertahap menurun di kedua arah. Untuk itu, kondisi untuk keberadaan angka R (lebar distribusi) terpenuhi, sehingga untuk setiap dua angka berturut-turut rasio probabilitasnya adalah R.

Untuk setiap lebar, ada satu kemungkinan distribusi Laplace. Karena itu, Anda dapat bermain dengan lebar untuk mendapatkan distribusi yang memberikan tingkat privasi yang tepat yang kami butuhkan. Untuk privasi yang kuat, distribusinya akan relatif lebar dan datar. Angka yang jauh dari 0 akan keluar dengan probabilitas yang hampir sama dengan angka yang mendekati nol. Data akan kabur cukup banyak.

Secara alami, ada konfrontasi antara privasi dan utilitas. Semakin banyak privasi yang Anda butuhkan, semakin banyak kebisingan yang harus Anda tambahkan, dan semakin tidak berguna jawabannya. Saat menggunakan distribusi Laplace, jumlah noise yang ditambahkan kembali Ɛ. Jika parameter privasi adalah 0,01, maka algoritma akan mengaburkan indikator kuantitatif sekitar 100.

Semakin besar kumpulan data, semakin sedikit blur yang diberikan akan mempengaruhi utilitas. Dalam basis data yang terdiri dari ratusan catatan, satu blur yang terdiri dari 100 akan mengganggu lebih banyak daripada dalam basis data jutaan rekaman. Menurut Dvork, untuk data skala Internet, yaitu ratusan juta, algoritma sudah menyediakan privasi yang cukup untuk penggunaan praktis.

Dan "noise" menurut Laplace hanyalah tahap pertama dari implementasi RP. Para peneliti telah menghasilkan sejumlah besar algoritma yang jauh lebih kompleks, karena banyak di antaranya rasio utilitas dan privasi melebihi Laplace dalam situasi tertentu.

"Orang selalu menemukan cara untuk meningkatkan, dan masih ada ruang untuk perbaikan," kata Dvork. Mengenai set data yang lebih sederhana daripada Internet, katanya, "ada algoritma untuk banyak tugas."

Dengan algoritma RP, tidak perlu menganalisis masalah untuk pelanggaran privasi dengan hati-hati - perlindungan ini sudah ada di dalam algoritme. Karena pertanyaan-pertanyaan yang mengganggu urusan mereka sendiri biasanya datang ke sejumlah kecil yang terkait dengan orang-orang tertentu, dan pertanyaan-pertanyaan yang sifatnya berbeda mempelajari perilaku kelompok-kelompok besar, jumlah kebisingan tambahan yang meniadakan karakteristik individu akan memiliki sedikit efek pada jawaban atas pertanyaan yang sah.

Dengan RP, masalah para peneliti data, seperti perbandingan silang dengan sumber eksternal, menghilang. Pendekatan matematika tidak mengharapkan penyerang memiliki sumber informasi eksternal yang terbatas.

"Pendekatan RP menyiratkan bahwa penyerang itu mahakuasa," kata McSherry. - Bahkan jika penyerang kembali setelah 100 tahun, mengumpulkan ide-ide dan teknologi komputer sepanjang waktu, mereka masih tidak akan dapat mengetahui apakah Anda berada di database. RP dilindungi dari masa depan. ”

Primitif fundamental

Sejauh ini, kami telah mempertimbangkan situasi di mana seseorang membuat pertanyaan ke database dengan nomor sebagai jawabannya. Tetapi kenyataannya lebih rumit. Peneliti ingin mengajukan banyak pertanyaan pada database. Dan seiring berjalannya waktu, potongan-potongan informasi pribadi Anda akan menuju ke berbagai database, yang masing-masing akan memberikan data tanpa meminta sisanya.

RP memberikan cara yang akurat dan mudah untuk menilai ancaman keseluruhan terhadap privasi ketika peneliti menanyakan semua database di mana data Anda menyajikan beberapa pertanyaan. Misalkan jika data Anda ada dalam dua database, dan data ini diberikan sesuai dengan algoritma yang menyediakan parameter privasi Ɛ1 dan Ɛ2, maka jumlah total informasi pribadi yang bocor tidak lebih dari Ɛ1 + Ɛ2. Rumus yang sama berfungsi untuk database tunggal dengan beberapa kueri. Untuk pertanyaan, kebocoran akan dibatasi di atas m * Ɛ.

Secara teori, kurator basis data dapat memungkinkan peneliti untuk mengajukan sebanyak mungkin pertanyaan, menambahkan jumlah kebisingan Laplace yang diperlukan untuk setiap jawaban sehingga jumlah total data pribadi yang bocor tidak melebihi batas tertentu.

Ternyata batas jawaban numerik tidak terlalu kritis. Banyak pertanyaan lain dapat diubah sehingga menjadi kuantitatif. Misalnya, jika Anda perlu membuat daftar ratusan nama paling populer untuk bayi yang lahir pada tahun 2012, Anda dapat, misalnya, mengajukan urutan pertanyaan seperti "Berapa banyak anak yang diberi nama dimulai dengan A?" Dan memproses hasilnya.

“Salah satu hasil awal pembelajaran mesin mengklaim bahwa apa pun yang dapat dipelajari pada prinsipnya dapat dipelajari menggunakan kueri numerik,” kata Aaron Roth. "Permintaan seperti itu bukan mainan sendiri, tetapi primitif mendasar," yaitu, batu bata, atas dasar yang algoritma yang lebih kompleks dapat dibangun.

Tapi ada yang menangkap. Semakin banyak pertanyaan yang dapat kami ajukan, semakin banyak suara akan ditambahkan ke setiap jawaban. Mari kita lihat contoh dengan nama. Jika kami memutuskan untuk membatasi biaya privasi maksimum Ɛ hingga 0,01, dan namanya akan menjadi 10.000, maka batas privasi untuk setiap masalah adalah Ɛ / 10.000, atau 0,000001. Tingkat kebisingan akan menjadi 10.000 / Ɛ, atau 1.000.000 - dan tingkat ini hanya menghilangkan hasil nyata.

Dengan kata lain, pendekatan "langsung" dengan penambahan noise Laplace untuk setiap jawaban dibatasi oleh jumlah pertanyaan yang mungkin. Untuk memperbaiki situasi, programmer harus mengembangkan primitif yang lebih cocok - "batu bata" algoritmik, dengan bantuan yang, mengingat struktur basis dan tugas tertentu, mereka dapat menjawab lebih banyak pertanyaan dengan akurasi yang lebih besar.

Sebagai contoh, pada tahun 2005, Smith menemukan bahwa tugas dengan nama memiliki struktur khusus: menghapus informasi tentang satu orang dari basis data mengubah jawaban hanya satu dari 10.000 nama. Oleh karena itu, kami dapat menambahkan tidak lebih dari 1 / Ɛ noise untuk setiap jawaban, alih-alih 10.000 / Ɛ, dan privasi jawaban akan tetap dalam batas kami. Primitif seperti itu dapat diterapkan pada kueri "histogram" apa pun - yaitu, kueri tentang berapa banyak orang yang termasuk dalam salah satu dari beberapa kategori yang saling eksklusif, seperti nama.

Ketika Smith memberi tahu Dwork tentang hal ini, “sesuatu di dalam diriku bersukacita,” kata Dwork. "Saya menyadari bahwa kita dapat menggunakan struktur permintaan atau perhitungan dan mendapatkan akurasi respons yang jauh lebih besar."

Sejak itu, para ilmuwan komputer telah mengembangkan perpustakaan besar primitif semacam itu. Dan karena aturan aditif menjelaskan apa yang terjadi pada privasi ketika menggabungkan algoritma, programmer dapat merakit "batu bata" ini menjadi struktur yang kompleks, sambil memantau pembatasan kebocoran privasi.

Untuk menyederhanakan akses ke sistem RP untuk orang-orang yang bukan ahli, beberapa kelompok bekerja untuk menciptakan bahasa pemrograman yang akan memungkinkan kita untuk abstrak dari dasar matematika dari algoritma.

PINQ - salah satu contoh PL untuk RP

Bahasa pemrograman untuk bekerja dengan privasi diferensial, seperti PINQ, menyediakan antarmuka untuk data sensitif dan memungkinkan Anda untuk mengajukan pertanyaan tentangnya, mengubah jawaban untuk melindungi privasi. "Jika Anda bertanggung jawab atas set data, Anda tidak perlu khawatir tentang apa yang dilakukan orang-orang saat permintaan mereka dibuat menggunakan PL ini," kata McSherry, yang menciptakan bahasa PINQ. "Program ini menjamin keamanan pertanyaan."

Sumber daya tidak terbarukan

Karena aturan aditif sederhana untuk Ɛ menetapkan batas atas tepat pada hilangnya privasi ketika basis data berbeda berisi data Anda memberikan jawaban atas pertanyaan, aturan ini, menurut McSherry, mengubah privasi menjadi mata uang.

Misalnya, jika Anda memutuskan batasan mana atas hilangnya privasi untuk Anda secara pribadi dapat diterima sepanjang hidup Anda, Anda kemudian dapat memutuskan untuk "menghabiskan" privasi ini - menukar uang, atau mendukung proyek penelitian yang baik. Setiap kali Anda mengizinkan penggunaan data Anda dalam rilis informasi baru, Anda akan tahu berapa saldo "anggaran" privasi Anda.

Dan kurator set data dapat memutuskan bagaimana menghabiskan jumlah privasi yang ia putuskan untuk rilis - misalnya, mempertimbangkan proposal dari proyek penelitian yang tidak hanya menggambarkan permintaan yang tersedia, tetapi juga jumlah privasi yang digunakan dalam proyek. Kemudian kurator akan dapat memilih proyek mana yang paling baik menggunakan “anggaran” yang ada dari rangkaian informasi ini. Setelah anggaran dihabiskan, kumpulan data ditutup.

"Privasi adalah sumber daya yang tidak terbarukan," kata McSherry. "Begitu kamu menghabiskannya, itu menghilang."

Ketika ditanya nilai apa yang mewakili pembatasan yang dapat diterima pada hilangnya privasi, masyarakat harus menjawab, bukan programmer. Dan setiap orang dapat memiliki jawaban mereka sendiri. Dan sementara prospek menetapkan label harga untuk hal yang tidak berwujud seperti privasi mungkin terlihat menakutkan, analog dari ini sudah ada.

"Ada sumber daya lain dengan properti yang sama - jam hidup Anda," kata McSherry. "Jumlah mereka terbatas, dan setelah kamu menghabiskannya, mereka menghilang." Tetapi karena kita memiliki mata uang dan pasar tenaga kerja, masyarakat kita telah menemukan cara menetapkan label harga untuk waktu manusia. Orang bisa membayangkan bagaimana hal yang sama akan terjadi dengan privasi. "

Matematika mengamankan privasi: pendekatan baru untuk keamanan data

Jarum di tumpukan jerami

Privasi dua dunia

Primitif fundamental

Sumber daya tidak terbarukan

More articles: