У чому проблема з жорсткою решіткою? Нитка 🧵

Криптографія на ґратці спирається на центральне завдання: знайти короткий векторний розв'язок s системи лінійних рівнянь за модулем цілого числа q (зазвичай простого або простого ступеня). Це називається задачею SIS (Коротке ціле розв'язання), простою за формою, але вважається складною проти квантових або класичних атак.

Існує дві основні версії: неоднорідна форма, що використовується як одностороння функція f_A(s) = A * s mod q у схемах зобов'язань, де ми розв'язуємо A * s = t (модуль q) для A і ціль t...

... та однорідною задачею SIS, яка просить знайти коротке замикання s, таке, що A * s = 0 (модуль q) для випадкової матриці A.

Схема зобов'язань гарантовано буде зв'язуючою завдяки твердості SIS. Якщо A * s = t = A * s', то A * (s - s') = 0, що означає, що пошук іншого s' вирішує складну однорідну задачу SIS.

Короткість s (мала норма) є необхідною. Без обмежень s розв'язки є тривіальними за допомогою класичної лінійної алгебри. Це обмеження норми лежить в основі складнорозв'язуваної природи SIS, навіть щодо квантових комп'ютерів.

Результат Айтая 1996 року пов'язав складність задачі SIS із розв'язуванням найгірших решіткових задач, що стало основою для припущень постквантової криптографії.

Задача SIS дозволяє стиснення з великого секретного вектора s (розмір M) до коротшого зобов'язання t. Матриця A має розміри N x M, де N зазвичай прив'язана до параметра безпеки, що робить її привабливою для доказів з нульовим розгаданням, які потребують лаконічності.

У сукупності SIS легко формулювати, але надзвичайно складно розв'язати, відіграючи фундаментальну роль у зобов'язань, доказах нульового розгадування та ширшій постквантовій безпеці.