Что такое задача жесткой решетки? Нить 🧵

Криптография на основе решеток основывается на центральной задаче: нахождении короткого векторного решения s для системы линейных уравнений по модулю целого числа q (обычно простого или степени простого числа). Это называется задачей SIS (Short Integer Solution), которая проста по форме, но считается сложной для квантовых/классических атак.

Существует две основные версии: неоднородная форма, используемая как односторонняя функция f_A(s) = A * s mod q в схемах обязательств, где мы решаем A * s = t (mod q), заданные A и целевое t...

...и однородная задача SIS, которая заключается в нахождении короткого вектора s, такого что A * s = 0 (mod 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 легко сформулировать, но крайне трудно решить, играя фундаментальную роль в обязательствах, доказательствах с нулевым разглашением и более широкой постквантовой безопасности.