Постквантовая стандартизация криптографии - Post-Quantum Cryptography Standardization

Постквантовая стандартизация криптографии это проект NIST стандартизировать постквантовая криптография.^[1] Было представлено 23 схемы подписи, 59 схем шифрования / KEM^[2] к первоначальному сроку подачи заявок в конце 2017 года, 69 из которых были признаны завершенными и надлежащими и участвовали в первом раунде. Семь из них прошли в третий раунд, о котором было объявлено 22 июля 2020 года (четыре шифрования / ключа- установление и три схемы подписи).

Фон

В отчете NIST, опубликованном в апреле 2016 года, цитируются эксперты, которые признают возможность квантовой технологии для визуализации широко используемых ЮАР к 2030 году алгоритм станет небезопасным.^[3] В результате возникла необходимость стандартизации квантово-безопасный возникли криптографические примитивы. Поскольку большинство симметричных примитивов относительно легко модифицировать таким образом, чтобы сделать их квантово-устойчивыми, усилия были сосредоточены на криптографии с открытым ключом, а именно цифровые подписи и механизмы инкапсуляции ключей. В декабре 2016 года NIST инициировал процесс стандартизации, объявив конкурс заявок.^[4]

Соревнование сейчас находится в третьем раунде из ожидаемых четырех, где в каждом раунде одни алгоритмы отбрасываются, а другие изучаются более тщательно. NIST надеется опубликовать документы по стандартизации к 2024 году, но может ускорить процесс, если крупные прорывы в квантовые вычисления сделаны.

В настоящее время не решено, будут ли будущие стандарты опубликованы как FIPS или как специальная публикация NIST (SP).

Первый раунд

На рассмотрении находились:^[5]
(зачеркивание означает, что он был отозван)

Тип	ПКЕ / КЕМ	Подпись	Подпись и PKE / KEM
Решетка	Компактный LWE КРИСТАЛЛЫ-КИБЕР Обмен ключами Ding ЭМБЛЕМА и REMBLEM FrodoKEM HILA5 (сняты и объединены в Round5) KCL (pka OKCN / AKCN / CNKE) КИНДИ LAC ЛИМА Ящерица ЛОТОС Новая надежда NTRUEncrypt[6] НТРУ-ХСС-КЭМ НТРУ Прайм Странный Манхэттен Раунд 2 (сняты и объединены в Round5) Round5 (слияние Round2 и Hila5, объявлено 4 августа 2018 г.)[7] САБРА Три медведя Титана	КРИСТАЛЛЫ-ДИЛИТИЙ DRS СОКОЛ pqNTRUSign[6] qTESLA
На основе кода	Большое землетрясение ВЕЛОСИПЕД Классический МакЭлис DAGS Эдон-К HQC ОЗЕРО (сняты и объединены в ROLLO) LEDAkem LEDApkc Лептон ЛОКЕР (сняты и объединены в ROLLO) Макни НТС-КЭМ РОЛЛО (слияние Уроборос-Р, LAKE и LOCKER) [8] Уроборос-Р (сняты и объединены в ROLLO) QC-MDPC KEM Ramstake RLCE-KEM RQC	pqsigRM RaCoSS RankSign
На основе хеша		Гравитация-СФИНКЫ СФИНКЫ +
Многомерный	CFPKM Гиофант	DualModeMS GeMSS Gui HiMQ-3 LUOV MQDSS Радуга	SRTPI DME
Группа кос		ОрехDSA
Изогения суперсингулярной эллиптической кривой	SIKE
Сатирическое подчинение			pqЮАР[9][10]
Другой	Угадай снова HK17 Mersenne-756839 RVB	Пикник

Опубликованные атаки в первом раунде

• Угадай снова, Лоренц Панни ^[11]
• RVB Лоренца Панни^[12]
• RaCoSS от Дэниел Дж. Бернштейн, Андреас Хюлсинг, Таня Ланге и Лоренц Панни^[13]
• HK17 Даниэля Бернштейна и Тани Ланге^[14]
• SRTPI Бо-Инь Ян^[15]
• ОрехDSA
  • Уорд Бёленс и Саймон Р. Блэкберн^[16]
  • Матвей Котов, Антон Меньшов и Александр Ушаков^[17]
• DRS Ян Ю и Лео Дука ^[18]
• DAGS Элиз Барелли и Ален Куврёр^[19]
• Эдон-К от Матье Лекена и Жан-Пьера Тиллиха^[20]
• RLCE Алена Куврера, Матье Лекена и Жан-Пьера Тиллиха^[21]
• Hila5 Даниэля Дж. Бернстайна, Леона Гроота Брундеринка, Тани Ланге и Лоренца Панни^[22]
• Гиофант Уорда Белленса, Воутера Кастрика и Фредерика Веркаутерена^[23]
• Знак ранга Томаса Дебрис-Алазара и Жан-Пьера Тиллиха ^[24]
• Макни Филиппа Габорита ^[25]; Терри Шу Чиен Лау и Чик Хау Тан ^[26]

Второй раунд

Кандидаты, прошедшие во второй тур, были объявлены 30 января 2019 года. Это:^[27]

