Dasar-Dasar Keamanan
Dasar-dasar keamanan menyediakan landasan matematis yang ketat untuk kriptografi: definisi yang tepat tentang arti keamanan, asumsi kesulitan yang mendasari keamanan, dan reduksi yang membuktikan skema aman.
Definition
Dasar-dasar keamanan terdiri dari kerangka kerja definisi, asumsi komputasi, dan teknik pembuktian yang digunakan untuk menentukan tujuan keamanan secara tepat dan untuk menunjukkan secara ketat bahwa konstruksi kriptografi mencapainya.
Scope
Area ini mencakup teori yang menjadikan kriptografi sebagai ilmu daripada seni: definisi keamanan formal dan model musuh, asumsi kesulitan komputasi, metodologi keamanan yang dapat dibuktikan berbasis reduksi, serta peran sentral keacakan dan keacakan semu. Ini membahas bagaimana 'aman' didefinisikan dan ditunjukkan. Ini tidak termasuk primitif dan protokol konkret yang mengimplementasikan ide-ide ini, yang dibahas di area yang berfokus pada kriptografi.
Sub-topics
Core questions
- Apa artinya, secara formal, bagi skema kriptografi untuk menjadi 'aman'?
- Bagaimana kekuatan dan tujuan musuh ditangkap dalam model yang tepat?
- Pada asumsi kesulitan yang tidak terbukti tetapi masuk akal apa keamanan bergantung?
- Bagaimana reduksi membuktikan bahwa memecahkan skema akan menyelesaikan masalah yang sulit?
- Mengapa keacakan dan keacakan semu menjadi dasar kriptografi?
Key concepts
- definisi keamanan
- model musuh
- keamanan semantik dan ketidakmampuan dibedakan
- asumsi kesulitan komputasi
- reduksi
- fungsi satu arah
- keacakan semu
- probabilitas yang dapat diabaikan
- keamanan komputasi vs. keamanan teoretis informasi
Key theories
- Keamanan semantik dan ketidakmampuan dibedakan
- Goldwasser dan Micali mendefinisikan keamanan enkripsi sebagai keamanan semantik — sebuah ciphertext tidak mengungkapkan apa pun yang berguna secara komputasi tentang plaintext — yang ditunjukkan setara dengan ketidakmampuan dibedakan ciphertext, menggantikan intuisi yang samar dengan tujuan yang tepat dan dapat dicapai.
- Keamanan yang dapat dibuktikan melalui reduksi
- Suatu skema dibuktikan aman dengan reduksi yang menunjukkan bahwa setiap musuh yang efisien yang memecahkannya dapat diubah menjadi algoritma yang memecahkan masalah yang diasumsikan sulit; keamanan dengan demikian bersifat kondisional pada asumsi tetapi ketat.
Clinical relevance
Sudut pandang fundamental inilah mengapa kriptografi modern dapat dipercaya: alih-alih berharap suatu skema tahan terhadap serangan, para perancang membuktikan bahwa memecahkannya sama sulitnya dengan masalah yang telah dipelajari dengan baik di bawah model musuh yang dinyatakan secara tepat. Metodologi ini mendasari klaim keamanan setiap primitif dan protokol standar, memandu skema mana yang disetujui oleh regulator dan badan standar, dan menjelaskan mengapa desain ad hoc yang tidak terbukti tidak disarankan.
Evidence & guidelines
Analisis keamanan yang dapat dibuktikan kini diharapkan dalam standardisasi kriptografi (kompetisi NIST untuk AES, SHA-3, dan skema pasca-kuantum semuanya mempertimbangkan bukti keamanan dan reduksi). Bukti yang diperiksa mesin (EasyCrypt) dan model standar (oracle acak, model standar) memberikan kekakuan, meskipun perdebatan tetap ada tentang asumsi ideal. Konstruksi yang keamanannya hanya bergantung pada heuristik tidak dianjurkan.
History
Kriptografi menjadi ilmu yang ketat pada awal 1980-an ketika Goldwasser dan Micali memperkenalkan enkripsi probabilistik dan keamanan semantik (1982-1984), memberikan definisi dan bukti tepat pertama. Yao dan Blum-Micali memformalkan keacakan semu, dan metodologi berbasis reduksi menyebar sepanjang tahun 1980-an dan 1990-an, dikonsolidasikan dalam 'Foundations of Cryptography' karya Goldreich. Revolusi definisi ini membedakan kriptografi modern dari pembuatan kode sebelumnya.
Key figures
- Shafi Goldwasser
- Silvio Micali
- Oded Goldreich
- Andrew Yao
- Manuel Blum
Related topics
Seminal works
- goldwasser1984
- goldreich2001
- katz2020
Frequently asked questions
- Apa sebenarnya arti 'aman secara provable'?
- Ini berarti ada bukti matematis bahwa memecahkan skema setidaknya sama sulitnya dengan memecahkan beberapa masalah yang diyakini tidak dapat dipecahkan, di bawah model musuh yang dinyatakan. Ini bukan jaminan mutlak: keamanan bersifat kondisional pada asumsi kesulitan dan model yang sesuai dengan kenyataan.
- Mengapa harus bergantung pada asumsi kesulitan yang belum terbukti sama sekali?
- Sebagian besar kriptografi yang berguna tidak dapat dibuktikan aman tanpa syarat — melakukannya akan menyelesaikan masalah terbuka besar seperti P versus NP. Sebaliknya, keamanan direduksi menjadi sejumlah kecil masalah yang telah lama dipelajari (faktorisasi, logaritma diskrit, kisi-kisi) yang kesulitannya didukung oleh puluhan tahun serangan yang gagal.