Физик Алексей Федоров о будущем гибридной криптографии, предпосылках возникновения квантового компьютера и задаче факторизации.

Современное общество является информационным. То есть практически каждое действие, которое мы совершаем в нашей жизни, очень тесно связано с информационными технологиями, то есть процессом создания, обработки, передачи информации. И поэтому очень важным является вопрос ее защиты.

Мы стали за последнее время свидетелями уникального прогресса в области развития вычислительных технологий. С каждым годом наши вычислительные устройства становятся все меньше и при этом гораздо более эффективными. Эта зависимость между условно ростом вычислительной мощности устройств и временем выражается законом Мура. Он на самом деле говорит о том, насколько уменьшается, насколько миниатюризируется элементная база современных классических компьютеров, то есть транзисторов. Однако у этого закона есть какие-то фундаментальные ограничения. Например, если закон Мура будет продолжаться дальше, то к 2020 году нам необходимо для поддержания этого тренда строить транзисторы размером с один атом и, конечно, уже в таком компьютере, в котором бы роль транзистора играли одиночные квантовые объекты, в нем доминировали бы свойства квантовой механики, а этот компьютер уже бы подчинялся законам не классической физики, а квантовой.

Оказывается, что в силу ряда феноменов квантовой физики устройство, которое бы работало на таком принципе, на принципах квантовой механики, на принципах квантовой физики, оказывается чрезвычайно эффективным при решении некоторых специфических классов задач. Причем очень интересно, как возникала концепция квантового компьютера.

С одной стороны, было интересно понять, какие ограничения вообще квантовая механика, помимо, например, размерных, накладывает на развитие классических компьютеров. Скажем, какое минимальное количество теплоты выделяется в процессе реализации одной элементарной операции в компьютере. И другие вопросы, с этим связанные. Второй вопрос был связан с тем, что есть определенные классы задач, которые, несмотря на то что компьютеры вроде как развиваются, решать очень тяжело. Например, есть некоторые классы алгоритмических задач и некоторые задачи, связанные с моделированием сложных физических материалов. Они даже сейчас на больших суперкомпьютерах требуют довольно много времени.

И кроме того, было другое интересное направление. Оно было связано с тем, чтобы понять, что будет, если соединить очень хорошо развитую на тот момент классическую теорию информации с квантовой физикой и получить так называемую квантовую теорию информации.

И когда все эти тренды сошлись вместе, начали возникать новые интересные вопросы. Например, дают ли выигрыш в чем-то по сравнению с классическим компьютером такие машины, которые оперируют за счет принципов квантовой физики, в которых информация кодируется в квантовое состояние, а алгоритмы вычислений реализуются при помощи каких-то квантовых операций? И достаточно быстро было обнаружено, что дают. Но первая задача, на которой это было показано, была достаточно игрушечная. Есть такой алгоритм Дойча, показывающий, что квантовый компьютер позволяет быстрее обнаружить, является ли функция константной или сбалансированной. Константной называется функция, которая вне зависимости от входного значения всегда выдает один и тот же результат, а сбалансированной — если она дает с вероятностью одна вторая либо ноль, либо единицу.

И оказалось, что такой задаче в том, чтобы проверить, заданная функция является константной или сбалансированной, квантовый компьютер дает ускорение. Он позволяет это сделать быстрее, чем классический компьютер. Такая задача кажется далекой от реальности, и тем не менее она спровоцировала большой интерес вообще к теме того, насколько квантовые компьютеры и квантовые алгоритмы могут быть эффективнее классических. Затем появилась еще одна задача, которая показала, что квантовый алгоритм может быстрее обнаруживать период заданной функции. Казалось бы, тоже достаточно абстрактная задача. Но тем не менее именно она, наверное, вдохновила Питера Шора на создание алгоритма, который назван в его честь, для решения задачи факторизации, дискретного логарифмирования. Задача факторизации достаточно интересна. Когда у вас есть большое число и вам нужно сказать, из каких простых множителей оно состоит. Особенность этой задачи состоит в том, что обратная к ней, то есть перемножить два простых числа, очень простая. Мы можем это сделать условно даже без калькулятора. А сказать, из каких простых множителей состоит заданное достаточно большое число, из каких простых множителей оно состоит, — это сложно.

И интерес к тому, что квантовый компьютер дает ускорение в этой задаче, был связан с тем, что задача факторизации, дискретного логарифмирования на самом деле лежит в основе того, что называется криптографией с открытым ключом, или асимметричной криптографией. Это тот вид криптографии, который повсеместно используется нами в мессенджерах, в электронно-цифровых подписях, в достаточно широком диапазоне информационных приложений. И интересен тот факт, что если построить квантовый компьютер, то та инфраструктура, которую мы с трудом много лет выстраивали, основывающаяся на криптографии с открытым ключом, будет разрушена. Такое разрушение возникает именно за счет того, что классы задач, на которых эта асимметричная криптография на данный момент основана, связаны с тем, в чем квантовый компьютер дает существенное ускорение.

Нужно сразу оговориться, что квантовый компьютер дает ускорение, но неуниверсальное. То есть он решает лучше некоторые заранее определенные классы задач. Но не все на свете задачи. На данный момент мы знаем только очень узкий класс задач, в котором квантовый компьютер дает существенное ускорение. Конечно, к задаче дискретного логарифмирования и факторизации было приковано большое внимание, потому что фактически от надежности этих криптографических алгоритмов зависит то, насколько хорошо мы можем защищать информацию.

