Pembagian Rahasia Visual & Skema Aditif

Pembagian rahasia visual (Naor & Shamir, 1994) membagi sebuah citra menjadi n lembar transparan sehingga penumpukan k lembar mengungkapkan citra rahasia, sedangkan jumlah yang lebih sedikit tidak mengungkapkan apa pun—bahkan kepada penyerang dengan kemampuan komputasi tak terbatas.

Setiap piksel rahasia diperluas menjadi blok 2x2. Untuk piksel hitam: kedua bagian mendapatkan pola yang saling melengkapi (saat ditumpuk, semuanya menjadi hitam). Untuk piksel putih: kedua bagian mendapatkan pola yang sama (saat ditumpuk, 50% hitam = abu-abu). Mata menangkap perbedaannya.

Untuk untaian bit: bagikan rahasia S dengan menghasilkan R_1, R_2, ..., R_{n-1} secara acak. Tetapkan R_n = S XOR R_1 XOR ... XOR R_{n-1}. Jika semua n bagian di-XOR bersama, hasilnya = S. Setiap subset dari n-1 bagian terdistribusi secara seragam—tidak mengungkapkan apa pun tentang S.

Pembagian XOR/aditif bersifat n-of-n (semua bagian diperlukan). SSS Shamir bersifat k-of-n (sembarang k bagian). Pembagian aditif lebih sederhana dan cepat; Shamir menangani ambang batas arbitrer. Protokol MPC sering menggunakan pembagian aditif untuk operasi aritmetika.

Untuk rahasia berupa bilangan bulat: bagikan S sebagai S = s_1 + s_2 + ... + s_n (mod p). Setiap s_i adalah elemen acak dari Z_p. Untuk menjumlahkan dua nilai yang dibagikan A+B: setiap pihak menjumlahkan bagiannya secara lokal: (a_i + b_i) mod p. Tidak diperlukan komunikasi untuk penjumlahan.

Perkalian nilai yang dibagikan secara rahasia memerlukan interaksi. Metode tripel Beaver klasik: hitung sebelumnya tripel acak yang dibagikan (a, b, c=ab). Untuk mengalikan x*y: ungkapkan (x-a) dan (y-b) kepada semua pihak (keduanya tidak mengungkapkan apa pun tentang x,y), lalu hitung x*y menggunakan tripel tersebut.

Skema Pembagian Rahasia Linear (LSSS) merealisasikan struktur akses monoton apa pun. Shamir adalah LSSS. LSSS merupakan blok pembangun untuk enkripsi berbasis atribut (ABE) dan sistem kendali akses multiotoritas.

Pembagian Shamir terpaket memuat banyak rahasia dalam satu polinom: menyandikan k rahasia sebagai koefisien polinom berderajat (n-k). Teknik ini memungkinkan biaya komunikasi teramortisasi dalam protokol MPC ketika banyak nilai perlu dibagikan secara bersamaan.

Skema pembagian dasar tidak menawarkan perlindungan terhadap pemegang bagian yang berniat jahat dan mengirimkan bagian tidak valid. Pembagian Rahasia yang Dapat Diverifikasi (VSS) menambahkan komitmen; Pembagian Rahasia Tangguh menambahkan koreksi kesalahan sehingga rekonstruksi tetap berhasil meskipun terdapat t bagian yang buruk.

Kriptografi visual: autentikasi dokumen tercetak, surat suara pemungutan suara yang aman. Pembagian aditif: MPC SPDZ, agregasi aman dalam pembelajaran federatif (Google). Skema ambang batas: pencadangan benih dompet perangkat keras, pengelolaan kunci perusahaan.

Skema bertingkat (k,n) lebih lemah: kurang dari k-d bagian mengungkapkan sebagian informasi (d tingkat kerahasiaan). Skema ini digunakan ketika kerahasiaan sempurna atas bagian parsial tidak diperlukan, tetapi efisiensi penyimpanan sangat penting. Skema ini memungkinkan bagian yang lebih pendek daripada Shamir.

Dalam pembagian aditif n-of-n berbasis XOR, berapa banyak bagian yang diperlukan untuk merekonstruksi rahasia?

Kriptografi visual membagi citra menjadi lembar transparan; pembagian aditif menggunakan XOR untuk skema n-of-n; Shamir menangani k-of-n. MPC menggunakan pembagian aditif dengan tripel Beaver untuk perkalian. Berikutnya: tanda tangan ambang batas dan penggunaan di dunia nyata.