Comments 9
Ради интереса.
Если здесь есть специалисты или энтузиасты постквантовой криптографии, могли бы пояснить один момент?
Когда писал диплом и разбирался в текущих «трех» направлениях — решётки, коды и многомерка, с удивлением обнаружил, что математически первые два сводятся к одной и той же задаче. Еднственное отличие, что решётки почему-то принято демонстрировать в графическом виде, а коды по традиции идут в алгебраическом.
Кто-то может пояснить, есть ли там действительно разные задачи, или просто «исторически сложилось» два направления и их так и развивают?
Первые сводятся как правило к задаче нахождения наименьшего вектора на решетке. Вторые сводятся к задаче декодирования линейного кода. Обе эти задачи являются NP-полными и могут быть сведены друг к другу. Так что нет ничего удивительного, что математика выглядит похожей. Но state-of-the-art методы криптоанализа систем имеют разную сложность и используют отличные друг от друга методы, поэтому имеет смысл разнести задачи по отдельным классам.
NIST на протяжении последних четырех лет провели анализ предложенных постквантовых схем со всего мира

Не только NIST, но и многие команды математиков по всему миру проводили анализ. Мне даже посчастливилось работать в одной из.
Да, я немного неправильно выразился в статье. Спасибо за замечание! А каким направлением вы занимаетесь, если не секрет?
Мы занимались анализом WalnutDSA, который был одной из 69 схем, предложенных на первом этапе.
Стоит отметить, что у алгоритмов на решетках есть небольшая, но всё же вероятность получения ошибки при дешифровке (декапсуляции). Для CRYSTALS-KYBER и Saber они составляют 1 на 2^120 — 1 на 2^160.
Это не представляет проблем для online коммуникаций, там можно всё переслать. Но для оффлайн хранения данных c долгоживущими ключами есть небольшая вероятность, что файл, который будет зашифрован ключом, полученным из протокола на решетках, невозможно будет расшифровать.

Как вариант, симметричный ключ для таких случаев можно энкапсулировать дважды, но этим никто заморачиваться, конечно, не будет.
Такие дела
Стоит отметить, что у алгоритмов на решетках есть небольшая, но всё же вероятность получения ошибки при дешифровке (декапсуляции). Для CRYSTALS-KYBER и Saber они составляют 1 на 2^120 — 1 на 2^160.
Согласен, есть такая неприятная особенность у некоторых PKE/KEM на решетках, но не во всех же! У NTRU нет ошибок декапсуляции (Хотя в оригинальном NTRUEncrypt они были). У NTRU Prime (из алтернативных кандидатов) так же нет ошибок декапсуляции. По поводу величины ошибки -имхо, — 1 на 2^120 — 1 на 2^160 достаточно низкая вероятность, чтобы о ней можно было даже не беспокоиться (может, за исключением каких-то критических систем).

Это ничтожная вероятность ошибки для большинства практических применений. Гораздо меньше вероятности сгенерировать 2 одинаковых GUID'а подряд.

Only those users with full accounts are able to leave comments. Log in, please.