Тип	ПКЕ / КЕМ	Подпись
Решетка	КРИСТАЛЛЫ-КИБЕР[28] FrodoKEM[29] LAC Новая надежда[30] НТРУ (слияние NTRUEncrypt и NTRU-HRSS-KEM)[6] НТРУ Прайм[31] Round5 (слияние Round2 и Hila5, объявлено 4 августа 2018 г.)[7] САБРА[32] Три медведя[33]	КРИСТАЛЛЫ-ДИЛИТИЙ[28] СОКОЛ[34] qTESLA[35]
На основе кода	ВЕЛОСИПЕД[36] Классический МакЭлис HQC[37] LEDAcrypt (слияние LEDAkem[38] и LEDApkc[39]) НТС-КЭМ[40] РОЛЛО (слияние Уроборос-Р, LAKE и LOCKER) [8] RQC[41]
На основе хеша		СФИНКЫ +[42]
Многомерный		GeMSS[43] LUOV[44] MQDSS[45] Радуга
Изогения суперсингулярной эллиптической кривой	SIKE[46]
Доказательства с нулевым разглашением		Пикник[47]

Третий раунд

22 июля 2020 года NIST объявил семь финалистов («первый трек»), а также восемь альтернативных алгоритмов («второй трек»). Первый трек содержит алгоритмы, которые кажутся наиболее многообещающими и будут рассмотрены для стандартизации в конце третьего раунда. Алгоритмы на втором треке все еще могут стать частью стандарта после завершения третьего раунда.^[48] NIST ожидает, что некоторые из альтернативных кандидатов будут рассмотрены в четвертом раунде.

Финалисты

Тип	ПКЕ / КЕМ	Подпись
Решетка[а]	КРИСТАЛЛЫ-КИБЕР НТРУ САБРА	КРИСТАЛЛЫ-ДИЛИТИЙ СОКОЛ
На основе кода	Классический МакЭлис
Многомерный		Радуга

Альтернативные кандидаты

Тип	ПКЕ / КЕМ	Подпись
Решетка	FrodoKEM НТРУ Прайм
На основе кода	ВЕЛОСИПЕД HQC
На основе хеша		СФИНКЫ +
Многомерный		GeMSS
Изогения суперсингулярной эллиптической кривой	SIKE
Доказательства с нулевым разглашением		Пикник

На протяжении всего конкурса, особенно после NIST объявления о финалистах и ​​альтернативных кандидатах, были озвучены различные проблемы интеллектуальной собственности, особенно в отношении схем на основе решеток, таких как Kyber и Новая надежда. NIST утверждает, что они должны принять во внимание такие соображения при выборе выигрышных алгоритмов. NIST хранит подписанные заявления от подателей, снимающих любые юридические претензии.^[49], пытаясь устранить возможность предъявления таких претензий третьими сторонами.

Смотрите также

• Стандартный процесс расширенного шифрования
• Конкурс хеш-функций NIST

Примечания

1. NIST намеревается стандартизировать не более одной из этих схем PKE / KEM на основе решеток и не более одной из этих схем подписи на основе решеток.^[48]

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

