Квантовая угроза: какая криптография умирает, а какая выживает? (Или: Почему ZK-STARKs являются PQ-безопасными?) Ранее я объяснял, как работает квантовый компьютер: Представьте себе решение проблемы как попытку выбраться из лабиринта. Существует множество возможных путей, и вам нужно проверить каждый из них, пока вы не найдете выход. Вот как работает классический (неквантовый) компьютер. Но законы квантовой механики позволяют делать лучше. Они позволяют системе (группе частиц) исследовать параллельно *все* разные пути в лабиринте. Пути, которые ведут к выходу, остаются жизнеспособными, в то время как те, что ведут в тупик, исчезают. Затем вселенная случайным образом выбирает один из оставшихся жизнеспособных путей (это та часть, которая не нравилась Эйнштейну, который говорил: "Бог не играет в кости", хотя на самом деле он это делает). Вот как квантовый компьютер решает проблемы, на решение которых классическому компьютеру потребовались бы миллионы лет. Но есть виды криптографических примитивов, которые могут быть сломаны квантовым компьютером, и те, которые остаются в безопасности. Как это возможно? В моем предыдущем объяснении я упустил важную часть: не все лабиринты одинаковы. Есть некоторые лабиринты, в которых пути с тупиками исчезают, оставляя вселенной только хороший путь, который ведет к выходу. Я называю эти "квантово-легкими лабиринтами", потому что когда вселенная выбирает путь для такого лабиринта, это всегда будет путь, который ведет к выходу. Легко добраться до конца лабиринта означает легко сломать его. Однако в "квантово-сложных лабиринтах" все пути остаются "живыми", независимо от того, ведут ли они в тупик или к выходу. Для такого лабиринта квантовый компьютер не лучше классического компьютера. Когда Бог бросает кости и выбирает путь, все пути – хорошие и плохие – имеют одинаковую вероятность появиться. Таким образом, квантовый компьютер делает аналог классического компьютера, случайно проверяя один путь в лабиринте. Теперь вы, вероятно, спрашиваете: Какие лабиринты являются квантово-легкими, а какие нет? ...