Asumsi Kekerasan Komputasi

Asumsi kekerasan komputasi adalah dugaan yang belum terbukti namun telah dipelajari dengan baik — seperti kesulitan faktorisasi, logaritma diskrit, dan masalah kisi — yang menjadi dasar keamanan skema kriptografi.

Definition

Asumsi kekerasan komputasi adalah dugaan bahwa suatu masalah komputasi tertentu tidak dapat diselesaikan secara efisien (dalam waktu polinomial) oleh musuh yang realistis, yang berfungsi sebagai fondasi di mana keamanan yang dapat dibuktikan dibangun.

Scope

Topik ini mencakup asumsi-asumsi yang menjadi sandaran kriptografi: keberadaan fungsi satu arah, masalah teori bilangan (faktorisasi, RSA, logaritma diskrit), serta masalah kisi dan kode yang digunakan dalam kriptografi pasca-kuantum. Topik ini membahas hierarki antar asumsi, perbedaan antara kekerasan kasus terburuk dan kasus rata-rata, serta bagaimana asumsi-asumsi tersebut divalidasi. Topik ini tidak mencakup mekanisme reduksi yang menghubungkan asumsi dengan skema dan definisi keamanan itu sendiri, yang dibahas dalam topik terkait.

Core questions

• Mengapa keamanan kriptografi harus didasarkan pada asumsi kekerasan yang belum terbukti?
• Apa saja asumsi utama (fungsi satu arah, faktorisasi, logaritma diskrit, kisi)?
• Bagaimana asumsi-asumsi saling berhubungan dalam kekuatan?
• Apa perbedaan antara kekerasan kasus terburuk dan kasus rata-rata?
• Bagaimana masalah sulit kandidat divalidasi, dan apa yang terjadi jika salah satunya gagal?

Key concepts

• fungsi satu arah
• fungsi perangkap
• asumsi faktorisasi bilangan bulat
• asumsi logaritma diskrit
• asumsi RSA dan Diffie-Hellman
• pembelajaran dengan kesalahan (LWE)
• kekerasan kasus terburuk vs kasus rata-rata
• P versus NP
• hierarki asumsi

Key theories

Fungsi satu arah sebagai asumsi minimal

Keberadaan fungsi satu arah — mudah dihitung, sulit dibalik — diperlukan dan cukup untuk sebagian besar kriptografi simetris dan merupakan asumsi paling dasar; hampir semua kriptografi mengandaikan setidaknya ini.

Asumsi teori bilangan dan kisi

Kriptografi kunci publik bertumpu pada masalah terstruktur — faktorisasi bilangan bulat, masalah RSA, dan logaritma diskrit (secara klasik), serta masalah pembelajaran-dengan-kesalahan dan vektor terpendek dalam kisi (pasca-kuantum) — masing-masing didukung oleh puluhan tahun pengawasan kriptanalitik.

Mechanisms

Kriptografi membutuhkan masalah yang sulit secara rata-rata (pada instansi acak), bukan hanya dalam kasus terburuk, karena kunci dipilih secara acak. Asumsi-asumsi diorganisasikan ke dalam hierarki kasar: pelanggaran asumsi yang lebih lemah (misalnya, faktorisasi) sering kali merusak skema yang dibangun di atasnya, sementara reduksi menghubungkan asumsi satu sama lain. Asumsi kisi terkenal karena reduksi kasus terburuk ke kasus rata-rata, memberikan kepercayaan yang lebih kuat. Kepercayaan pada asumsi apa pun berasal dari upaya kriptanalitik yang berkelanjutan dan gagal, bukan dari bukti.

Clinical relevance

Asumsi kekerasan menentukan apa yang aman dan tidak aman untuk diterapkan. Penemuan bahwa komputer kuantum akan memecahkan faktorisasi dan logaritma diskrit (melalui algoritma Shor) membatalkan asumsi di balik RSA dan kriptografi kurva elips terhadap musuh kuantum, secara langsung mendorong pergeseran ke standar pasca-kuantum berbasis kisi. Memilih skema yang dibangun di atas asumsi yang telah dipelajari dengan baik, dan melacak statusnya, sangat penting untuk keamanan jangka panjang.

Evidence & guidelines

Badan standar menyukai asumsi dengan rekam jejak kriptanalitik yang panjang; proses pasca-kuantum NIST secara eksplisit mengevaluasi kematangan dan kepercayaan asumsi kisi, kode, dan hash yang mendasarinya. Praktik terbaik menghindari asumsi eksotis atau yang baru diusulkan untuk sistem dengan jaminan tinggi dan lebih memilih masalah yang konservatif dan telah divalidasi dengan baik, dengan ukuran kunci yang ditetapkan berdasarkan serangan terbaik yang diketahui.

History

Ketergantungan pada kekerasan muncul dengan kriptografi kunci publik pada tahun 1976, ketika Diffie dan Hellman mengaitkan keamanan dengan logaritma diskrit, dan RSA dengan faktorisasi. Tahun 1980-an memformalkan fungsi satu arah dan perbedaan kasus terburuk/kasus rata-rata. Reduksi kasus terburuk ke kasus rata-rata Ajtai (1996) dan masalah pembelajaran-dengan-kesalahan Regev (2005) menetapkan asumsi kisi, yang mendapatkan prominensi sebagai fondasi tahan kuantum dan menjadi dasar standar pasca-kuantum yang baru.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

Mengapa kita tidak bisa membuktikan bahwa masalah-masalah ini sulit?

Membuktikan bahwa suatu masalah membutuhkan waktu super-polinomial akan menyelesaikan pertanyaan terbuka yang mendalam dalam teori kompleksitas (terutama P versus NP), yang masih belum terpecahkan. Jadi kriptografi mengandalkan asumsi yang plausibilitasnya berasal dari puluhan tahun upaya yang tidak berhasil untuk menyelesaikannya secara efisien.

Apa yang terjadi jika asumsi kekerasan dilanggar?

Setiap skema yang keamanannya direduksi ke asumsi tersebut menjadi berpotensi tidak aman dan harus diganti. Inilah sebabnya mengapa ancaman kuantum terhadap faktorisasi dan logaritma diskrit mendorong migrasi global ke skema yang didasarkan pada asumsi yang berbeda, yang tahan kuantum.