Lotre yang dapat Anda yakini adil

27

(Maaf jika ini sudah diketahui.) Saya ingin memberikan beberapa item kepada salah satu agen , sehingga agen akan mendapatkan item dengan probabilitas . Apakah ada alat kriptografi (atau lainnya) sehingga setiap agen (dan bahkan setiap pengamat) akan dapat diyakinkan bahwa gambar acak itu memang adil?kjpi

cr.crypto-security Gil Kalai
sumber
1
Apakah agen diizinkan untuk mengetahui .. ? hal0halk
Mike Samuel
Pernahkah kamu melihat ini? ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4232861
dspyz

Jawaban:

19

Jika saya memahami masalahnya dengan benar, tampaknya akan sama dengan publik membalik koin sided. Tampaknya ada banyak cara untuk melakukan ini jika Anda menganggap sedikit komitmen. Salah satu contoh akan memiliki masing-masing pihak menghasilkan bilangan bulat acak antara 0 dan , menggunakan komitmen bit untuk secara publik berkomitmen pada string bit itu. Kemudian setelah masing-masing agen melakukan, mereka semua secara terbuka mengungkapkan integer rahasia mereka. Agen pemenang kemudian diindeks oleh jumlah dari bilangan bulat modulo . Jika satu agen jujur, maka flip harus acak.k - 1 kkk-1k

Tentu saja satu masalah dengan ini adalah bahwa itu memerlukan sedikit komitmen. Skema teori informasi untuk komitmen bit tidak mungkin dilakukan untuk komputasi klasik dan kuantum (meskipun baru-baru ini Adrian Kent mengusulkan skema yang mengeksploitasi relativitas). Namun, komitmen bit aman dapat dicapai dengan asumsi komputasi.

Joe Fitzsimons
sumber
2
Masalah saya dengan pendekatan ini adalah bahwa jika Anda ingin meyakinkan banyak pengamat dari luar dari keadilan, maka masing-masing dari mereka harus melakukan sedikit dan Anda harus yakin bahwa masing-masing dari mereka akan mengungkapkan bukti komitmen mereka. Anda tidak bisa begitu saja mengabaikan sedikit pengamat yang tidak mengungkapkan bukti mereka karena kemudian pengamat terakhir yang mengungkapkan bisa memanipulasi hasil lotere dengan memutuskan apakah akan mengungkapkan buktinya atau tidak.
Zsbán Ambrus
1
@ user8067: Saya tidak percaya itu mungkin tanpa interaksi atau percaya bahwa setidaknya satu pihak jujur. Alasan saya mengatakan ini adalah bahwa jika keacakan awal sebenarnya telah ditentukan melalui konspirasi semua orang yang berpartisipasi pada saat itu, maka seluruh proses bersifat deterministik dan bukan acak. Namun masalahnya memerlukan proses secara acak, jadi ini sepertinya yang terbaik yang dapat Anda lakukan.
Joe Fitzsimons
2
Saya tidak yakin itu mungkin.
Joe Fitzsimons
2
@ RickyDemer: Tidak ada cukup informasi dalam pertanyaan untuk memberi tahu model musuh apa yang berlaku di sini. Jika Gil memberi tahu kami dengan tepat untuk apa, maka akan lebih mudah untuk membuktikan apakah suatu skema tertentu memenuhi persyaratannya atau tidak. Tetapi yang mengatakan, saya tidak ragu Gil lebih dari mampu memeriksa apakah jawaban kami memenuhi kebutuhannya atau tidak.
Joe Fitzsimons
2
@ RickyDemer: Sama sekali tidak jelas bagi saya apa model yang jelas untuk kasus ini. Ini sangat tergantung pengaturan, dan tidak jelas apa asumsi default seharusnya. Agak banyak untuk merendahkan dan mulai bertindak seperti jawaban saya dan jawaban Lev salah. Mereka tidak secara eksplisit memasukkan peringatan yang ditunjukkan dalam jawaban Adam. Perhatikan bahwa saya -tidak- mengedit jawaban saya, karena tanpa lebih banyak informasi dari Gil, saya merasa tidak masuk akal untuk menebak tentang model musuh, dan jadi saya membiarkannya sesering mungkin (tidak menentukan apakah atau tidak komitmen bit perlu tidak dapat diubah).
Joe Fitzsimons
15

Seperti yang telah diindikasikan oleh pengguna lain, ini adalah masalah yang dipelajari dalam kriptografi. Ini disebut "coin-flipping" dan merupakan kasus khusus perhitungan multi-pihak.

Protokol apa yang dikerjakan sebenarnya tergantung pada konteksnya.

  • Dalam pengaturan "mandiri", protokol akan dijalankan secara terpisah, tanpa pemain terlibat dalam protokol lain (atau memang, interaksi dengan dunia luar) pada saat yang sama. Ada perlakuan luar biasa menyeluruh tentang hal ini dalam buku teks Oded Goldreich "Foundations of Cryptography" (Volume 2, saya pikir).

