Тестирование заявок PQC NIST round3

Я новичок в этой области и у меня есть некоторые опасения по поводу PQC;

Как NIST проводит сравнение того, что конкретный алгоритм эффективен и его безопасность не может быть нарушена будущими квантовыми атаками? Я с энтузиазмом понимаю критерии.

Пытался ли NIST взломать алгоритм шифрования, применив алгоритм Шора с помощью доступного квантового компьютера IBM?

Каковы критерии NIST для проверки подачи алгоритмов PQC?

Как NIST проводит сравнение того, что конкретный алгоритм эффективен и его безопасность не может быть нарушена будущими квантовыми атаками?

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

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

Единственная разница между алгоритмом PQC и алгоритмом без PQC заключается в том, что для алгоритма PQC мы также рассматриваем алгоритмы криптоанализа, которые выполняются на квантовом компьютере. Это несколько сложнее, потому что у нас нет ничего, что могло бы запустить нетривиальный алгоритм криптоанализа (квантовый компьютер IBM и ему подобные слишком малы и не в состоянии выполнить необходимое исправление ошибок), и квантовых симуляторов (которые работают на классические компьютеры) также ограничены в количестве кубитов, с которыми они могут работать. С другой стороны, у нас действительно есть хорошее представление о том, какие операции может выполнять квантовый компьютер, и поэтому мы можем разрабатывать алгоритмы, которые могут выполняться на квантовом компьютере. NIST не занимается всей этой проектной работой — подавляющее большинство этой работы выполняется учеными и криптографами вне NIST — NIST внимательно следит за этой работой и принимает это во внимание.

Следует отметить, что конкретные оценки квантовой стойкости различных задач еще очень новый области исследований, и некоторые вопросы до сих пор не решены. Хорошим примером этого является статья Пикерта. Он дает сито C от CSIDH. Помимо отличного каламбура, в этой статье используется нечто, называемое коллиниационное сито (разработан в 2013 году Грегом Купербергом iirc), чтобы опровергнуть предположение CSIDH. Обратите внимание, что это предположение выделяется среди всех постквантовых предположений, поскольку оно непосредственно дает неинтерактивный обмен ключами, что-то такое

• довольно легко получить из классических задач (варианты дискретного логарифма), но
• для получения таких вещей, как LWE, либо требуются очень большие параметры, либо обращение к продвинутому примитиву (либо FHE, либо функциональное шифрование) — в любом случае результирующая схема неэффективна.

Суть статьи заключается в том, что коллиниационное сито не требует доступа к большому ($\приблизительно 2^{30}$) количество квантовой памяти напрямую, но вместо этого может использовать «квантово-доступную классическую память» (окончательная оценка больше, $\приблизительно 2^{40}$). Я помню, что были некоторые дебаты (я предполагаю, между Дэном Бернштейном и Крисом, но точно не помню) либо в твиттере, либо в группе nist PQC google о практических последствиях этой измененной оценки.

Очень грубо, можно охарактеризовать классическую безопасность с точки зрения пары (время, память), необходимой для взлома примитива. Тогда квантовая безопасность связана с четвёркой (классическое время, классическая память, квантовое время, квантовая память). Вопрос о том, как именно извлечь единственную оценку безопасности из такой четверки, до сих пор является предметом споров, и даже у двух экспертов по постквантовой криптографии могут быть разногласия.