Apakah bukti keamanan berarti skema tidak akan pernah bisa dibobol?

Tidak. Bukti menunjukkan bahwa membobol skema menyiratkan pemecahan masalah yang diasumsikan sulit dalam model yang ditentukan. Jika asumsi gagal, model tidak realistis, atau implementasi menyimpang dari skema yang dianalisis, serangan tetap mungkin terjadi. Bukti mengurangi, tetapi tidak menghilangkan, risiko.

Mengapa model oracle acak dianggap kontroversial?

Ini memodelkan fungsi hash sebagai fungsi yang sangat acak, yang tidak ada fungsi konkret yang benar-benar demikian. Bukti dalam model ini adalah bukti kuat dan memungkinkan skema yang efisien, tetapi ada skema (buatan) yang aman dalam model tersebut namun tidak aman setelah oracle diganti dengan hash nyata apa pun, sehingga bukti semacam itu bersifat heuristik.

Keamanan dan Reduksi yang Dapat Dibuktikan

Keamanan yang dapat dibuktikan menunjukkan bahwa membobol skema kriptografi setidaknya sama sulitnya dengan memecahkan masalah yang dianggap tidak dapat dipecahkan, dengan memberikan reduksi eksplisit dari masalah yang dianggap sulit ke setiap serangan pada skema tersebut.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Reduksi keamanan adalah bukti yang mengubah setiap musuh yang efisien yang membobol skema kriptografi menjadi algoritma yang efisien yang memecahkan masalah yang dianggap sulit, sehingga menunjukkan bahwa skema tersebut aman kecuali jika masalah tersebut mudah.

Scope

Topik ini mencakup metodologi berbasis reduksi dari bukti kriptografi: struktur reduksi keamanan, ketatnya dan keamanan konkret, gaya bukti berbasis permainan dan berbasis simulasi, model oracle acak dan standar, serta batasan dan kritik terhadap pendekatan tersebut. Ini membahas bagaimana jaminan keamanan dinyatakan dan diperdebatkan. Ini tidak termasuk asumsi kesulitan spesifik dan definisi serta model musuh, yang dibahas dalam topik terkait.

Core questions

Bagaimana reduksi menerjemahkan serangan pada suatu skema menjadi solusi untuk masalah yang sulit?
Apa perbedaan antara bukti berbasis permainan dan berbasis simulasi?
Apa arti 'ketatnya' reduksi untuk parameter keamanan dunia nyata?
Apa itu model oracle acak dan standar, dan mengapa yang pertama kontroversial?
Apa batasan dan jebakan umum dari argumen keamanan yang dapat dibuktikan?

Key concepts

reduksi keamanan
bukti berbasis permainan
bukti berbasis simulasi
reduksi ketat vs longgar
keamanan konkret
model oracle acak
model standar
keuntungan yang dapat diabaikan
asumsi kesulitan

Key theories

Metodologi bukti reduksionis: Untuk membuktikan skema aman, diasumsikan ada musuh yang membobolnya dan membangun, menggunakan musuh tersebut sebagai subrutin, sebuah algoritma yang memecahkan masalah sulit yang mendasarinya — sehingga serangan yang berhasil akan bertentangan dengan asumsi kesulitan.
Model oracle acak: Banyak skema efisien terbukti aman dengan mengidealkan fungsi hash sebagai oracle yang benar-benar acak; model ini memungkinkan bukti untuk konstruksi praktis tetapi bersifat heuristik, karena tidak ada fungsi nyata yang merupakan oracle acak.

Mechanisms

Dalam reduksi, pembukti mengasumsikan musuh hipotetis yang membobol skema dengan keuntungan yang tidak dapat diabaikan dan membangun pembungkus yang menyematkan instans masalah sulit ke dalam pandangan musuh, menjalankan musuh, dan menggunakan keluarannya untuk memecahkan masalah. Bukti berbasis permainan berjalan melalui urutan permainan yang tidak dapat dibedakan dari skema nyata ke skema di mana musuh jelas tidak dapat menang. Ketatnya reduksi — seberapa banyak keuntungan dan waktu berjalan yang hilang — menentukan ukuran kunci yang dibutuhkan untuk tingkat keamanan target.

Clinical relevance

Keamanan yang dapat dibuktikan adalah standar di mana skema kriptografi mendapatkan kepercayaan dan standardisasi: AES, SHA-3, dan proses pasca-kuantum NIST sangat mempertimbangkan bukti keamanan, dan protokol seperti TLS 1.3 disertai dengan analisis reduksionis dan yang diperiksa mesin. Memahami reduksi memungkinkan praktisi menilai apa yang dijamin dan tidak dijamin oleh klaim keamanan, dan memilih parameter yang memperhitungkan ketatnya reduksi.

Evidence & guidelines

Praktik modern mendukung bukti dalam model standar jika memungkinkan dan memperlakukan bukti oracle acak sebagai bukti heuristik yang kuat daripada jaminan mutlak. Kerangka kerja yang dibantu alat (EasyCrypt, CryptoVerif) menyediakan bukti yang diperiksa mesin. Analisis keamanan konkret (tepat), yang mengukur keuntungan musuh sebagai fungsi sumber daya, lebih disukai daripada pernyataan asimtotik murni untuk menetapkan parameter nyata.

History

Metodologi reduksionis muncul dengan revolusi definisi awal 1980-an dan disistematisasi sepanjang 1990-an. Bellare dan Rogaway memperkenalkan model oracle acak (1993) untuk membuktikan skema praktis aman, dan kemudian analisis 'keamanan konkret' untuk mengukur jaminan. Hasil Canetti, Goldreich, dan Halevi tahun 1998 yang menunjukkan skema aman dalam model oracle acak tetapi tidak aman ketika diinstansiasi mempertajam perdebatan mengenai model ideal.

Key figures

Mihir Bellare
Phillip Rogaway
Oded Goldreich
Shafi Goldwasser
Silvio Micali

Seminal works

bellare1993
katz2020
goldreich2001

Frequently asked questions

Apakah bukti keamanan berarti skema tidak akan pernah bisa dibobol?: Tidak. Bukti menunjukkan bahwa membobol skema menyiratkan pemecahan masalah yang diasumsikan sulit dalam model yang ditentukan. Jika asumsi gagal, model tidak realistis, atau implementasi menyimpang dari skema yang dianalisis, serangan tetap mungkin terjadi. Bukti mengurangi, tetapi tidak menghilangkan, risiko.
Mengapa model oracle acak dianggap kontroversial?: Ini memodelkan fungsi hash sebagai fungsi yang sangat acak, yang tidak ada fungsi konkret yang benar-benar demikian. Bukti dalam model ini adalah bukti kuat dan memungkinkan skema yang efisien, tetapi ada skema (buatan) yang aman dalam model tersebut namun tidak aman setelah oracle diganti dengan hash nyata apa pun, sehingga bukti semacam itu bersifat heuristik.