Hanya untuk memberikan gambaran tentang betapa halusnya itu, protokol "semua orang berkomitmen untuk nilai acak" yang disarankan oleh responden lain tidak aman jika skema komitmen yang Anda gunakan mudah ditempa. Skema komitmen nonmalleable memang memberi Anda protokol yang aman, tetapi mereka agak rumit untuk dirancang.

  • Dalam pengaturan di mana peserta terlibat dalam protokol konkuren lainnya, Anda menginginkan protokol yang dapat dikompilasi . Ada berbagai gagasan tentang kompabilitas, tetapi yang terkuat, yang disebut kompabilitas universal , memerlukan beberapa asumsi pengaturan tambahan (misalnya, PKI atau string acak umum yang terlihat oleh semua pihak, tetapi tidak dapat dikontrol oleh siapa pun). Sayangnya, saya tidak tahu cara mengakses topik ini yang dapat diakses. Tetapi melihat makalah baru-baru ini tentang baik kompabilitas universal atau komitmen nonmalleable akan menjadi tempat yang baik untuk memulai.
Adam Smith
sumber
1
"String acak yang umum terlihat oleh semua pihak tetapi tidak dapat dikontrol oleh semua pihak" adalah yang ingin kami hasilkan.
Zsbán Ambrus
1
dan setelah entah bagaimana menyelesaikan masalah itu sekali, seseorang dapat secara komposisional atasi lagi (berkali-kali sewenang-wenang).
Saya pikir komitmen UC dikenal untuk pengaturan Kunci Publik Terdaftar (yang merupakan asumsi yang lebih kuat dari PKI) dan pengaturan multi-string (yang merupakan asumsi yang lebih lemah daripada string acak umum).
2
Selamat datang di situs, Adam!
Gil Kalai
11

Catatan: silakan baca komentar di bawah ini. Protokol ini tampaknya memiliki masalah.

halj

{0,1}bb

Agen apa pun dapat memastikan nomor acak yang dipilih datang secara acak secara acak dengan memilih vektornya sendiri secara acak. Agar setiap pengamat diyakinkan, mereka harus percaya bahwa setidaknya satu agen mengikuti protokol, tetapi jika tidak ada, saya kira tidak ada yang benar-benar menginginkan lotere yang adil untuk memulai.

Lev Reyzin
sumber
Maaf Lev, saya baru saja memperhatikan jawaban Anda. Ketika saya mulai menulis jawaban, tidak ada apa-apa di sini, tetapi kami berdua tampaknya telah menemukan jawaban yang sangat mirip.
Joe Fitzsimons
Jangan khawatir! Sepertinya kita berada di jalur yang benar, lalu.
Lev Reyzin
Ya, sebenarnya saya pikir ada banyak makalah tentang ini dalam konteks membalik koin, tetapi saya tidak benar-benar tahu bahwa literatur cukup baik untuk memberikan jawaban yang tepat berdasarkan itu.
Joe Fitzsimons
7
Referensi paling awal yang saya tahu adalah: M. Blum. Koin Terbalik Dengan Telepon. CRYPTO 1981: 11-15. Dapat diunduh di dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/…
Ryan Williams
4
Ada serangan standar, jika Anda menggunakan skema komitmen bit standar (misalnya, hashing). Mari kita perhatikan kasus dengan dua pihak, Alice dan Bob, di mana Alice pergi dulu. Setelah Alice menyiarkan komitmennya, Bob dapat menyalinnya. Setelah Alice membuka komitmennya, Bob dapat membuka komitmennya yang sama sekarang. Sekarang vektor acak mereka adalah sama, sehingga mereka xor ke nol - Bob mampu memaksa nilai akhir menjadi nol, sebuah kontradiksi dari persyaratan untuk keadilan.
DW
-3

Pengamat pasif tidak dapat memverifikasi bahwa gambar tidak dipentaskan. Input ke dalam proses pseudorandom dapat dipilih untuk memberikan hasil yang diinginkan.

Namun jika pengamat dapat memberikan nomor acak yang dia tahu adalah acak DAN memastikan bahwa agen lain tidak akan mengubah input mereka setelah itu (karena mereka dapat mengkompensasi efeknya dengan input mereka), maka dia dapat yakin bahwa hasilnya memang acak .

Ini membutuhkan skema komitmen yang kita tidak tahu apa pun yang secara matematis terbukti aman tetapi dalam praktiknya dapat direalisasikan menggunakan hash aman (seperti SHA3).

Pertimbangkan contoh ini:

masukkan deskripsi gambar di sini

Saya sudah membuat contoh implementasi. Anda dapat melihatnya langsung di sini: https://mrogalski.eu/cl/ atau periksa sumber di GitHub .

Marek Rogalski
sumber
1
Ini sudah dicatat dalam jawaban Joe.
Kaveh
1
Ilustrasi grafisnya sangat bagus!
Gil Kalai
3
Grafiknya sangat cantik tetapi jawaban Anda tidak mengandung apa pun yang tidak ada dalam jawaban yang ada.
David Richerby