Золотой билет. P, NP и границы возможного - Лэнс Фортноу

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

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

Боб и Элис спорят, куда пойти ужинать. Бобу хочется в стейк-хаус, Элис – в рыбный ресторан. В конце концов на помощь призывают орла и решку. Боб подбрасывает монетку и накрывает ее ладонью. Элис ставит на орла. Боб открывает монетку… решка. Этим вечером Боб будет наслаждаться сочным стейком.

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

Простейший способ – положиться на случайное событие, исход которого станет известен всем. Например, договориться, что если последняя цифра промышленного индекса Доу-Джонса на закрытие дня окажется нечетной, то выбирать ресторан будет Боб, а если четной – то Элис. Правда, в субботу торги не ведутся, так что на выходные придется придумывать что-то другое.

В этом случае подойдет рассмотренная ранее схема шифрования с открытым ключом. Боб создает пару ключей, открытый и закрытый. Затем выбирает случайное число, к примеру – 69441251920931124, и шифрует его своим открытым ключом, который отсылает Элис вместе с шифровкой.

Элис выбирает «чет» или «нечет» и сообщает об этом Бобу. В ответ он отправляет ей секретный ключ. Расшифровав криптограмму, Элис узнает, что Боб загадал 69441251920931124. Если она выбрала «чет», то выиграла, а если «нечет» – выиграл Боб.

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

Бросать монетку – это как-то слишком просто. Что, если взять какую-нибудь более сложную игру?

Можно ли, к примеру, провести по телефону шахматную партию? Без проблем: игроки по очереди будут сообщать друг другу свой следующий ход, пользуясь принятыми в шахматах обозначениями.

Как насчет игры в кости, нарды или «Монополию»? Поверит ли Элис, что Боб не врет насчет выпавших очков? Безусловно – для этого лишь нужно будет утвердить протокол бросания костей, во многом совпадающий с протоколом бросания монетки.

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

В интернете сейчас очень много покерных сайтов, однако все они играют роль ведущего, так как сами тасуют карты и раздают их игрокам.

Можно ли провести игру в покер без сайта-посредника? Можно, конечно, – вот только протоколом бросания монетки тут уже не обойдешься. В семидесятых и восьмидесятых годах прошлого века для карточных игр с двумя и более игроками появилось множество хитрых криптографических схем, в которых были и открытые ключи, и закрытые, и даже двойное шифрование. Применялись эти схемы как по телефону, так и по сети.

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

Допустим, у Элис имеются конфиденциальные данные, над которыми требуется произвести некие вычисления, а Боб как раз предоставляет сервис облачных вычислений. Элис отправляет Бобу информацию, закодированную его открытым ключом. Боб расшифровывает данные, выполняет вычисления и отправляет Элис результат, закодированный ее открытым ключом. Если система шифрования достаточно надежна, то ни один злоумышленник не сумеет похитить секретную информацию. Схема работает – но лишь до тех пор, пока Элис доверяет Бобу. А что, если она захочет скрыть свои данные даже от него?

В этом случае помогут системы, называемые полностью гомоморфными. Протокол RSA устроен таким образом, что, умножив шифр одного числа (к примеру, числа 28) на шифр другого (к примеру, 45), мы в итоге получим шифр их произведения (т. е. числа 1260). Умножение чисел можно проводить без расшифровки, и исходные данные при этом знать не обязательно. Для сложения, однако, это правило не действует, и по кодам чисел 28 и 45 код числа 73 в системе RSA не получишь.

Умножение соответствует логическому «И», а сложение – логическому «ИЛИ». Вместо логических схем можно строить схемы из операций умножения и сложения, и такими схемами на самом деле реализуются очень многие вычисления. Полностью гомоморфная криптосистема позволяет не только умножать зашифрованные числа, но и складывать; обе операции можно проводить без расшифровки, и никакая дополнительная информация при этом не потребуется.

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

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