Несколько вступительных слов
Давайте представим мир, в котором квантовые компьютеры привычны не менее, чем новый айфон. Как говорят в более научных кругах: "достигнуто квантовое преимущество."
Квантовое преимущество - это порог, при достижении которого созданная нами квантовая система может выполнять операции, которые лучший из возможных классических компьютеров не может смоделировать за любое разумное время.
Не будем пока углубляться в такие понятия как "кубит", "квантовые вычисления", "суперпозиция", "запутанность" и "декогеренция". Это важные понятия, они будут расмотрены в дальнейших публикациях, но для понимания роли и потенциала пост-квантовой криптографии они необязательны. Определения в сносках можно пропустить без опасения потерять нить повествования.
Кубит - наименьшая единица информации в квантовых компьютерах. Аналог "бита" в теории информации. Разница в том, что "обычный" бит может находиться только в двух состояниях - 1 или 0. А кубит может также находится в третьем состоянии - "суперпозии" единицы и нуля.
Суперпозиция утверждает, что, подобно волнам в классической физике, вы можете сложить два или более квантовых состояния, и результатом будет другое действительное квантовое состояние. И наоборот, каждое квантовое состояние можно представить как сумму двух или более других отдельных состояний. Эта суперпозиция кубитов придает квантовым компьютерам присущий им параллелизм, позволяя им обрабатывать миллионы операций одновременно.
Квантовая запутанность возникает, когда две системы связаны настолько тесно, что знание об одной из них дает вам немедленное знание о другой, независимо от того, насколько далеко они находятся друг от друга. Квантовые процессоры позволяют делать выводы об одной частице, измеряя другую. Например, с их помощью можно определить, что если один кубит вращается вверх, то другой всегда будет вращаться вниз, и наоборот. Квантовая запутанность позволяет квантовым компьютерам быстрее решать сложные задачи. Когда квантовое состояние измеряется, волновая функция схлопывается, и вы измеряете состояние как ноль или единицу. В этом известном или детерминированном состоянии кубит действует как классический бит. Запутанность – это способность кубитов соотносить свое состояние с другими кубитами.
Декогеренция – это потеря квантового состояния в кубите. Факторы окружающей среды, такие как радиация, могут вызвать коллапс квантового состояния кубитов. Большой инженерной задачей при создании квантового компьютера является разработка различных функций, которые пытаются задержать декогеренцию состояния, например, создание специальных структур, экранирующих кубиты от внешних полей.
Напомним также, что вся современная криптография базируется на двух математических действиях - факторизации чисел и вычисления дискретного логарифма.
Это достаточно сложные операции для обычных компьютеров. В марте 1994 года командой математиков под руководством Ленстры было разложено на множители 129-разрядное (428-битовое) число. Вычисления выполнялись добровольцами в Интернете. В течение восьми месяцев трудились 600 человек и 1600 компьютеров.
Как видно, были задействованы немалые ресурсы, и это для факторизации только одного числа, а ведь в каждой криптосистеме RSA будут свои пары чисел. Поэтому криптосистемы на основе факторизации считаются достаточно устойчивыми ко взлому.
Алгоритм Шора
В 1994 году произошло ещё одно событие - американский математик Питер Шор разработал квантовый алгоритм для целочисленной факторизации. Алгоритм использует метод определения периода функции и может быть настроен для решения задач вычисления дискретного логарифма в конечной группе или группе точек эллиптических кривых. Этот квантовый алгоритм теоретически позволит эффективно (за время, лишь ненамного превосходящее требующееся для зашифрования) взламывать большинство используемых сейчас асимметричных криптографических схем (RSA, DSA, EdDSA, ГОСТ Р 34.10-2012 и других).
Получается, что с момента создания квантового компьютера достаточной мощности, самые распространённые криптосистемы перестанут быть чем-то большим, чем интересными математическими объектами.
Пост-квантовая криптография
Это криптография, которая будет актуальна (позволим себе это слово вместо сухого "стойкости ко взлому" или "дороговизна поддержки") в мире доступных квантовых вычислений. Очевидно, что криптосистемы в таком мире не должны быть основаны на факторизации. Сейчас существует несколько таких систем, но в основном будет расмотрена т.н. "криптография на решётках" (англ. Lattice-based cryptography)
На этой точке в повествовании пока остановимся.
Вопросы приветствуются 🙂