Apakah komitmen bit menghasilkan transfer yang tidak disadari dalam model keamanan informasi-teoretis?

16

Misalkan Anda memiliki dua peserta kuat yang sewenang-wenang yang tidak saling mempercayai. Mereka memiliki akses ke komitmen bit (mis., Amplop tertutup berisi data yang dapat diberikan satu pemain kepada yang lain tetapi tidak dapat dibuka sampai pemain pertama memberikan kunci kedua). Bisakah Anda menggunakan ini untuk membangun protokol transfer yang tidak disadari. Apakah ini benar bahkan jika para pemain setuju untuk membuka semua amplop pada akhirnya untuk mendeteksi kecurangan (misalnya, setelah kartu poker dimainkan, semua orang setuju untuk mengungkapkan kartu mereka)?

Saya berasumsi bahwa Anda tidak bisa mendapatkan transfer tanpa sadar dari komitmen bit, karena transfer tanpa sadar secara universal bersifat kriptografis, dan saya tidak dapat menemukan referensi yang mengatakan komitmen bit, tetapi apakah ada bukti di suatu tempat bahwa Anda tidak dapat melakukannya?

Akhirnya, adakah yang melihat masalah jika para pemainnya kuantum?

reference-request cr.crypto-security Peter Shor
sumber
2
Dalam komentar pada pertanyaan tentang mathoverflow, dinyatakan bahwa quantum Oblivious Transfer setara dengan Komitmen Bit kuantum (dengan referensi): mathoverflow.net/questions/32801/… .
M. Alaggan
4
Kedua makalah ini menunjukkan bahwa komitmen bit kuantum aman tanpa syarat adalah tidak mungkin. Jika Anda bisa melakukan transfer tanpa sadar kuantum, itu akan menyiratkan Anda bisa melakukan komitmen bit kuantum, sehingga mereka juga menunjukkan transfer tanpa sadar quantum secure yang aman juga tidak mungkin. Yang saya ingin tahu adalah jika Anda diberikan (sebagai kotak hitam) komitmen bit yang berfungsi untuk protokol kuantum, bisakah Anda juga melakukan transfer secara tidak sadar untuk protokol kuantum.
Peter Shor
3
Mungkin sedikit lebih banyak latar belakang diperlukan. Saya pikir saya memiliki skema yang agak sederhana yang, dengan komitmen bit, menggunakannya untuk mencapai transfer yang tidak disadari dalam protokol kuantum. Saya ingin (1) tahu apa bukti klasik bahwa transfer tanpa sadar benar-benar lebih kuat, untuk memastikan bahwa mereka tidak berlaku untuk kasus kuantum, dan (2) untuk mengetahui apakah ada orang yang telah mengamati ini sebelumnya. Literatur untuk transfer yang tidak sadar kuantum dan komitmen bit sulit untuk dicari karena beberapa bukti keamanan berantakan ketika Mayers dan Lo dan Chau membuktikan teorema no-go mereka.
Peter Shor 8-10
4
Mencari literatur sedikit lagi, ada sedikit komitmen ==> bukti transfer tidak sadar dalam rezim kuantum dalam makalah tahun 1991 dari Bennett, Brassard, Crépeau dan Skubiszewska ( springerlink.com/content/k6nye3kay7cm7yyx ), jadi ini diketahui.
Peter Shor 8-10
2
@ M. Alaggan: Izinkan saya meminta maaf karena mengabaikan komentar Anda di atas dengan tiba-tiba. Penulis komentar MathOverflow yang Anda maksud mungkin tahu bahwa mereka setara, dan pada kenyataannya komentar itu menempatkan saya pada jalur bibliografi yang mengarah pada bukti referensi yang saya temukan dalam komentar saya di atas. Terima kasih banyak.
Peter Shor

Jawaban:

14

