Bukti Keselamatan dan Pengurangan dalam Skema Kekisi

Pembuktian keselamatan bagi sesuatu skema kriptografi ialah hujah matematik formal yang menunjukkan bahawa memecahkan skema tersebut bermakna menyelesaikan masalah sukar yang mendasarinya. Pembuktian itu tidak menjamin keselamatan mutlak; sebaliknya, ia menunjukkan bahawa mana-mana musuh yang cekap terhadap skema tersebut boleh ditukarkan menjadi penyelesai yang cekap bagi masalah sukar itu. Jika masalah sukar tersebut tidak boleh diselesaikan secara praktik, skema itu selamat.

Pembuktian penting Regev pada tahun 2005 menunjukkan bahawa algoritma masa polinomial yang menyelesaikan LWE keputusan boleh digunakan untuk menyelesaikan GapSVP (Masalah Vektor Terpendek Berjurang) pada kekisi berdimensi n dalam kes terburuk. Pengurangan ini bersifat kuantum: ia menggunakan prosedur pensampelan kuantum untuk menukarkan penyelesai LWE kepada penyelesai kekisi. Ini bermakna LWE sekurang-kurangnya sesukar masalah kekisi dalam kes terburuk di bawah pengiraan kuantum.

Pengurangan Regev tidak ketat: faktor polinomial dalam pengurangan itu bermakna tahap keselamatan yang dijamin oleh pembuktian agak lebih lemah daripada yang dicadangkan oleh serangan terbaik yang diketahui. Untuk pemilihan parameter praktikal, ahli kriptografi menggunakan keselamatan konkrit yang diberikan oleh serangan terbaik yang diketahui melalui penganggar kekisi, bukannya batas pengurangan teori, kerana pengurangan itu bersifat konservatif.

Skema penyulitan berasaskan LWE dibuktikan selamat terhadap IND-CPA (tidak dapat dibezakan di bawah serangan teks biasa terpilih) melalui hujah hibrid. Pembuktian itu menunjukkan bahawa pembeza IND-CPA membayangkan wujudnya pembeza LWE. Dalam hibrid pertama, teks sif sebenar digantikan dengan rentetan rawak seragam; ketidakbolehbezanya mengikuti andaian LWE. Ini memberikan pembuktian keselamatan yang jelas untuk penyulitan kekisi asas.

Keselamatan IND-CPA tidak mencukupi untuk mekanisme pengkapsulan kunci yang digunakan dalam TLS: mekanisme tersebut memerlukan keselamatan IND-CCA2 (serangan teks sif terpilih). Transformasi Fujisaki-Okamoto (FO) menukarkan mana-mana skema IND-CPA kepada KEM IND-CCA2 dalam Model Orakel Rawak (ROM). ML-KEM menggunakan varian transformasi FO pada penyulitan LWE modul yang mendasarinya, lalu menyediakan keselamatan CCA2 yang diperlukan untuk penggunaan dalam sistem sebenar.

Model Orakel Rawak (ROM) memodelkan fungsi cincangan sebagai fungsi yang benar-benar rawak. Banyak pembuktian keselamatan, termasuk pembuktian untuk transformasi FO, memerlukan ROM. Dalam amalan, fungsi cincangan seperti SHA-3 bukanlah orakel rawak yang sebenar, jadi pembuktian ROM tidak menjamin keselamatan dalam model piawai. Namun begitu, pembuktian ROM diterima secara meluas dalam komuniti kriptografi sebagai bukti kukuh tentang keselamatan.

Pembuktian model piawai tidak membuat sebarang pengidealan tentang fungsi cincangan dan lebih kukuh secara ketat berbanding pembuktian ROM. Kebanyakan skema kekisi praktikal menggunakan pembuktian ROM kerana pembuktian CCA2 dalam model piawai untuk KEM berasaskan kekisi jauh lebih kompleks dan menghasilkan parameter konkrit yang lebih buruk. NIST menerima pembuktian berasaskan ROM untuk ML-KEM kerana menganggapnya mencukupi bagi tahap keselamatan yang disasarkan.

Pembuktian keselamatan ML-KEM berjalan dalam dua langkah. Pertama, penyulitan LWE modul yang mendasari ditunjukkan selamat terhadap IND-CPA di bawah andaian M-LWE. Kedua, transformasi Fujisaki-Okamoto (khususnya transformasi T dan U yang digunakan dalam Kyber) menaik tarafnya kepada IND-CCA2 dalam ROM kuantum (QROM), yang mengendalikan musuh yang membuat pertanyaan kepada orakel rawak dalam superposisi.

Penganggar kekisi oleh Albrecht, Player dan Scott ialah alat piawai untuk mengira keselamatan konkrit bagi skema berasaskan LWE. Alat ini memodelkan kos serangan kekisi terbaik yang diketahui (BKZ dengan penyaringan atau penghitungan) dan mengeluarkan anggaran keselamatan bit bagi parameter yang diberikan (n, q, sigma). Alat ini dikemas kini secara berkala apabila algoritma baharu dan model kos perkakasan baharu diterbitkan.

Algoritma Korkine-Zolotarev Berblok (BKZ) ialah algoritma pengurangan kekisi praktikal yang terbaik. BKZ dengan saiz blok beta mencari vektor pendek dengan kerumitan kira-kira 2^{0.292*beta} operasi get menggunakan algoritma penyaringan terbaik. Bagi ML-KEM-768, keselamatan klasik yang dianggarkan ialah kira-kira 180 bit dan keselamatan kuantum kira-kira 164 bit, jauh melebihi sasaran 192 bit.

Pembuktian keselamatan asimptotik menunjukkan bahawa sesuatu skema selamat untuk parameter yang cukup besar, tetapi tidak menyatakan maksud "cukup besar" dalam amalan. Analisis keselamatan konkrit mengisi jurang ini dengan menganggarkan kos sebenar serangan terbaik bagi parameter yang dipilih. Penyeragaman pascakuantum sangat bergantung pada analisis keselamatan konkrit, dengan parameter dipilih untuk menentang serangan pada perkakasan kuantum yang dijangka sepanjang tempoh 30 tahun.

Pembuktian keselamatan skema kekisi mengurangkan keselamatan skema tersebut kepada kesukaran LWE atau SVP. Pengurangan Regev menjamin bahawa LWE sekurang-kurangnya sesukar masalah kekisi dalam kes terburuk. Transformasi Fujisaki-Okamoto menaik taraf IND-CPA kepada IND-CCA2 dalam ROM. Keselamatan konkrit dinilai menggunakan penganggar kekisi dengan model kerumitan BKZ. Jurang keketatan pengurangan bermakna parameter praktikal bergantung pada anggaran kos serangan, bukannya batas pengurangan semata-mata.