Суперсингулярный граф изогении

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

Определение и свойства

Суперсингулярный граф изогении определяется выбором большого простого числа $p$ и небольшое простое число $\ell$ и рассматривая класс всех суперсингулярных эллиптических кривых, определенных над конечным полем $\mathbb {F} _{p^{2}}$ . Есть примерно $(p+1)/12$ такие кривые, каждые две из которых могут быть связаны изогениями. Вершины суперсингулярного графа изогении представляют эти кривые (или, более конкретно, их $j$ -инварианты , элементы $\mathbb {F} _{p^{2}}$ ), а ребра представляют собой изогении степени $\ell$ между двумя кривыми. ^[1]^[2]^[3]

Суперсингулярные графы изогений: $\ell +1$ - регулярные графы , означающие, что каждая вершина имеет ровно $\ell +1$ соседи. Пайзер доказал, что они являются графами Рамануджана , графами с оптимальными свойствами расширения для своей степени. ^[1]^[2]^[4]^[5] Доказательство основано на Пьера Делиня доказательстве гипотезы Рамануджана-Петерссона . ^[4]

Криптографические приложения

Одно из предложений по созданию криптографической хеш-функции включает в себя начало с фиксированной вершины суперсингулярного графа изогении, использование битов двоичного представления входного значения для определения последовательности ребер, которым необходимо следовать при обходе графа, и использование тождества вершина, достигнутая в конце обхода, как значение хеш-функции для ввода. Безопасность предлагаемой схемы хеширования основана на предположении, что в этом графе трудно найти пути, соединяющие произвольные пары вершин. ^[1]

Также было предложено использовать обходы в двух суперсингулярных графах изогений с одним и тем же набором вершин, но разными наборами ребер (определяемыми с использованием разных вариантов выбора $\ell$ параметр) для разработки примитива обмена ключами, аналогичного обмену ключами Диффи-Хеллмана , называемого обменом ключами суперсингулярной изогении , ^[2] предложен как форма постквантовой криптографии . ^[6] Однако ведущий вариант обмена ключами суперсингулярной изогении был взломан в 2022 году с использованием неквантовых методов. ^[7]

Ссылки

^ Перейти обратно: ^а ^б ^с Чарльз, Денис X.; Лаутер, Кристин Э .; Горен, Эял З. (2009), «Криптографические хеш-функции из графов-расширителей» (PDF) , Journal of Cryptology , 22 (1): 93–113, doi : 10.1007/s00145-007-9002-x , MR 2496385 , S2CID 6417679
^ Перейти обратно: ^а ^б ^с Де Фео, Лука; Джао, Дэвид; Плют, Жером (2014), «К квантовоустойчивым криптосистемам на основе суперсингулярных изогений эллиптических кривых» (PDF) , Журнал математической криптологии , 8 (3): 209–247, doi : 10.1515/jmc-2012-0015 , MR 3259113 , S2CID 10873244
^ Местре, Ж.-Ф. (1986), «Метод графов. Примеры и приложения», Труды международной конференции по числам классов и фундаментальным единицам полей алгебраических чисел (Катата, 1986) , Университет Нагои, стр. 217–242, MR 0891898
^ Перейти обратно: ^а ^б Пайзер, Арнольд К. (1990), «Графы Рамануджана и операторы Гекке», Бюллетень Американского математического общества , New Series, 23 (1): 127–137, doi : 10.1090/S0273-0979-1990-15918-X , МР 1027904
^ Пайзер, Арнольд К. (1998), «Графы Рамануджана», Вычислительные перспективы теории чисел (Чикаго, Иллинойс, 1995) , AMS/IP Stud. Адв. Матем., вып. 7, Американское математическое общество, стр. 159–178, MR 1486836.
^ Эйзентрагер, Кирстен ; Халлгрен, Шон; Лаутер, Кристин ; Моррисон, Трэвис; Пети, Кристоф (2018), «Суперсингулярные графы изогений и кольца эндоморфизмов: редукции и решения» (PDF) , в Нильсене, Йеспере Буусе; Реймен, Винсент (ред.), Достижения в криптологии – EUROCRYPT 2018: 37-я ежегодная международная конференция по теории и применению криптографических методов, Тель-Авив, Израиль, 29 апреля – 3 мая 2018 г., Материалы, Часть III (PDF) , Лекция Заметки по информатике, том. 10822, Чам: Спрингер, стр. 329–368, doi : 10.1007/978-3-319-78372-7_11 , MR 3794837 , S2CID 4850644
^ Гудин, Дэн (2 августа 2022 г.), «Претендент на постквантовое шифрование уничтожен одноядерным ПК и 1 час: предоставьте математикам возможность испортить то, что выглядело как новый впечатляющий алгоритм» , Ars Technica

[clg-1] Перейти обратно: ^а ^б ^с Чарльз, Денис X.; Лаутер, Кристин Э .; Горен, Эял З. (2009), «Криптографические хеш-функции из графов-расширителей» (PDF) , Journal of Cryptology , 22 (1): 93–113, doi : 10.1007/s00145-007-9002-x , MR 2496385 , S2CID 6417679

[fjp-2] Перейти обратно: ^а ^б ^с Де Фео, Лука; Джао, Дэвид; Плют, Жером (2014), «К квантовоустойчивым криптосистемам на основе суперсингулярных изогений эллиптических кривых» (PDF) , Журнал математической криптологии , 8 (3): 209–247, doi : 10.1515/jmc-2012-0015 , MR 3259113 , S2CID 10873244

[m-3] Местре, Ж.-Ф. (1986), «Метод графов. Примеры и приложения», Труды международной конференции по числам классов и фундаментальным единицам полей алгебраических чисел (Катата, 1986) , Университет Нагои, стр. 217–242, MR 0891898

[p1-4] Перейти обратно: ^а ^б Пайзер, Арнольд К. (1990), «Графы Рамануджана и операторы Гекке», Бюллетень Американского математического общества , New Series, 23 (1): 127–137, doi : 10.1090/S0273-0979-1990-15918-X , МР 1027904

[p2-5] Пайзер, Арнольд К. (1998), «Графы Рамануджана», Вычислительные перспективы теории чисел (Чикаго, Иллинойс, 1995) , AMS/IP Stud. Адв. Матем., вып. 7, Американское математическое общество, стр. 159–178, MR 1486836.

[ehlmp-6] Эйзентрагер, Кирстен ; Халлгрен, Шон; Лаутер, Кристин ; Моррисон, Трэвис; Пети, Кристоф (2018), «Суперсингулярные графы изогений и кольца эндоморфизмов: редукции и решения» (PDF) , в Нильсене, Йеспере Буусе; Реймен, Винсент (ред.), Достижения в криптологии – EUROCRYPT 2018: 37-я ежегодная международная конференция по теории и применению криптографических методов, Тель-Авив, Израиль, 29 апреля – 3 мая 2018 г., Материалы, Часть III (PDF) , Лекция Заметки по информатике, том. 10822, Чам: Спрингер, стр. 329–368, doi : 10.1007/978-3-319-78372-7_11 , MR 3794837 , S2CID 4850644

[goodin-7] Гудин, Дэн (2 августа 2022 г.), «Претендент на постквантовое шифрование уничтожен одноядерным ПК и 1 час: предоставьте математикам возможность испортить то, что выглядело как новый впечатляющий алгоритм» , Ars Technica

[1]

[2]

[3]

[4]

[5]

[6]

[7]