1. «Постквантовая стандартизация криптографии - постквантовая криптография». Csrc.nist.gov. 3 января 2017 г.. Получено 31 января 2019.
2. «Архивная копия». Архивировано из оригинал на 2017-12-29. Получено 2017-12-29.
3. «NIST выпустил отчет о постквантовой криптографии NISTIR 8105». Получено 5 ноября 2019.
4. «NIST просит общественность помочь будущей электронной информации». Получено 5 ноября 2019.
5. Отдел компьютерной безопасности, Лаборатория информационных технологий (3 января 2017 г.). «Прием заявок на раунд 1 - Постквантовая криптография - CSRC». Csrc.nist.gov. Получено 31 января 2019.
6. «Архивная копия». Архивировано из оригинал на 2017-12-29. Получено 2017-12-29.
7. "Группы Google". Groups.google.com. Получено 31 января 2019.
8. "РОЛЛО". Pqc-rollo.org. Получено 31 января 2019.
9. RSA с использованием 2³¹ 4096-битные простые числа для общего размера ключа 1 ТиБ. «Ключ почти умещается на жестком диске»Бернштейн, Даниэль (2010-05-28). «Макбитс и постквантовый RSA» (PDF). Получено 2019-12-10.
10. Бернштейн, Даниэль; Хенингер, Надя (2017-04-19). «Постквантовый RSA» (PDF). Получено 2019-12-10.
11. «Уважаемые все, следующий скрипт Python быстро восстанавливает сообщение из заданного зашифрованного текста« Угадай снова »без знания секретного ключа» (PDF). Csrc.nist.gov. Получено 30 января 2019.
12. Панни, Лоренц (25 декабря 2017 г.). «Атака с быстрым восстановлением ключа против отправки RVB в #NISTPQC: t…. Вычисляет закрытый из открытого ключа». Twitter. Получено 31 января 2019.
13. «Архивная копия». Архивировано из оригинал на 2017-12-26. Получено 2018-01-04.
14. «Архивная копия». Архивировано из оригинал на 2018-01-05. Получено 2018-01-04.
15. «Уважаемые, мы нарушили SRTPI под CPA и TPSig под KMA» (PDF). Csrc.nist.gov. Получено 30 января 2019.
16. Беулленс, Уорд; Блэкберн, Саймон Р. (2018). «Практические атаки на схему цифровой подписи Walnut». Eprint.iacr.org.
17. Котов, Матвей; Меньшов, Антон; Ушаков, Александр (2018). «АТАКА НА АЛГОРИТМ ЦИФРОВОЙ ПОДПИСИ ОРЕХА». Eprint.iacr.org.
18. Ю, Ян; Дукас, Лео (2018). «Обучение снова поражает: случай схемы подписи DRS». Eprint.iacr.org.
19. Барелли, Элиза; Куврёр, Ален (2018). «Эффективная структурная атака на DAGS представления NIST». arXiv:1805.05429 [cs.CR ].
20. Лекен, Матье; Тиллих, Жан-Пьер (2018). «Атака на механизм инкапсуляции ключей Edon-K». arXiv:1802.06157 [cs.CR ].
21. Куврёр, Ален; Лекен, Матье; Тиллих, Жан-Пьер (2018). «Восстановление коротких секретных ключей RLCE за полиномиальное время». arXiv:1805.11489 [cs.CR ].
22. Бернштейн, Даниэль Дж .; Groot Bruinderink, Леон; Ланге, Таня; Ланге, Лоренц (2017). "Хила5 Пиндакаас: О безопасности CCA решеточного шифрования с исправлением ошибок".
23. "Официальные комментарии" (PDF). Csrc.nist.gov. 13 сентября 2018.
24. Дебрис-Алазард, Томас; Тиллих, Жан-Пьер (2018). «Две атаки на схемы на основе кода метрики ранга: RankSign и схема шифрования на основе идентификации». arXiv:1804.02556 [cs.CR ].
25. «Боюсь, что параметры в этом предложении имеют не более 4-6 битов защиты от атаки декодирования информационного набора (ISD)» (PDF). Csrc.nist.gov. Получено 30 января 2019.
26. Лау, Терри Шу Чиен; Тан, Чик Хау (31 января 2019 г.). «Атака восстановления ключа на Макни, основанная на кодах проверки четности низкого ранга и ее возмещение». Inomata, Ацуо; Ясуда, Кан (ред.). Достижения в области информационной и компьютерной безопасности. Конспект лекций по информатике. 11049. Издательство Springer International. С. 19–34. Дои:10.1007/978-3-319-97916-8_2. ISBN  978-3-319-97915-1.
27. Отдел компьютерной безопасности, Лаборатория информационных технологий (3 января 2017 г.). «Подача заявок на 2 раунд - Постквантовая криптография - CSRC». Csrc.nist.gov. Получено 31 января 2019.
28. Швабе, Питер. "КРИСТАЛЛЫ". Pq-crystals.org. Получено 31 января 2019.
29. «ФродоКЕМ». Frodokem.org. Получено 31 января 2019.
30. Швабе, Питер. "Новая надежда". Newhopecrypto.org. Получено 31 января 2019.
31. «Архивная копия». Архивировано из оригинал на 2019-09-01. Получено 2019-01-30.
32. "САБРА". Получено 17 июн 2019.
33. "Три медведя". SourceForge.net. Получено 31 января 2019.
34. "Сокол". Сокол. Получено 26 июн 2019.
35. «qTESLA - Эффективная и постквантовая безопасная схема подписи на основе решетки». Получено 31 января 2019.
36. «ВЕЛОСИПЕД - инкапсуляция ключа с изменяющимся битом». Bikesuite.org. Получено 31 января 2019.
37. "HQC". Pqc-hqc.org. Получено 31 января 2019.
38. "Модуль инкапсуляции ключей LEDAkem". Ledacrypt.org. Получено 31 января 2019.
39. «Криптосистема с открытым ключом LEDApkc». Ledacrypt.org. Получено 31 января 2019.
40. «Архивная копия». Архивировано из оригинал на 2017-12-29. Получено 2017-12-29.
41. «РКК». Pqc-rqc.org. Получено 31 января 2019.
42. [1]
43. «Архивная копия». Архивировано из оригинал на 2019-01-31. Получено 2019-01-30.
44. "LUOV - схема подписи MQ". Получено 22 января 2020.
45. «Постквантовая подпись MQDSS». Mqdss.org. Получено 31 января 2019.
46. «SIKE - суперсингулярная инкапсуляция ключей изогении». Sike.org. Получено 31 января 2019.
47. "Пикник. Семейство пост-квантовых алгоритмов защищенной цифровой подписи". microsoft.github.io. Получено 26 февраля 2019.
48. «Отчет о состоянии второго раунда процесса стандартизации постквантовой криптографии NIST». Получено 2020-07-23.
49. «Требования к подаче и критерии оценки» (PDF).

внешняя ссылка

• Сайт постквантовой криптографии к djb
• Кандидаты первого тура по областям к Рио Фудзита
• Кандидаты первого тура по областям (пересмотрено)
• Кандидаты первого раунда по областям (повторно пересмотрено)