Золотой билет - Лэнс Фотноу

«У них тут ошибка. Это решить невозможно!» – восклицает он, совершенно выбившись из сил. На крики приходит его коллега Элис; взглянув на судоку, она видит ту самую головоломку, которую утром решила в метро. Боб зря ругается. На рисунке ниже вы видите решение Элис.

Боб вот-вот сдастся, и Элис хочется его поддержать. Она говорит, что решила задачу, но он ей, конечно, не верит. Он ужасно расстроится, когда увидит в завтрашней газете ответ, так что нужно обязательно убедить его подумать еще. Показать свое решение значит испортить Бобу все удовольствие от процесса; но как доказать, что задача решается, не давая при этом никаких подсказок?

Рис. 8.7. Решение судоку с нулевым разглашением

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

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

Рис. 8.8. Новый порядок цифр

С помощью полученной таблицы Элис шифрует свое решение, заменяя 1 на 2, 9 на 3, и т. д., и рисует его на большом листе бумаги. Вот что у нее выходит:

Рис. 8.9. Зашифрованное решение

Дальше Элис аккуратно режет сетку с решением на маленькие квадратики по одной цифре в каждом. Всего квадратиков получается 81. Каждый квадратик она прячет в маленький пакетик и кладет в соответствующую ячейку нарисованной на другом листе пустой сетки.

Рис. 8.10. Решение спрятано

Рис. 8.11. Открытая строка

В левом верхнем пакетике лежит цифра 2, справа от него – цифра 3, и так далее.

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

• открыть все пакетики в одной из строк;

• открыть все пакетики в одном из столбцов;

• открыть все пакетики в одном из девяти блоков 3 × 3;

• открыть все пакетики, расположенные на тех же позициях, что и заданные цифры исходной головоломки.

Допустим, Боб решил открыть третью строку. Что он там увидит?

Если бы в строке оказалось две одинаковых цифры, это означало бы, что Элис наврала. Но поскольку решение у нее действительно есть, и она четко объяснила Бобу, что сделала с пакетиками, Боб видит все различные цифры от 1 до 9 в случайном порядке. Тест пройден!

Если Боб решит открыть столбец или блок 3 × 3, результат будет точно таким же.

Теперь предположим, что он выберет последний вариант – «открыть все пакетики, расположенные на тех же позициях, что и заданные цифры исходной головоломки». Открыв пакетики, Боб видит такую картину.

Рис. 8.12. Открытые позиции соответствуют заданным цифрам

Рис. 8.13. Новый порядок цифр

Это единственный случай, когда Боб получает от Элис еще и таблицу кодировки, при помощи которой он проверит, соответствуют ли открытые цифры тем, что были указаны в задаче изначально. Например, согласно схеме, цифра 9 должна была превратиться в цифру 3… так и есть!

Если Элис и правда решила задачу и четко следовала правилам, она пройдет любую проверку. А что же Боб? Получит ли он хоть какую-нибудь подсказку, когда откроет строку, столбец или блок 3 × 3? Исключено: перед ним будут лишь цифры от 1 до 9, расположенные в случайном порядке.

Последний вариант даст ему перестановку цифр, при помощи которой было зашифровано решение. Но что он при этом узнает? Ничего.

Другое дело, если Элис наврала: один из тестов обязательно провалится, и она ничего не сможет с этим поделать. Когда Боб выбирает тест наугад, вероятность попасться на вранье составляет одну двадцать восьмую, или примерно 3,57 %. Не так уж и рискованно, правда? Однако если Элис и Боб проведут 83 эксперимента подряд и при этом будут каждый раз менять схему кодировки, вероятность провалить один из тестов возрастет до 95 %.

Боб убедился, что Элис действительно решила судоку, а ей при этом удалось соблюсти принцип «нулевого разглашения»: о решении Боб знает только то, что оно существует. Эта мысль будет греть его, когда он вернется к головоломке, но справляться ему придется исключительно своими силами.

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

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

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

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

Криптография в играх

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

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

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

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

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

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