В этот момент возникает вопрос: а что мы можем делать? Что будет с нами, если квантовый компьютер возникнет? На самом деле тут есть два возможных варианта решения этой проблемы. Первый из них — и это интересно — был предложен еще до того, как стало очевидно, что квантовый компьютер дает ускорение задаче факторизации. Это так называемая квантовая криптография, квантовое распределение ключа. Это метод для выработки криптографических ключей, ключей для шифрования, основывающийся на кодировании информации и их передаче при помощи одиночных квантовых состояний, например при помощи одиночных фотонов.

Этот метод, как было показано, дает возможность двум удаленным пользователям распределить ключ, который они могут использовать для шифрования в так называемом режиме одноразовых блокнотов. Режим одноразовых блокнотов — это алгоритм шифрования, при котором размер ключа для шифрования совпадает с размером сообщения, которое вы хотите передать. Ключ достаточно случаен и может использоваться только один раз. Как было показано Шенноном и независимо Котельниковым, такая система абсолютно стойкая. То есть такую систему невозможно взломать, потому что, какими бы вычислительными ресурсами ни обладал злоумышленник, из-за того, что ключ одноразовый и случайный, злоумышленник не может получить никакой информации о том, какое сообщение передано. И эти системы называются абсолютно стойкими.

И в принципе возможным решением в эпоху квантовых компьютеров являлась бы замена всей существующей инфраструктуры на то, чтобы использовать квантовую криптографию и такие средства шифрования в виде одноразовых блокнотов. К сожалению, на данный момент это реализовать достаточно трудно, потому что технология квантовой криптографии, несмотря на то что достигла коммерческого уровня и ее можно купить, она разрабатывается, есть конкретные устройства, конкретные девайсы, у нее есть определенные ограничения (например, ограничения в скорости генерации ключей). Для того чтобы шифровать, например, весь трафик в режиме одноразовых блокнотов, просто потребуются очень высокие скорости генерации ключей, а для этого еще очень много интересных технических задач нужно решить.

Кроме того, есть ограничения, связанные с расстоянием. Дело в том, что если мы передаем информацию о ключе при помощи одиночных фотонов, то расстояние, на которое мы это можем делать, существенно ограничено. Мировые рекорды в лабораториях — это сотни километров. Это в идеальных условиях. А если мы говорим о каких-то реальных условиях, то это обычно достаточно ограниченные расстояния. Для того чтобы сделать эту технологию глобальной, можно, например, идти по пути китайцев, которые недавно запустили спутник, для того чтобы отрабатывать эту технологию в режиме «Земля — спутник — Земля» и передавать таким образом ключи.

И тем не менее у квантовой криптографии много ограничений. Поэтому возникает вопрос: неужели это единственное решение в постквантовую эпоху, как ее часто называют, в эпоху информационной безопасности с квантовым компьютером? Ответ: да, это единственное решение, которое гарантирует безусловную абсолютную стойкость. То есть если информация должна быть надежна очень длительное время и мы не хотим в этом смысле иметь никаких катаклизмов, то необходимо уже сейчас начинать внедрять квантовую криптографию.

И тем не менее есть другой ответ — это называется постквантовой криптографией. Название немного неочевидное. То есть, несмотря на то что она называется постквантовой, от квантовой физики там нет практически ничего. Это просто новый класс математических алгоритмов, основанных на задачах, которые квантовый компьютер не решает сильно быстрее, чем классический. Как я уже сказал, квантовый компьютер не является панацеей или универсальным средством. На данный момент известно, что в довольно специфических классах задач он дает существенное ускорение. Однако если мы, например, построим криптографию на задачах, в которых квантовый компьютер не дает существенного ускорения, то это способ нам защититься достаточно эффективно просто при помощи новой математики.

У этого способа тоже есть свои трудности, потому что математика, стоящая за такими алгоритмами, достаточно сложная и ее необходимо изучать. И достаточно трудно сделать эти алгоритмы эффективными, например, для постквантовой выработки ключей или постквантовой электронно-цифровой подписи. Поэтому здесь постоянно есть тренд, постоянно есть такая борьба за то, чтобы, с одной стороны, сохранить защищенность этих алгоритмов, с другой стороны, сделать их эффективными и достаточно быстрыми, для того чтобы их могли реализовывать современные компьютеры.

Однако есть два решения, и, кажется, что в новом мире, в мире XXI века, в котором уже могут появиться достаточно большие квантовые компьютеры, чтобы взламывать классическую криптографию, мир будет гибридный. В каких-то приложениях, которые требуют очень важной и надежной защиты, чтобы, например, защитить ДНК человека — а эта информация должна быть защищена на достаточно большом масштабе времени, на всем периоде жизни человека, — имеет смысл использовать квантовую криптографию, потому что она обеспечит ультранадежную защиту, которая не связана с вычислительными характеристиками злоумышленника. Она полностью базируется на том, что законы квантовой физики правильные и они работают. А для каких-то приложений, для которых квантовый компьютер сейчас представляет угрозу, например для инфраструктуры электронно-цифровой подписи, мы можем перейти на постквантовые алгоритмы и, надеюсь, сделать их достаточно эффективными, чтобы они были внедрены в жизнь.

Алексей Федоров
PhD in Theoretical Physics Университет Париж-Сакле, старший научный сотрудник Российского Квантового Центра
ПостНаука