Квантова загроза: Яка криптографія вмирає, а яка виживає? (Або: Чому ZK-STARK захищені PQ?) Раніше я пояснював, як працює квантовий комп'ютер: Думайте про розв'язання проблем як про спробу втекти з лабіринту. Існує багато можливих шляхів, і потрібно перевірити кожен з них, поки не знайдете вихід. Так працює класичний (неквантовий) комп'ютер. Але закони квантової механіки дозволяють робити краще. Вони дозволяють системі (групі частинок) паралельно досліджувати *всі* різні шляхи в лабіринті. Шляхи, що ведуть до виходу, залишаються життєздатними, а ті, що ведуть у глухий кут, зникають. Потім всесвіт випадково обирає один із життєздатних шляхів, що залишилися (це та частина, яка не подобалася Ейнштейну, він казав: «Бог не грає в кості», але насправді це робить). Ось як QC вирішує задачі, на розв'язання яких класичному комп'ютеру знадобилося б мільйони років. Але існують види криптографічних примітивів, які можна зламати квантовим комп'ютером, і ті, що залишаються безпечними. Як це можливо? У попередньому поясненні я пропустив важливу частину: не всі лабіринти однакові. Є деякі лабіринти, де глухі кути зникають, залишаючи всесвіт лише з хорошим шляхом, що веде до виходу. Я називаю це «квантово-легкими лабіринтами», бо коли всесвіт вибирає шлях для такого лабіринту, це завжди буде шлях, що веде до виходу. Легко дістатися до кінця лабіринту означає легко зламатися. Однак у «квантово-складних лабіринтах» усі шляхи залишаються «живими», незалежно від того, чи заходять вони в глухий кут, чи до виходу. Для такого лабіринту квантовий комп'ютер не кращий за класичний. Коли Бог кидає кості і обирає шлях, усі шляхи — добрі й погані — однаково ймовірно з'являться. Отже, квантовий комп'ютер виконує аналог класичного комп'ютера, випадково перевіряючи один шлях у лабіринті. Тепер ви, мабуть, питаєте: Які лабіринти є квантово простими, а які — ні? ...