Masalah Pembagian Rahasia

Anda memiliki kunci utama yang harus tetap tersedia dan dapat diakses dalam keadaan darurat, tetapi tidak boleh disalahgunakan oleh satu orang pun. Bagaimana cara menyimpannya? Memberikan kunci lengkap kepada beberapa orang berarti siapa pun dari mereka dapat menyalahgunakannya. Menyimpan satu salinan menciptakan satu titik kegagalan.

Memisahkan kunci 128-bit menjadi dua bagian 64-bit dan memberikan setiap bagian kepada dua orang tampak cerdas, tetapi tidak aman: setiap bagian mengurangi biaya brute force dari 2^128 menjadi 2^64. Musuh yang menyusupi satu orang memperoleh keunggulan awal sebesar 64 bit.

Skema pembagian rahasia yang tepat harus memiliki sifat berikut: (1) Ambang batas: setiap k-dari-n bagian dapat merekonstruksi rahasia. (2) Keamanan: setiap k-1 bagian tidak mengungkapkan informasi apa pun tentang rahasia. (3) Sempurna: tidak diperlukan asumsi komputasi.

Dompet Bitcoin, kunci utama HSM, kunci privat otoritas sertifikat, kode peluncuran nuklir, dan dompet dingin bursa mata uang kripto semuanya memerlukan akses berbasis ambang batas. Hilangnya satu-satunya kunci = bencana besar. Kunci yang disusupi oleh satu orang dalam = juga bencana besar.

Untuk membagi rahasia S antara dua pihak: buat R acak. Berikan share1=R kepada pihak 1, dan share2=S XOR R kepada pihak 2. Untuk merekonstruksi: share1 XOR share2 = R XOR (S XOR R) = S. Setiap bagian saja bersifat acak sempurna — tidak mengungkapkan apa pun tentang S.

Pembagian XOR sempurna untuk 2-dari-2, tetapi tidak dapat digeneralisasi ke skema ambang batas k-dari-n. Anda tidak dapat membuat skema 3-dari-5 yang memungkinkan setiap 3 bagian merekonstruksi rahasia, tetapi setiap 2 bagian tidak mengungkapkan apa pun. Interpolasi polinomial menyelesaikan masalah ini.

Kerahasiaan sempurna berarti bagian-bagian tersebut mengandung informasi timbal balik nol tentang rahasia jika jumlahnya kurang dari k bagian. Ini lebih kuat daripada keamanan komputasional — bahkan penyerang dengan kemampuan komputasi tak terbatas tidak memperoleh apa pun dari k-1 bagian.

AWS CloudHSM menggunakan autentikasi kuorum M-of-N. PGP membagi kunci utama untuk escrow. Penyedia kustodi mata uang kripto (Fireblocks, BitGo) menggunakan MPC atau pembagian Shamir untuk kunci dompet panas. Kunci luring Otoritas Sertifikat menggunakan seremoni 5-dari-7.

Seremoni kunci adalah proses formal dan diaudit untuk membuat serta membagi kunci utama. Contoh: 7 pemegang kunci hadir di ruangan aman, masing-masing menerima token perangkat keras dengan satu bagian. Proses direkam dalam video, dua auditor hadir, dan setiap langkah didokumentasikan.

Pembagian rahasia merekonstruksi rahasia lengkap (risiko: satu titik kegagalan pada waktu rekonstruksi). Multitanda tangan membagi proses penandatanganan: setiap pihak menandatangani secara independen dan tanda tangan digabungkan. Tanda tangan ambang batas (TSS) adalah pembagian rahasia yang diterapkan pada operasi penandatanganan itu sendiri.

Secure Multi-Party Computation (MPC) menghilangkan langkah rekonstruksi sepenuhnya — para pihak menghitung bersama menggunakan bagian mereka tanpa mengungkapkan rahasia. ECDSA ambang batas dan BLS ambang batas telah diterapkan dalam sistem kustodi produksi.

Dalam skema pembagian rahasia XOR 2-dari-2, berapa banyak bagian yang diperlukan penyerang untuk mengetahui rahasianya?

Pemisahan kunci secara naif tidak aman. Pembagian rahasia yang tepat memerlukan akses berbasis ambang batas dengan kerahasiaan sempurna. XOR menangani 2-dari-2; interpolasi polinomial menangani k-dari-n. Berikutnya: matematika Pembagian Rahasia Shamir.