Реплика: быстрая факторизация квантовым компьютером и штампы в СМИ
Кстати, что касается постквантовых криптосистем от NIST и “квантовых компьютеров, взламывающих современные криптосистемы”, которые, якобы, “могут появиться через десять лет” (а могут и не появиться): есть ещё ничуть не менее распространённый штамп, утверждающий, в этом контексте, что “квантовые компьютеры кардинально быстрее решают задачу факторизации”. Факторизация – это разложение данного числа на простые множители. Однако речь в данном штампе почти всегда идёт про алгоритм Шора. Технически, это разные утверждения: о скорости факторизации и – про алгоритм Шора. Что не так важно. Куда как более показательно, что никакой “квантовый компьютер” пока что вообще не решал задачу факторизации, что уж там говорить про то, чтобы решать эту задачу “кардинально быстрее”.
Без преувеличений и “раздувания хайпа” надо было бы сказать, что алгоритм Шора описывает теоретическое “квантовое преобразование”, которое позволяет снизить сложность факторизации, проводимой классическим компьютером, до полиномиальной. И тот же математический аппарат, который порождает данное “квантовое преобразование”, пока что успешно используется при интерпретации некоторых физических экспериментов. Не более того. О каком-то “кардинально быстрее” – и речи-то пока что не идёт. А вот “постквантовая стойкость” – это, в рамках термина, именно предполагаемая стойкость именно к “алгоритму Шора”.
Понятно, что стандартизованная постквантовая криптосистема может оказаться уязвимой для классического криптоанализа (и, скорее всего, так и выйдет). При этом, несмотря на прижившиеся штампы в СМИ, пока никто не продемонстрировал, как именно можно было бы реализовать алгоритм Шора с полиномиальной сложностью, что называется, в железе. Потому что те немногие эксперименты с числом 15 или чуть большим числом, на которые ссылаются много лет, в принципе не позволяют проверить ключевую часть реализации алгоритма – квантовое преобразование Фурье.
Тем не менее, пробовать построить квантовый компьютер хотя бы на 2^1024 состояний – это полезно.
Адрес записки: https://dxdt.ru/2024/08/15/13644/
Похожие записки:
- Зависания проекта California Forever
- Хитрости записи корней уравнений
- DNSSEC и особенности развития технологий
- Замена смысла текстовых предложений
- О визире и слоне
- Gofetch как уязвимость
- Apple и процессор радиоканала 5G
- Оптимизирующие компиляторы, микроконтроллер и ассемблер
- Автомобили-роботы из "обязательной" сети такси
- Палеография и падение тел
- Уровни сигнатур клиентских подключений
Кратко этот сайт характеризуется так: здесь можно узнать про технологический прогресс, Интернет, математику, криптографию, авиацию, компьютеры, авиационные компьютеры, вооружения, роботов, вооружение роботов, армии мира, астрономию, космические исследования. И иногда о чём-то ещё (
Комментарии читателей блога: 2
1. 20th August 2024, 16:14 // Читатель alex написал:
Каков ваш прогноз, – когда ждать качественного скачка в возможностях преодоления текущих криптосистем (не знаю, как технически грамотно сказать, но суть наверное понятна; и понятна же произвольность прогноза) ?
2. 20th August 2024, 20:00 // Александр Венедюхин:
Прогнозы тут сложно строить – область весьма “нечёткая”, а доказательства эвристические, в основном. Но вот что я бы предположил, так это то, что никаких универсальных квантовых компьютеров через десять лет мы ещё не увидим, хоть хайп и продолжится на этом направлении. Да и качественного скачка для имеющихся криптосистем, если говорить про что-то универсальное, в ближайшие годы тоже вряд ли стоит ожидать (однако тут ошибиться даже проще, чем с квантовыми компьютерами, на мой взгляд).
Зато вот классические атаки на предложенные NIST постквантовые криптосистемы – точно сильно улучшатся за эти же десять лет; вполне возможно, что что-то даже сломают на практике, и не исключено, что через те же десять лет (скорее – раньше) предложат и квантовые алгоритмы (теоретические), которые полностью, – но не менее теоретически, – сломают некоторые из тех криптосистем, что сейчас обозначены как постквантовые.
Написать комментарий