simulabilitas garis lurus

11

Apakah ada yang tahu referensi bagus untuk arti simulabilitas garis lurus? Saat ini saya jauh ke dalam kerangka kerja Universal Composability (UC) dari Canetti, tetapi saya tidak dapat menemukan referensi yang baik untuk arti simulabilitas garis lurus. Bantuan apa pun dihargai.

cr.crypto-security Yasser Sobhdel
sumber

Jawaban:

10

Di sini, "garis lurus" kontras dengan "memutar ulang". Simulator adalah "garis lurus" jika tidak "mundur" dari pihak yang melakukan simulasi.

Misalnya, dalam protokol tanpa pengetahuan, simulator biasanya memutar ulang "pemverifikasi". Dalam arti "garis lurus", pemunduran ini tidak terjadi.

Saya pertama kali melihat istilah "simulator garis lurus" dalam makalah Rafael Pass ( On Deniabililty dalam String Referensi Umum dan Model Oracle Acak. (CRYPTO'03) ) dan M.Sc. tesis ( Varian Alternatif Bukti Tanpa Pengetahuan ).

Sunting: Saya menemukan makalah sebelumnya: Concurrent Zero-Knowledge: Mengurangi Kebutuhan untuk Menghambat Waktu oleh Cynthia Dwork dan Amit Sahai, yang berasal dari tahun 1998. Untuk petunjuk lebih lanjut, lihat komentar Alon Rosen di bawah ini.

MS Dousti
sumber
Saya tidak tahu istilah "simulator garis lurus" tetapi bagi saya itu "garis lurus" kontras dengan "percabangan", analog dengan logika temporal linear-waktu vs percabangan-waktu dan melacak kesetaraan vs ekuivalensi bisimulasi (percabangan). Apakah ada sesuatu untuk ini?
Dave Clarke
Kurasa tidak. Saya menemukan referensi lain yang sesuai dengan definisi saya.
MS Dousti
Penjelasan Sadeq sama dengan konteks apa pun yang pernah saya dengar istilah yang digunakan. Berikut adalah beberapa catatan kuliah NYU dari kelas di Adv Crypto dari tahun lalu yang membahas topik tersebut; khususnya, lihat Klaim 8.
Daniel Apon
Deterministik terdengar seperti sinonim yang mungkin.
Dave Clarke
5
Sebelumnya penggunaan konsep simulatabilitas garis lurus (meskipun mungkin tidak di bawah terminologi ini) dapat ditemukan di: (1) Ran Canetti, Oded Goldreich, Goldwasser Shafi, Silvio Micali: Reset pengetahuan nol (abstrak diperpanjang). STOC 2000: 235-244, dan (2) Ran Canetti, Marc Fischlin: Komitmen yang Dapat Dikomposisikan Secara Universal. CRYPTO 2001: 19-40. Gagasan muncul dalam definisi UC, karena tidak mungkin untuk memundurkan "lingkungan". Itu muncul sebelumnya dalam konteks yang berbeda dalam pengetahuan nol bersamaan, di mana simulator rewinding dapat mengalami masalah.
Alon Rosen
3

Tidak ada definisi formal tentang apa artinya menjadi simulator garis lurus. Ini hanya ide intuitif yang dapat digunakan untuk menggambarkan berbagai hal secara informal. Saya sangat skeptis tentang apakah seseorang dapat mendefinisikan apa artinya tidak memundurkan mesin. Memang, memutar mesin itu sendiri adalah istilah informal! Apa yang sebenarnya kita maksud dengan memutar ulang sebuah mesin adalah bahwa dengan kita dapat menjelajahi banyak kemungkinan jalur eksekusi mesin dari kondisi tertentu. Argumen formal kemudian didasarkan pada sejumlah eksekusi yang perlu kita eksplorasi sebelum kita dapat memperoleh pintu jebakan atau informasi lain yang perlu kita lanjutkan bukti kita.


sumber