Bukti Keamanan dan Reduksi dalam Skema Kisi

Pembuktian keamanan untuk suatu skema kriptografi adalah argumen matematis formal yang menunjukkan bahwa mematahkan skema tersebut berarti menyelesaikan masalah sulit yang mendasarinya. Pembuktian ini tidak menjamin keamanan mutlak; pembuktian ini menunjukkan bahwa setiap penyerang efisien terhadap skema dapat diubah menjadi pemecah masalah yang efisien untuk masalah sulit tersebut. Jika masalah sulit itu tidak dapat diselesaikan secara layak, skema tersebut aman.

Pembuktian penting Regev pada 2005 menunjukkan bahwa algoritma waktu polinomial yang menyelesaikan LWE keputusan dapat digunakan untuk menyelesaikan GapSVP (Masalah Vektor Terpendek dengan Celah) pada kisi berdimensi-n dalam kasus terburuk. Reduksi ini bersifat kuantum: reduksi ini menggunakan prosedur pengambilan sampel kuantum untuk mengubah pemecah LWE menjadi pemecah masalah kisi. Artinya, LWE setidaknya sama sulitnya dengan masalah kisi dalam kasus terburuk pada komputasi kuantum.

Reduksi Regev tidak ketat: faktor polinomial dalam reduksi tersebut berarti tingkat keamanan yang dijamin oleh pembuktian agak lebih lemah daripada yang ditunjukkan oleh serangan terbaik yang diketahui. Untuk pemilihan parameter praktis, para kriptografer menggunakan keamanan konkret yang diberikan oleh serangan terbaik yang diketahui (melalui pengestimasi kisi), bukan batas reduksi teoretis, karena reduksi tersebut bersifat konservatif.

Skema enkripsi berbasis LWE dibuktikan aman terhadap IND-CPA (tidak dapat dibedakan di bawah serangan teks terang terpilih) melalui argumen hibrida. Pembuktian tersebut menunjukkan bahwa pembeda IND-CPA mengimplikasikan pembeda LWE. Dalam hibrida pertama, teks sandi nyata digantikan dengan untaian acak seragam; ketidakdapatdibedaan mengikuti asumsi LWE. Ini memberikan pembuktian keamanan yang jelas untuk enkripsi kisi dasar.

Keamanan IND-CPA tidak memadai untuk mekanisme enkapsulasi kunci yang digunakan dalam TLS: mekanisme tersebut memerlukan keamanan IND-CCA2 (serangan teks sandi terpilih). Transformasi Fujisaki-Okamoto (FO) mengubah skema IND-CPA apa pun menjadi KEM IND-CCA2 dalam Model Oracle Acak (ROM). ML-KEM menerapkan varian transformasi FO pada enkripsi Module-LWE yang mendasarinya, sehingga menyediakan keamanan CCA2 yang diperlukan untuk penerapan di dunia nyata.

Model Oracle Acak (ROM) memodelkan fungsi hash sebagai fungsi yang benar-benar acak. Banyak pembuktian keamanan, termasuk pembuktian untuk transformasi FO, memerlukan ROM. Dalam praktiknya, fungsi hash seperti SHA-3 bukanlah oracle acak yang benar-benar acak, sehingga pembuktian ROM tidak menjamin keamanan dalam model standar. Namun, pembuktian ROM diterima secara luas dalam komunitas kriptografi sebagai bukti kuat keamanan.

Pembuktian model standar tidak membuat idealisasi apa pun tentang fungsi hash dan secara ketat lebih kuat daripada pembuktian ROM. Sebagian besar skema kisi praktis menggunakan pembuktian ROM karena pembuktian CCA2 dalam model standar untuk KEM berbasis kisi jauh lebih kompleks dan menghasilkan parameter konkret yang lebih buruk. NIST menerima pembuktian berbasis ROM untuk ML-KEM karena menganggapnya memadai untuk tingkat keamanan yang ditargetkan.

Pembuktian keamanan ML-KEM berlangsung dalam dua langkah. Pertama, enkripsi Module-LWE yang mendasarinya ditunjukkan aman terhadap IND-CPA berdasarkan asumsi M-LWE. Kedua, transformasi Fujisaki-Okamoto (khususnya transformasi T dan U yang digunakan dalam Kyber) meningkatkannya menjadi IND-CCA2 dalam ROM kuantum (QROM), yang menangani penyerang yang mengajukan kueri ke oracle acak dalam superposisi.

Pengestimasi kisi karya Albrecht, Player, dan Scott adalah alat standar untuk menghitung keamanan konkret skema berbasis LWE. Alat ini memodelkan biaya serangan kisi terbaik yang diketahui (BKZ dengan penyisiran atau enumerasi) dan menghasilkan perkiraan keamanan dalam bit untuk parameter tertentu (n, q, sigma). Alat ini diperbarui secara berkala seiring diterbitkannya algoritma baru dan model biaya perangkat keras.

Algoritma Blok Korkine-Zolotarev (BKZ) adalah algoritma reduksi kisi praktis terbaik. BKZ dengan ukuran blok beta menemukan vektor pendek dengan kompleksitas kira-kira 2^{0.292*beta} operasi gerbang menggunakan algoritma penyisiran terbaik. Untuk ML-KEM-768, perkiraan keamanan klasiknya sekitar 180 bit dan keamanan kuantumnya sekitar 164 bit, jauh di atas target 192 bit.

Pembuktian keamanan asimtotik menunjukkan bahwa suatu skema aman untuk parameter yang cukup besar, tetapi tidak menjelaskan apa arti "cukup besar" dalam praktik. Analisis keamanan konkret mengisi kesenjangan ini dengan memperkirakan biaya aktual serangan terbaik untuk parameter yang dipilih. Standardisasi pascakuantum sangat bergantung pada analisis keamanan konkret, dengan parameter yang dipilih agar tahan terhadap serangan pada perangkat keras kuantum yang diperkirakan selama jangka waktu 30 tahun.

Transformasi apa yang digunakan untuk meningkatkan enkripsi kisi IND-CPA menjadi keamanan IND-CCA2 dalam ML-KEM?

Pembuktian keamanan skema kisi mereduksi keamanan skema tersebut menjadi kesulitan LWE atau SVP. Reduksi Regev menjamin bahwa LWE setidaknya sama sulitnya dengan masalah kisi dalam kasus terburuk. Transformasi Fujisaki-Okamoto meningkatkan IND-CPA menjadi IND-CCA2 dalam ROM. Keamanan konkret dievaluasi dengan pengestimasi kisi menggunakan model kompleksitas BKZ. Kesenjangan dalam keketatan reduksi berarti parameter praktis mengandalkan perkiraan biaya serangan, bukan hanya batas reduksi.