Demokrasi bukan suara, itu penghitungan suara.
Tom StoppardUntuk peneliti kriptografi, pemungutan suara elektronik terutama tidak terhubung dengan mesin pemungutan suara dan tidak dengan pemungutan suara online - itu hanya
bidang untuk penelitian matematika . Penelitian e-voting berkaitan dengan pembuatan protokol, komponen matematika utama,
sistem pemungutan suara yang aman dan
dapat diverifikasi , atau sistem di mana auditor dan pemilih independen dapat dengan aman memverifikasi kebenaran penghitungan suara. Sistem ini bukan karya teoretis sederhana, tetapi sudah merupakan teknologi nyata yang digunakan untuk pemilihan nyata: di Tacoma Park, Maryland, pemilih mempercayai sistem
Scantegrity II berdasarkan kertas suara kertas tak kasat mata, dan kriptografi sendiri menggunakan sistem pemungutan suara online
Helios untuk
pemilihan kepemimpinan.
Pemungutan suara elektronik adalah topik yang sangat rumit, jadi dalam artikel ini saya akan membatasi diri pada konsep-konsep kunci: apa arti verifikasi suara yang aman, bagaimana saya bisa menghitung suara tanpa mengalamatkan masing-masing secara individu, dan apa yang mencegah kecurangan pemilih. Saya tidak akan memberi Anda deskripsi lengkap tentang seluruh protokol pemungutan suara elektronik dengan semua nuansanya, tetapi mereka yang berharap dapat secara mandiri mencari pekerjaan untuk topik ini,
yang jumlahnya banyak .
Konfirmasi Aman
Apa yang diharapkan dari sistem pemungutan suara yang aman?
Pertama, dan yang paling jelas: Anda perlu memeriksa bahwa surat suara dihitung dengan benar, yaitu, sehingga semua orang dapat mengonfirmasi bahwa penghitungan akhir dilakukan sesuai dengan jumlah surat suara yang diisi oleh pemilih. Cek tidak boleh memberikan informasi tambahan, kecuali untuk total. Secara khusus, peninjau tidak boleh menebak siapa yang memberikan suara. Ini sama dengan penghitungan kertas suara manual klasik.
Kedua, perlu bahwa setiap pemilih dapat memastikan bahwa suaranya dihitung, dan dihitung dengan benar. Ini harus dilakukan tanpa mengungkapkan suaranya, dan dalam kasus yang lebih umum, pemilih seharusnya tidak dapat membuktikan siapa yang dia pilih. Hal ini dilakukan untuk menghilangkan paksaan, dan untuk memungkinkan pemilih bebas memilih seorang kandidat tanpa takut akan konsekuensi dari pilihan mereka.
Akhirnya, sistem pemungutan suara harus dilindungi dari penipuan: pemilih seharusnya tidak dapat memilih lebih dari satu kali, dan seharusnya tidak ada kemampuan untuk mengubah atau menyalin surat suara. Selain itu, hanya pemilih terdaftar yang dapat memilih.
Jadi untuk meringkas: kita perlu pengawasan publik, kepercayaan pemilih, resistensi terhadap paksaan, dan integritas pemilu. Prinsip-prinsip ini diajukan dalam studi fundamental oleh Chaum, Neff dan lainnya, yang diterbitkan pada awal 2000-an.
Prinsip dasar
Kebanyakan protokol e-voting klasik berfungsi sebagai berikut:
- Pemilih menerima token dalam bentuk buletin, yang berubah sesuai pilihannya. Pemilih yang berbeda menerima surat suara yang berbeda.
- Pemilih mengenkripsi surat suara (menggunakan jenis enkripsi khusus yang memungkinkan keajaiban pemilihan elektronik berfungsi, dan mengirimkannya sehingga penyelenggara pemilihan menerima surat suara terenkripsi.
- Panitia menerbitkan buletin terenkripsi di papan buletin, "saluran siaran publik dengan memori", dalam jargon cryptographers - sederhananya, pada sesuatu seperti Pastebin.
- Panitia menggabungkan surat suara terenkripsi untuk menghitung hasil yang di-cache. Kemudian mereka memecahkan kode itu (tetapi bukan surat suara itu sendiri!) Dan mempublikasikan hasilnya.
- Setelah menerima hasil dan suara terenkripsi, siapa pun dapat memeriksa kebenarannya.
Secure Count: Enkripsi Homomorfik
Pada langkah ke-4, penyelenggara menggabungkan kriptogram untuk membuat kriptogram baru yang mengenkripsi jumlah suara individu. Untuk ini, skema pemilihan elektronik menggunakan skema enkripsi Enc (), di mana Anda dapat menghitung Enc (v1 + v2), hanya memiliki Enc (v1) dan Enc (v2) yang tersedia, dan tanpa mengetahui kunci enkripsi. Skema enkripsi semacam itu disebut
homomorfik .
Misalnya, jika sangat disederhanakan, pemilih AS melakukan hal berikut pada 8 November:
- Mereka menerima buletin Clinton dan buletin Trump dari penyelenggara (untuk kesederhanaan, kami hanya akan mempertimbangkan dua kandidat).
- Mereka menulis Enc (1) di satu surat suara dan Enc (0) di sisi lain, menggunakan kunci publik yang dikeluarkan oleh penyelenggara sebagai kunci.
Surat suara terenkripsi kemudian diterbitkan di papan pengumuman bersama dengan ID pemilih. Saya tahu semua yang memilih, tetapi tidak mungkin untuk memahami untuk siapa sebenarnya, karena setiap Enc (0) dan Enc (1) unik, dan kami menggunakan enkripsi yang kuat dan acak. Jika enkripsi bersifat deterministik, pemilih dapat dipaksa untuk mengungkapkan suaranya dengan menghitung Enc (0) lagi dan membandingkannya dengan nilai di papan tulis.
Akhirnya, penyelenggara menggabungkan semua surat suara untuk Clinton dan mendapatkan hasil dari Enc (jumlah suara untuk Clinton), dan kemudian mereka melakukan hal yang sama dengan surat suara untuk Trump dan mendapatkan Enc (jumlah suara untuk Trump). Kemudian mereka mengambil kunci dekripsi dan mendekripsi dua nilai ini, menyatakan pemenang.
Bagaimana menemukan skema enkripsi homomorfik? Cukup mudah - sirkuit seperti RSA dan ElGamal adalah homomorfik dalam bentuk dasarnya karena memenuhi persamaan
Enc (v1) × Enc (v2) = Enc (v1 × v2)
Tetapi ini bukan yang kita butuhkan - ini adalah homomorfisme multiplikasi, tetapi kita membutuhkan aditif. Ada trik yang mengubah skema RSA dan ElGamal menjadi homomorfik aditif, tetapi sebaliknya saya akan menunjukkan skema yang kurang dikenal yang langsung
menambah homomorfik:
kriptosistem Paye mengenkripsi pesan v1 ke
Enc (v1) = g
v1 r1
n mod n
2Di mana n = pq dan g adalah tetap, dan r1 adalah bilangan bulat acak dari] 1; n
2 [. Oleh karena itu, kami memiliki:
Enc (v1) × Enc (v2) = (g
v1 r1
n ) × (g
v2 r2
n ) mod n
2 = g
v1 + v2 (r1r2)
n mod n
2 = Enc (v1 + v2)
Artinya, skema Peye dapat digunakan untuk menghitung suara terenkripsi.
Untuk menipu, seorang pemilih mungkin ingin menulis Enc (10000), bukan Enc (1) dalam pemungutan suara untuk menambahkan suara ke kandidat. Dalam hal niat buruk, Anda dapat menulis Enc (very_large_number) sehingga ini mengarah pada overflow keseluruhan dan kegagalan seluruh sistem. Bagaimana cara menjamin validitas suara (0 atau 1) tanpa dekripsi?
Solusinya adalah
tanpa pengetahuan interaktif (NIZK). Bukti NINR adalah objek kriptografi yang sangat kompleks dan sangat kuat: dalam kasus kami, ini akan memungkinkan pemilih untuk membuktikan bahwa kriptogram mereka berisi 0 atau 1, tetapi tanpa menunjukkan pesan terenkripsi itu sendiri. Dalam kasus umum, bukti NINR memungkinkan peribahasa meyakinkan verifier kebenaran pernyataan dengan mengirimnya hanya kumpulan data tanpa jenis interaksi lainnya.
Mungkin sistem paling sederhana dengan nol pengungkapan adalah
skema Schnorr : katakanlah Anda tahu solusi untuk masalah logaritma diskrit (tugas sulit di balik
DSA dan enkripsi pada kurva eliptik), dan Anda ingin membuktikan bahwa Anda tahu solusinya tanpa mengungkapkan solusi itu sendiri. Yaitu, Anda tahu x sedemikian sehingga g
x = y mod p, dan pemeriksa hanya tahu g, y dan p. Untuk meyakinkan pengulas, Anda memainkan game berikut:
- Pilih angka acak r dan kirim nilai g r ke tester (kewajiban).
- Anda mendapatkan nomor acak dari tester (panggilan).
- Kirim ke verifier s = r + cx.
- Peninjau menghitung g s = g r + cx dan memverifikasi bahwa itu sama dengan g r × y c = g r × (g x ) c .
Dalam protokol interaktif ini, prover tidak mengungkapkan nilai x, karena hanya mengirimkan angka acak. Namun, hanya prover yang tahu x dapat mengirim s, melewati tes terakhir.
Untuk mengubah protokol interaktif seperti itu menjadi protokol non-interaktif (protokol yang dapat dikirim dengan satu set data), NINR-proof dibangun. Kami memainkan game ini sendiri dan berpura-pura menjadi penguji sehingga penguji yang sesungguhnya memastikan bahwa kami tidak dapat menghasilkan NINR-proof tanpa mengetahui pernyataan yang terbukti.
Kesimpulan
Gagasan utama yang dibahas dalam artikel ini:
- Masalah utama dengan sistem pemungutan suara elektronik yang aman adalah kemampuan mendengar publik. Ini dicapai dengan menerbitkan buletin terenkripsi di forum yang dapat diakses publik. Pemilih juga harus menggambarkan mekanisme yang melakukan konfirmasi itu sendiri.
- Kebenaran pemungutan suara dikonfirmasi dengan memberi wewenang kepada setiap pemilih dengan ID unik dan memberikan akses pemilih yang memungkinkan mereka memverifikasi bahwa surat suara mereka 1) telah dihitung dan 2) belum diubah.
- Pemilih tidak dapat dihukum karena memilih kandidat yang “salah” karena penolakan terhadap paksaan, yang, khususnya, dicapai melalui enkripsi yang tidak terduga dan probabilistik.
- Privasi surat suara dijamin oleh fakta bahwa suara terenkripsi tidak didekripsi, dan hanya hasil yang dibuat menggunakan enkripsi homomorfik yang didekripsi.
- Penipuan tidak berfungsi jika kami memaksa pemilih untuk menerbitkan bukti kriptografi tentang validitas surat suara mereka menggunakan NINR.
Konsep dan teknologi yang dijelaskan di sini mungkin tampak dalam dan kompleks, tetapi dalam kenyataannya ini hanyalah puncak gunung es. Anda tidak dapat membuat sistem pemilihan elektronik yang berfungsi dengan aman hanya dengan mengikuti uraiannya. Misalnya, saya menghilangkan detail seperti cara pemilih memeriksa surat suara mereka dalam praktik, alasan untuk menggunakan server NINR, dan sebagainya. Intinya adalah bahwa setiap protokol pemungutan suara elektronik yang aman adalah hal yang sangat rumit dan penuh nuansa, dan implementasi aktual menambah kompleksitas tambahan karena faktor manusia dan organisasi.
Untuk mempelajari lebih lanjut tentang kriptografi yang terkait dengan topik pemungutan suara elektronik, Anda dapat mempelajari materi berkualitas ini: