Граф суперсингулярной изогении - Supersingular isogeny graph

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

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

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

Графы суперсингулярной изогении ${ displaystyle ell +1}$ -регулярные графики, что означает, что каждая вершина имеет ровно ${ displaystyle ell +1}$ соседи. Пайзер доказал, что они Графики Рамануджана, графики с оптимальными свойства расширения для их степени.^[1]^[2]^[4]^[5] Доказательство основано на Пьер Делинь доказательство Гипотеза Рамануджана – Петерсона.^[4]

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

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

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

Дополнительные криптографические методы, основанные на этих графиках, включают схемы подписи и криптографию с открытым ключом. Они были предложены как форма постквантовая криптография: По состоянию на 2018 год^{[Обновить]}, нет известных субэкспоненциальных методов взлома этих схем даже на квантовые компьютеры.^[6]

Рекомендации

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

[clg-1] а ^б ^c Чарльз, Денис X .; Лаутер, Кристин Э.; Горен, Эял З. (2009), «Криптографические хеш-функции из расширительных графов» (PDF), Журнал криптологии, 22 (1): 93–113, Дои:10.1007 / s00145-007-9002-x, МИСТЕР 2496385, S2CID 6417679

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]