Что такое решетчатая криптография?

Криптография на основе решеток использует математическую структуру решеток — регулярных сеток точек в многомерном пространстве — для создания криптографических систем, устойчивых к квантовым атакам. Он формирует основу для стандартизированных NIST алгоритмов, включая Kyber (ML-KEM), используемых в квантово-устойчивых криптовалютных кошельках.

Математическая решетка определяется набором базисных векторов, причем точки решетки представляют собой все целочисленные линейные комбинации этих векторов. В больших размерностях (сотни или тысячи) некоторые проблемы на решетках становятся вычислительно неразрешимыми даже для квантовых компьютеров.

Основной сложной задачей является задача о кратчайшем векторе (SVP): по заданной решетке найти кратчайший ненулевой вектор. Тесно связана проблема обучения с ошибками (LWE): по заданным линейным уравнениям с небольшими добавленными случайными ошибками восстанавливаются секретные значения. Этим проблемам противостоят как классические, так и квантовые алгоритмы.

Kyber-768 реализует Module-LWE, структурированный вариант, обеспечивающий эффективность при сохранении безопасности. Открытые ключи кодируют точки решетки, скрытые ошибками; расшифровка использует знание базовой структуры для восстановления общих секретов, несмотря на шум.

Решетчатая криптография предлагает несколько преимуществ: относительно небольшие размеры ключей по сравнению с другими постквантовыми семействами, эффективные вычисления, универсальность шифрования и подписей, а также десятилетия исследований, подтверждающих предположения о надежности. По этим причинам NIST выбрал решетчатые схемы в качестве основных стандартов.

Потенциальные проблемы включают в себя алгебраическую структуру, которая потенциально делает возможной будущие атаки (смягчается за счет консервативного выбора параметров) и то, что она новее классической криптографии (решается посредством обширного публичного криптоанализа во время оценки NIST).

SynX реализует Kyber-768, стандартизированный NIST механизм инкапсуляции ключей на основе решетки, обеспечивающий квантово-устойчивый обмен ключами для операций с кошельком. В сочетании с подписями SPHINCS+ на основе хэша это создает глубокую защиту с использованием различных криптографических основ.