Алиса у Боба украла бит

Еще один, последний протокол…

В. Коркия, "Черный человек"

Предлагаю вниманию читателей популярное изложение работы Чау (H. F. Chau) и Ху-Квань-Ло (Hoi-Kwang Lo). Первый автор - из университета Гонконга, второй работает в Великобритании, в лабораториях "Хьюлетт Паккард". Статья была написана для спец. выпуска по квантовым вычислениям авторитетного физического журнала "Fortschritte der Physik" и положена на сервер в Лос-Аламосе 26 сентября нынешнего года (e-print quant-ph/9709053). Называется она: "Как нарушить обещание при помощи квантового компьютера". Многие из используемых ниже понятий и терминов поясняются в беседе с Михаилом Вялым (см. предыдущую статью).

Главные действующие лица - Алиса и Боб.

Алиса хочет принять - притом немедленно - некое решение, важное для обоих. А еще она хочет, чтобы Боб в течение определенного срока не знал, что именно она решила. Боб согласен на это, но при одном условии: он должен быть твердо уверен, что решение принято и Алиса уже не сможет его изменить. Для полного спокойствия он желает иметь возможность проверить это в момент объявления решения (скажем, через год). Последняя деталь: решение закодировано значением одного-единственного бита - 0 или 1.

Как решались подобные вопросы в далеком прошлом? Алиса могла записать свой бит на листе бумаги, запереть лист в шкатулку и отдать ее Бобу, оставив ключ у себя. В момент объявления решения она вручала Бобу ключ, шкатулка торжественно вскрывалась, и все убеждались в том, что Алиса сдержала слово. Но, увы, техническая сторона такой схемы не слишком надежна: что если хитроумный Боб сумеет подобрать ключ, или ловкая Алиса как-нибудь при случае незаметно подменит записку в шкатулке?..

Решение этой задачи (будем называть ее задачей ПБ, от "передача бита на хранение", в оригинале - bit commitment) играет очень большую роль в криптографии. Причем именно в "мирной" криптографии - например, при обеспечении секретности информации в процессе голосования. Другой животрепещущий вопрос, имеющий прямое отношение к задаче ПБ: бывшие муж и жена желают подбросить монетку, чтобы решить, кому достанется дом. Встречаться ради такого пустяка они категорически не согласны, но столь же категорически друг другу не доверяют. Более того, никакой третьей стороне подбрасывание монетки они тоже доверить не хотят. Как им быть?¹

Мотивировав таким образом важность задачи ПБ, авторы рассматривают сначала современную (классическую) схему ее решения. Введем фундаментальное для криптографии понятие односторонней (необратимой) функции (one-way function) - это такая функция f(x), что для любого допустимого x легко вычислить y=f(x), а вот вычислить x по данному y - "невозможно" (то есть на это нужно совершенно неприемлемое время). Пример - показательная функция в поле вычетов. Обратная к ней - дискретный логарифм, о котором много говорилось в беседе с М. Вялым. Между прочим, авторы отмечают, что на сегодняшний день нет ни одного (!) строго обоснованного примера односторонней функции, и значительная часть практической криптографии держится просто на вере (довольно странный термин в этом контексте) в "односторонность" той или иной функции.

Так вот, классическая схема для задачи ПБ имеет следующий вид. Выбирается некоторая односторонняя функция f(x) - ее знают и Боб, и Алиса. После этого:

1. Алиса принимает решение, чему будет равен ее бит b - нулю или единице.
2. Если b=0, Алиса случайным образом выбирает четное целое число x, в противном случае - нечетное. После этого она вычисляет y=f(x) и посылает Бобу значение y.
3. Когда приходит время объявить свое решение, Алиса посылает Бобу x.
4. Чтобы убедиться, что его не обманули, Боб проверяет, что y действительно равен f(x). После этого он определяет четность x и узнает, каким было значение b.

В данной ситуации Боб с самого начала располагает полной информацией о решении Алисы. Но он не может ею воспользоваться - если только некстати не научится обращать одностороннюю функцию или делать квантовые компьютеры. Алиса же после отсылки икса имеет мало шансов на что-либо повлиять.

