Криптографические схемы, основанные на теории решеток
На английском языке: Lattice-based cryptography
Коротко
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о сложности некоторых математических задач, связанных с теорией целочисленных решеток. В частности, на таких задачах основано большинство финалистов конкурса NIST — алгоритмы CRYSTALS-KYBER, NTRU, SABER, CRYSTALS-DILITHIUM, FALCON и альтернативные финалисты FrodoKEM, NTRUprime, а также подавляющее количество участников конкурса CACR.
Криптографические алгоритмы данного семейства отличаются относительно высокой эффективностью и обладают ключами умеренной длины. Однако, некоторые из схем шифрования и выработки общего ключа по построению обладают возможностью ошибки ― некорректного декодирования. Усилия криптоаналитиков направлены на оптимальный выбор параметров данных алгоритмов, позволяющих найти баланс между стойкостью и производительностью и одновременно минимизирующих вероятность ошибки.
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о сложности некоторых математических задач, связанных с теорией целочисленных решеток. В частности, на таких задачах основано большинство финалистов конкурса NIST — алгоритмы CRYSTALS-KYBER, NTRU, SABER, CRYSTALS-DILITHIUM, FALCON и альтернативные финалисты FrodoKEM, NTRUprime, а также подавляющее количество участников конкурса CACR.
Криптографические алгоритмы данного семейства отличаются относительно высокой эффективностью и обладают ключами умеренной длины. Однако, некоторые из схем шифрования и выработки общего ключа по построению обладают возможностью ошибки ― некорректного декодирования. Усилия криптоаналитиков направлены на оптимальный выбор параметров данных алгоритмов, позволяющих найти баланс между стойкостью и производительностью и одновременно минимизирующих вероятность ошибки.
Подробно
Под решеткой понимают подмножество векторов многомерного евклидова пространства, которые образуют дискретную подгруппу относительно операции сложения. К изучению решеток сводятся многие алгебраические задачи, так, например, алгоритмические методы теории решеток давно получили широкое распространение при криптоанализе классических систем с открытым ключом (RSA, DSA). Активные исследования в данной области привели к обнаружению ряда сложных задач, которые могут быть положены в основу квантово-устойчивых криптографических алгоритмов.
К числу сложных задач теории решеток относятся, например, NP-задачи поиска кратчайшего вектора (SVP) и поиска ближайшего вектора (CVP), задача обучения с ошибками и ее варианты (LWE, RLWE) и задача поиска наименьшего целочисленного решения системы линейных алгебраических уравнений (SIS).
Под решеткой понимают подмножество векторов многомерного евклидова пространства, которые образуют дискретную подгруппу относительно операции сложения. К изучению решеток сводятся многие алгебраические задачи, так, например, алгоритмические методы теории решеток давно получили широкое распространение при криптоанализе классических систем с открытым ключом (RSA, DSA). Активные исследования в данной области привели к обнаружению ряда сложных задач, которые могут быть положены в основу квантово-устойчивых криптографических алгоритмов.
К числу сложных задач теории решеток относятся, например, NP-задачи поиска кратчайшего вектора (SVP) и поиска ближайшего вектора (CVP), задача обучения с ошибками и ее варианты (LWE, RLWE) и задача поиска наименьшего целочисленного решения системы линейных алгебраических уравнений (SIS).
Впервые конструкция криптографической схемы на основе теории решеток была предложена в 1996 году в работах М. Аджтая и С. Дворк. В 1998 году группа исследователей предложила хорошо зарекомендовавшую себя на практике, но не обладающую теоретическим обоснованием схему NTRU (обоснование ее стойкости было получено позже). Наконец, в 2005 году О. Реджев предложил задачу обучения с ошибками и эффективные криптосхемы на ее основе, обладающие как практической, так и теоретической доказуемой стойкостью.
В истории криптографии,основанной на теории решеток, есть и громкие примеры неудачных синтезных решений - так, схема шифрования GGH (Гольдрайх-Гольдвассер-Шалеви, 1997) была взломана (Нгуен, 1999).
В истории криптографии,основанной на теории решеток, есть и громкие примеры неудачных синтезных решений - так, схема шифрования GGH (Гольдрайх-Гольдвассер-Шалеви, 1997) была взломана (Нгуен, 1999).
Отметим также возможности применения теории решеток при создании схем гомоморфного шифрования.
К числу достоинств криптографических схем, основанных на теории решеток, относятся их хорошая изученность, возможность эффективной реализации (отметим здесь систему NTRU, практически не уступающую в скорости классическим системам типа RSA при одинаковом уровне стойкости) и относительно невысокий порог входа для исследователей. В то же время в этих схемах не всегда удается добиться приемлемого на практике размера параметров.
К числу достоинств криптографических схем, основанных на теории решеток, относятся их хорошая изученность, возможность эффективной реализации (отметим здесь систему NTRU, практически не уступающую в скорости классическим системам типа RSA при одинаковом уровне стойкости) и относительно невысокий порог входа для исследователей. В то же время в этих схемах не всегда удается добиться приемлемого на практике размера параметров.
Как уже сегодня использовать криптографические схемы, основанные на теории решеток для защиты данных вашего бизнеса?
Команда QApp уделяет большое внимание исследованию криптографических алгоритмов на основе сложных задач теории решеток. Так, в библиотеку PQLR SDK включены алгоритмы инкапсуляции ключа SABER и подписи FALCON.
Команда QApp уделяет большое внимание исследованию криптографических алгоритмов на основе сложных задач теории решеток. Так, в библиотеку PQLR SDK включены алгоритмы инкапсуляции ключа SABER и подписи FALCON.