Tentang Teknik Bukti dari Tanda Tangan Celah Boneh-Lynn-Shacham

8

Di kertas "tanda tangan pendek dari pasangan Weil" oleh Boneh, Lynn dan Shacham, saya akan melalui bukti keamanan sama seperti tanda tangan lainnya.

Namun teknik yang digunakan dalam tulisan ini cukup unik. Alih-alih menggunakan penantang normal dan interaksi musuh, mereka membagi bukti menjadi 6 game di mana setiap game diperpanjang secara berurutan dari game sebelumnya.

Saya tidak yakin mengapa mereka menggunakan pendekatan ini sebagai ganti dari game normal. Apakah bukti keamanan semacam ini membantu mengurangi kemungkinan lebih mudah atau mereka baru saja memberikannya dari sudut pandang "mudah dibaca dan dipahami"?

Terima kasih!

reference-request cr.crypto-security Maverickgugu
sumber

Jawaban:

11

Teknik "melompat" dari satu game ke game lainnya, dan membuktikan keamanan melalui "urutan game" bukanlah hal baru. Secara khusus, ada beberapa makalah yang membahas teknik-teknik ini, dan mencontohkannya melalui berbagai bukti keamanan. Contoh terkenal adalah:

Mengenai pertanyaan Anda, saya menggunakan kutipan dari makalah terakhir yang dikutip di atas:

Dalam bukti hopping game, kami mengamati bahwa penyerang yang berlari di lingkungan serangan tertentu memiliki probabilitas keberhasilan yang tidak diketahui. Kami kemudian perlahan mengubah lingkungan serangan sampai probabilitas keberhasilan penyerang dapat dihitung. Kami juga mengikat peningkatan probabilitas keberhasilan penyerang yang disebabkan oleh perubahan pada lingkungan serangan. Dengan demikian, kita dapat menarik kesimpulan untuk probabilitas keberhasilan penyerang di lingkungan aslinya.

Dengan demikian, alasan untuk menggunakan beberapa game adalah bahwa di setiap game, kami menyederhanakan perhitungan beberapa probabilitas yang tidak diketahui, tanpa mengubahnya secara signifikan. Ini berlanjut sampai kita mencapai permainan di mana perhitungan probabilitasnya cukup mudah.

MS Dousti
sumber
Terima kasih atas referensi !! saya akan berkomentar setelah mempelajari melalui makalah ini untuk gambar yang lebih baik. Tetapi untuk membuatnya lebih abstrak, dapatkah bukti berbasis game berurutan tersebut dikonversi menjadi bukti permainan tunggal dan menghitung probabilitas secara keseluruhan?
Maverickgugu
@Maverickgugu: Sama-sama! Mengatur ulang pertanyaan Anda: Terkadang dimungkinkan untuk mengubah beberapa game menjadi satu, tetapi buktinya semakin rumit. (Jika saya ingat dengan benar, referensi pertama atau kedua yang dikutip dalam jawaban saya menyebutkan satu permainan seperti itu.) Tetapi secara umum, bukti seperti itu bisa menjadi sangat kompleks, dan bahkan tidak mungkin dilakukan. Saya pikir Anda dapat mengatasi ini dengan mencoba menggabungkan 6 game dalam bukti Boneh-Lynn-Shacham, dan melihat sendiri di mana masalah muncul.
MS Dousti
@Sadiq Dousti: Dalam makalah Shoup ia menyebutkan "Selain itu, bahkan ketika teknik ini berlaku, itu hanya alat untuk mengatur bukti - ide sebenarnya untuk konstruksi kriptografi dan analisis keamanan harus datang dari tempat lain." Dengan argumen itu, saya mencoba untuk menyingkat 6 game menjadi 1 dalam bukti Boneh-Lynn-Shacham dan saya tidak dapat menemukan kesulitan dalam penggabungan. Saya merasa itu hanya dengan jelas menggabungkan semua kondisi tambahan dan peristiwa kegagalan yang memberikan kemungkinan akhir. Bisakah Anda membantu saya dengan informasi halus yang saya lewatkan?
Maverickgugu
@Maverickgugu: Kirimkan saya bukti gabungan melalui email. Anda dapat menemukan informasi kontak saya di sini .
MS Dousti
2

Gagasan untuk menggunakan urutan permainan sebagai bagian dari bukti keamanan reduksionis mendahului referensi yang diberikan (itu tersirat dalam pekerjaan sejak awal tahun 80-an jika tidak sebelumnya, dan eksplisit setidaknya pada akhir tahun 90-an).

pengguna686
sumber
Jika saya dapat menyarankan peningkatan, Anda dapat menambahkan beberapa contoh sebagai karya di mana gagasan "urutan permainan" tersirat (jawaban saya sudah mencakup beberapa contoh eksplisit).
MS Dousti