Как теперь известно, многие классические односторонние функции при наличии квантового компьютера перестают быть таковыми. Поэтому описанная выше схема при появлении квантовых компьютеров рушится. С другой стороны, довольно давно рассматриваются чисто квантовые схемы (протоколы) для задачи ПБ. Так вот, утверждается, что в квантовом варианте как раз Алиса, имея квантовый компьютер, может обмануть Боба - причем даже в том случае, если у Боба тоже есть такой компьютер!

Далее формулируется наиболее общая квантовая схема ПБ:

1. Алиса и Боб переводят имеющиеся у них квантовые частицы в предписанное состояние.
2. Алиса, в соответствии с выбранным ею значением бита, применяет некоторое унитарное преобразование к своим частицам. После этого она отсылает какое-то количество своих частиц Бобу.
3. Получив от Алисы ее частицы, Боб применяет некоторое унитарное преобразование к своим частицам. После этого он отсылает несколько своих частиц Алисе.
4. Шаги 2 и 3 повторяются несколько раз.
5. В момент объявления решения Алиса отсылает все свои частицы Бобу.
6. Получив от Алисы частицы, Боб проводит измерение объединенной системы частиц, чтобы определить, не обманули ли его.

В доказательство общности этой схемы авторы приводят ряд аргументов, которые мы опускаем. Разъясняется также, почему эта схема включает уже описанные в литературе схемы ПБ. Нам же сейчас важно понять общую идею. Авторы объясняют ее так: исходное состояние алисиных частиц перед отсылкой их Бобу - это "и есть загаданный ею бит". Все манипуляции с унитарными преобразованиями в пунктах 2-4 эквивалентны одному унитарному преобразованию квантовой системы, состоящей из частиц Алисы, частиц Боба и канала связи. Это преобразование известно обеим сторонам. Однако Боб до последнего момента имеет доступ только к части полного вектора состояния системы. В момент объявления решения Алиса предоставляет ему доступ ко всему вектору - то есть к результату действия оператора, определяемого описанным выше протоколом, на неизвестное (Бобу) начальное состояние. Зная оператор и результат, он может определить начальное состояние, убедившись тем самым в честности Алисы.

Итак, секретность основана на том, что и Боб, и Алиса до объявления решения не могут даже посмотреть, что же за частицы у них в данный момент "на руках". Ведь тогда это сложное, сцепленное состояние всей системы разрушится, превратившись в одно из наблюдаемых чистых состояний, - но по нему невозможно будет узнать исходное состояние всей системы. А это означает, что алисин бит так и останется тайной. Грубо говоря, шкатулка, при попытке к ней прикоснуться, взрывается. Поэтому измерение производится только один раз, в самом конце всей игры, когда у Боба достаточно частиц, чтобы по измерениям конечного состояния определить исходное.

Далее предъявляется довольно простой, чисто математический факт: запись произвольного состояния объединения двух систем в некоем специальном виде. И вот из этой специальной записи (в которой состояния каждой из подсистем "максимально расцеплены") очевидно, что у Алисы есть возможность непосредственно перед объявлением решения применить - только к своим частицам! - такой унитарный оператор, что несчастный Боб в результате своих измерений получит в ответе то, что нужно ей, Алисе.

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

Она всегда выбирает нулевое значение бита и честно выполняет все дальнейшие манипуляции вплоть до объявления решения. В момент объявления решения Алиса оценивает, какое значение ей выгоднее - ноль или единица. Если ноль, она спокойно и честно завершает процедуру. Если единица, то она перед отправкой Бобу быстренько корректирует имеющиеся у нее на руках частицы так, чтобы последующие шаги протокола привели Боба к выводу: с самого начала была выбрана единица.

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

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

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

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

¹ Тем, кто хочет больше узнать о таких вещах, рекомендую увлекательную книгу А. Саломаа "Криптография с открытым ключом" (М., "Мир", 1996 год).