Tidak, komitmen memiliki kompleksitas yang lebih rendah daripada PL. Saya pikir cara mudah untuk melihat ini adalah pendekatan yang diambil dalam Kompleksitas Masalah Komputasi Multipartai: Kasus Evaluasi Fungsi Aman Symmetric 2-Pihak oleh Maji, Prabhakaran, Rosulek dalam TCC 2009 (disclaimer: self promotion!). Dalam makalah itu kami memiliki hasil yang mengkarakterisasi apa yang dapat Anda lakukan mengingat akses ke komitmen ideal dalam model UC dengan keamanan statistik.

πππ

Cara lain untuk melihatnya adalah melalui Impagliazzo-Rudich . Jika Anda memiliki pihak yang tidak terikat secara komputasi dan oracle acak, Anda dapat melakukan komitmen (karena semua yang Anda butuhkan adalah fungsi satu arah) tetapi Anda tidak dapat melakukan hal-hal seperti perjanjian utama, dan dengan demikian bukan PL.

mikero
sumber
1
@ Mikero: itu bukti yang sangat bagus, dan sederhana.
Peter Shor 8-10
Untuk PL bit klasik (yaitu, dunia ideal klasik) argumen akan melewati untuk protokol kuantum / musuh. Jika PL memanipulasi qbits maka mungkin ada komplikasi. Langkah yang "tidak sepele seperti kedengarannya tetapi tidak sulit" melibatkan mengatakan bahwa WLOG simulator selalu menggunakan input yang disediakan oleh lingkungan. Ini adalah properti dari PL yang harus ditunjukkan (jika simulator tidak mengirimkan apa yang diberikan, output akan salah dengan probabilitas yang nyata, sehingga simulasi tidak sehat), dan harus diargumentasikan ulang jika lingkungan dapat memberikan Saya menerima qbits dari PL.
mikero
1
@Mikero: Saya tidak mengerti komentar Anda sebelumnya. Apa artinya bagi PL untuk tidak memanipulasi qubit? Apakah maksud Anda bahwa kedua pihak hanya berkomunikasi dengan bit klasik, tetapi mungkin memiliki prosesor kuantum? Ini akan mengikuti dari fakta bahwa tidak ada protokol aman informasi-teori untuk OT ada, bahkan dengan sedikit komitmen.
Peter Shor 8-10
Saya sedang mempertimbangkan apakah "protokol PL kuantum" berarti PL klasik (fungsionalitas PL hanya tahu tentang bit) dengan protokol kuantum yang mungkin, atau PL di mana lingkungan tahu tentang qubit dan OT mengirim / menerima qubit. Dalam kasus sebelumnya, saya pikir argumen yang sama tidak dimodifikasi. Mungkin yang Anda maksud adalah kasus terakhir. Kemudian jika benar-benar ada contoh tandingan di dunia kuantum itu berarti bahwa PL qubit tidak memiliki properti yang WLOG simulasi memetakan musuh-musuh dunia nyata yang jujur-tetapi-ingin tahu terhadap musuh-musuh ideal yang jujur-tetapi-ingin tahu. Menarik!
mikero
1
Jika saya memahami pertanyaan Anda dengan benar, Bennett dkk. kertas dan bukti saya adalah untuk PL klasik, dengan pesan-pesan kuantum antara para peserta untuk mengimplementasikan PL.
Peter Shor
7

Dalam kasus kuantum, protokol pertama untuk membangun transfer (klasik) tanpa sadar berdasarkan komitmen bit (klasik) menggunakan protokol kuantum diusulkan pada tahun 1991 oleh Bennett, Brassard, Crépeau, dan Skubiszewska (http://www.springerlink.com/content / k6nye3kay7cm7yyx /), tetapi bukti keamanan lengkap hanya diberikan baru-baru ini oleh Damgaard, Fehr, Lunemann, Salvail dan Schaffner di http://arxiv.org/abs/0902.3918

Untuk ekstensi ke komputasi multi-partai dan bukti dalam kerangka kerja kompabilitas universal, lihat karya Unruh: http://arxiv.org/abs/0910.2912

Christian Schaffner
sumber