Быстрая факторизация и постквантовые алгоритмы
Кстати, если вдруг придумают алгоритм быстрой факторизации больших полупростых чисел, сломав тем самым RSA, то, конечно, “популярной мотивации” для создания универсального квантового компьютера станет сильно меньше: на этом направлении всегда пишут про алгоритм Шора. А вот с необходимостью перехода на постквантовые криптосистемы, в этом случае, есть интересные особенности.
Так, обнаружение алгоритма быстрой факторизации, естественно, легко может грозить тем, что попутно обнаружится и способ быстро сломать задачи типа привычного эллиптического варианта Диффи-Хеллмана (читай – ECDSA). Однако только из этого не следует автоматически вывод, что переходить требуется именно на постквантовые криптосистемы. Вот тут и начинаются особенности. Во-первых, постквантовые криптосистемы уже разработаны, уже имеют какую-то практическую “классическую” стойкость, уже реализованы, – так что их быстрее внедрить; во-вторых, задачи, на которых базируются те или иные постквантовые криптосистемы, имеют гораздо больше шансов сохранить известную сложность после обнаружения каких-то принципиально новых методов быстрой факторизации – это, конечно, тоже не гарантируется, однако для ускорения факторизации/логарифмирования до сих пор использовались математические конструкции, которые, в общем-то, стоят и за многими постквантовыми алгоритмами.
Адрес записки: https://dxdt.ru/2023/11/07/11463/
Похожие записки:
- Перспективный ИИ в "разработке кода"
- Неравенство треугольника в Интернете и anycast
- Кусочки папирусов и буквы манускриптов
- "Сверхмашинный" интеллект
- "Лазейки" вокруг неравенства Белла
- Реплика: возможный доступ приложений "Яндекса" к OBD автомобиля
- Выключение вариантов в двухщелевом опыте
- Превентивное удаление "цифровых следов" и художественное произведение
- Распознавание TLS-клиентов в трафике
- Open Source и добавление "вредоносного кода"
- Подводные кабели и связность Интернета
Написать комментарий