Криптография на изогениях суперсингулярных эллиптических кривых
На английском языке: Supersingular isogeny-based cryprography
Коротко
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о вычислительной сложности задачи поиска пути в графе изогений суперсингулярных эллиптических кривых и связанных задачах. Криптографические алгоритмы данного семейства отличаются относительно невысоким быстродействием, но в тоже время предлагают короткие открытые ключи и шифротексты. По состоянию на 2022 год, основные алгоритмы этого класса подвержены эффективной атаке.
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о вычислительной сложности задачи поиска пути в графе изогений суперсингулярных эллиптических кривых и связанных задачах. Криптографические алгоритмы данного семейства отличаются относительно невысоким быстродействием, но в тоже время предлагают короткие открытые ключи и шифротексты. По состоянию на 2022 год, основные алгоритмы этого класса подвержены эффективной атаке.
Подробно
Перспектива появления квантового компьютера достаточной производительности для реализации алгоритма Шора делает нестойкими традиционные протоколы выработки общего ключа типа Диффи-Хеллмана, основанные на задаче дискретного логарифмирования. Для решения этой проблемы было предложено использовать механизмы на основе математического аппарата изогений суперсингулярных эллиптических кривых.
Изогения — это рациональное отображение между двумя эллиптическими кривыми, являющееся гомоморфизмом. Если существует такого рода отображение между двумя кривыми, то они называются изогенными. Графом изогений называется граф, множеством вершин которого является множество классов изоморфизма эллиптических кривых. Две различных вершины этого графа соединены ребром тогда и только тогда, когда представители соответствующих классов изоморфизма изогенны. Если ограничиться только изогениями степени l, то получим граф l-изогений.
При рассмотрении так называемых суперсингулярных эллиптических кривых (считающихся «слабыми» в классической криптографии) оказывается, что граф их l-изогений обладает рядом свойств, позволяющих строить криптографические схемы, в основе стойкости которых лежит предположение о сложности задачи поиска пути между двумя вершинами в этом графе. Эти свойства использовались в работах Couveignes (1997), Charles-Goren-Lauter (2006), Ростовцева-Столбунова (2006) и, наконец, в работе De Feo-Jao-Plût (2011), где впервые удалось предложить стойкий и практически эффективный протокол выработки общего ключа SIDH.
В свою очередь, на основе протокола SIDH была создана схема инкапсуляции ключа SIKE, дошедшая до 4 этапа конкурса NIST. Однако, в августе 2022 года Castryk и Decru разработали эффективную атаку на протоколы SIDH и SIKE, позже доработанную Damien до получения полиномиальной оценки сложности. Таким образом, в настоящее время эффективные криптографические алгоритмы, основанные на изогениях, являются нестойкими и не могут быть использованы.
Перспектива появления квантового компьютера достаточной производительности для реализации алгоритма Шора делает нестойкими традиционные протоколы выработки общего ключа типа Диффи-Хеллмана, основанные на задаче дискретного логарифмирования. Для решения этой проблемы было предложено использовать механизмы на основе математического аппарата изогений суперсингулярных эллиптических кривых.
Изогения — это рациональное отображение между двумя эллиптическими кривыми, являющееся гомоморфизмом. Если существует такого рода отображение между двумя кривыми, то они называются изогенными. Графом изогений называется граф, множеством вершин которого является множество классов изоморфизма эллиптических кривых. Две различных вершины этого графа соединены ребром тогда и только тогда, когда представители соответствующих классов изоморфизма изогенны. Если ограничиться только изогениями степени l, то получим граф l-изогений.
При рассмотрении так называемых суперсингулярных эллиптических кривых (считающихся «слабыми» в классической криптографии) оказывается, что граф их l-изогений обладает рядом свойств, позволяющих строить криптографические схемы, в основе стойкости которых лежит предположение о сложности задачи поиска пути между двумя вершинами в этом графе. Эти свойства использовались в работах Couveignes (1997), Charles-Goren-Lauter (2006), Ростовцева-Столбунова (2006) и, наконец, в работе De Feo-Jao-Plût (2011), где впервые удалось предложить стойкий и практически эффективный протокол выработки общего ключа SIDH.
В свою очередь, на основе протокола SIDH была создана схема инкапсуляции ключа SIKE, дошедшая до 4 этапа конкурса NIST. Однако, в августе 2022 года Castryk и Decru разработали эффективную атаку на протоколы SIDH и SIKE, позже доработанную Damien до получения полиномиальной оценки сложности. Таким образом, в настоящее время эффективные криптографические алгоритмы, основанные на изогениях, являются нестойкими и не могут быть использованы.