📚 Hub Books: Онлайн-чтение книгДомашняяЗолотой билет. P, NP и границы возможного - Лэнс Фортноу

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

Шрифт:

-
+

Интервал:

-
+
1 ... 32 33 34 35 36 37 38 39 40 ... 46
Перейти на страницу:

Равенство P = NP многое упрощает, однако криптографам оно может принести лишь головную боль.

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

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

Боб пожертвовал обедом, чтобы добить судоку из последнего номера газеты.

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

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

Золотой билет. P, NP и границы возможного

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

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

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

Золотой билет. P, NP и границы возможного

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

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

Золотой билет. P, NP и границы возможного

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

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

Золотой билет. P, NP и границы возможного

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

Золотой билет. P, NP и границы возможного

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

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

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

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

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

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

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

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

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

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

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

Золотой билет. P, NP и границы возможного

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

Золотой билет. P, NP и границы возможного

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

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

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

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

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

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

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

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

1 ... 32 33 34 35 36 37 38 39 40 ... 46
Перейти на страницу:

Комментарии

Обратите внимание, что комментарий должен быть не короче 20 символов. Покажите уважение к себе и другим пользователям!

Никто еще не прокомментировал. Хотите быть первым, кто выскажется?