Apa Masalah Kisi Keras? Sebuah utas 🧵

Kriptografi berbasis kisi bergantung pada tantangan utama: menemukan solusi vektor pendek s untuk sistem persamaan linier modulo bilangan bulat q (biasanya pangkat prima atau prima). Ini disebut masalah SIS (Short Integer Solution), sederhana dalam bentuk tetapi diyakini keras terhadap serangan kuantum/klasik.

Ada dua versi utama: bentuk tidak homogen yang digunakan sebagai fungsi satu arah f_A(s) = A * s mod q dalam skema komitmen, di mana kita memecahkan A * s = t (mod q) diberikan A dan target t...

... dan masalah SIS homogen, meminta untuk menemukan s pendek sedemikian rupa sehingga A * s = 0 (mod q) untuk matriks acak A.

Skema komitmen dijamin mengikat dengan kekerasan SIS. Jika A * s = t = A * s', maka A * (s - s') = 0, yang berarti menemukan s' yang berbeda memecahkan masalah SIS homogen yang keras.

Pendeknya s (norma kecil) sangat penting. Tanpa batas s, larutan sepele menggunakan aljabar linier klasik. Pembatasan norma ini mendasari sifat SIS yang sulit dipecahkan, bahkan terhadap komputer kuantum.

Hasil Ajtai tahun 1996 menghubungkan kekerasan masalah SIS untuk memecahkan masalah kisi terburuk, membentuk dasar untuk asumsi kriptografi pasca-kuantum.

Masalah SIS memungkinkan kompresi dari vektor rahasia besar s (dimensi M) ke komitmen t yang lebih pendek. Matriks A memiliki dimensi N x M, di mana N biasanya terikat dengan parameter keamanan, membuatnya menarik untuk bukti pengetahuan nol yang membutuhkan keringkasan.

Secara keseluruhan, SIS mudah dinyatakan tetapi sangat sulit untuk dipecahkan, memainkan peran mendasar dalam komitmen, bukti tanpa pengetahuan, dan keamanan pasca-kuantum yang lebih luas.