Криптографические схемы, основанные на теории решеток
На английском языке: Lattice-based cryptography
Коротко
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о сложности некоторых математических задач, связанных с теорией целочисленных решеток. В частности, на таких задачах основан единственный финалист конкурса NIST в части стандартизации алгоритмов передачи ключа — CRYSTALS-KYBER, два финалиста конкурса NIST в части стандартизации схем цифровой подписи — CRYSTALS-DILITHIUM, FALCON, а также подавляющее количество участников конкурса CACR.
Криптографические алгоритмы данного семейства отличаются относительно высокой эффективностью и обладают ключами умеренной длины. Однако, некоторые из схем шифрования и выработки общего ключа по построению обладают возможностью ошибки ― некорректного декодирования. Усилия криптоаналитиков направлены на оптимальный выбор параметров данных алгоритмов, позволяющих найти баланс между стойкостью и производительностью и одновременно минимизирующих вероятность ошибки.
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о сложности некоторых математических задач, связанных с теорией целочисленных решеток. В частности, на таких задачах основан единственный финалист конкурса NIST в части стандартизации алгоритмов передачи ключа — CRYSTALS-KYBER, два финалиста конкурса NIST в части стандартизации схем цифровой подписи — CRYSTALS-DILITHIUM, FALCON, а также подавляющее количество участников конкурса 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 при одинаковом уровне стойкости) и относительно невысокий порог входа для исследователей. В то же время в этих схемах не всегда удается добиться приемлемого на практике размера параметров.