Текст книги "Квантовые вычисления со времен Демокрита"

Загадки

1. Вы с приятелем хотите бросать монетку, но единственная монетка, которая у вас имеется, явно неправильная: на ней выпадает орел с некоторой фиксированной, но неизвестной вероятностью p. Сможете ли вы с помощью этой монетки смоделировать бросание настоящей честной монетки? (Я имею в виду, идеально честной, а не просто приблизительно честной.)

2. n человек встали в круг. У каждого из них на голове либо красная, либо синяя шляпа, полученные случайно, равномерно и независимо. Каждый может видеть шляпы всех остальных, но не свою собственную. Эти люди хотят устроить голосование на тему того, является ли число красных шляп четным или нечетным. Все голосуют одновременно, так что голоса друг на друга не влияют. Какова максимальная вероятность, с которой люди могут выиграть в этой игре? (Под «выиграть» я подразумеваю, что результат голосования будет соответствовать истине.) Считать для простоты, что число n нечетное.

8. Крипто

Ответы на загадки из главы 7

Загадка 1. Нам дана неправильная монетка, при бросании которой орел выпадает с вероятностью p. При помощи этой монетки нужно «построить» механизм моделирования честной монетки.

Решение. Нужное нам решение – это так называемый фокус фон Неймана: бросаем монетку дважды, интерпретируя ОР как орла, а РО как решку. (Если выпадут ОО или РР, пробуем еще раз.) Теперь «орел» и «решка» равновероятны, поскольку в любом заданном испытании то и другое возникает с вероятностью p (1 – p). Следовательно, такая модель монетки работает честно (при условии, что выпадает ОР или РО).

Загадка 2. n человек сидят по кругу. У каждого из них на голове либо красная, либо синяя шляпа, полученные случайно, равномерно и независимо. Каждый может видеть шляпы всех остальных, но не свою собственную. Основываясь только на том, что видит, каждый высказывает свое мнение: является число красных шляп нечетным или нет. Существует ли схема, при которой результат голосования будет верным с вероятностью, большей 1/2?

Решение. Каждый человек определяется с голосованием так: если число видимых ему синих шляп больше, чем число видимых красных шляп, он голосует в соответствии с четностью числа видимых красных шляп. В противном случае – голосует наоборот. Если число красных шляп отличается от числа синих на две или больше, то эта схема срабатывает точно. Если нет, схема может и не сработать. Однако вероятность того, что число красных шляп отличается от числа синих меньше чем на 2, невелика – O (1/√N).

Крипто

Криптография уже более 3000 лет играет заметную роль в истории человечества. Немало войн было выиграно или проиграно благодаря хитроумности или глупости криптосистем. Если вам кажется, что я преувеличиваю, почитайте «Взломщиков кодов» Дэвида Кана[41]41
  D. Kahn, The Codebreakers (New York: Scribner, 1996).


[Закрыть] – и не забывайте, что эта книга написана еще до того, как стала известна крупнейшая криптографическая история всех времен: взлом нацистского военно-морского шифра во Второй мировой войне командой с участием Алана Тьюринга.

И все же, хотя криптография тысячелетиями влияла на человеческие дела, события последних тридцати лет полностью – да, именно полностью! – изменили наши представления о ней. Если нанести на шкалу времени основные математические открытия в области криптографии, то вы увидите несколько отметок в античности, несколько, может быть, от Средневековья до XIX века, одно в 1920-е гг. (одноразовые ключи), еще несколько во время и около Второй мировой войны – а затем, после рождения теории вычислительной сложности в 1970-е гг., они пойдут сплошным потоком, одно за одним…

Наше путешествие по истории криптографии начнется со знаменитого и жалкого «шифра Цезаря», использовавшегося в Римской империи. В нем обычное послание превращается в шифрованный текст простым добавлением 3 к номеру каждой буквы (с замыканием алфавита в кольцо, так что после Z снова идет A). Таким образом, D превращается в G, Y становится B, а DEMOCRITUS выглядит как GHPRFULWXV. Были и более сложные варианты шифра Цезаря (он же шифр замены), но при наличии достаточного количества зашифрованного текста все их нетрудно взломать при помощи (например) частотного анализа присутствия букв в зашифрованном тексте. Правда, это не очень-то останавливает людей в использовании подобных вещей! Представьте себе, совсем недавно, в 2006 г., глава сицилийской мафии[42]42
  См.: http://en.wikipedia.org/wiki/Pizzino.


[Закрыть] был наконец-то пойман после 40 лет охоты потому, что использовал шифр Цезаря – его оригинальную версию – для отправки записок своим подчиненным!

Может ли существовать криптосистема, безопасная с точки зрения теории информации, то есть доказуемо надежная вне зависимости от того, сколько компьютерного времени есть у перехватившей сообщение стороны на его взлом? Поразительно (если вы никогда прежде об этом не слышали), но ответ на этот вопрос оказывается положительным, и еще более поразительно, что такая система была открыта только в 1920-е гг. По причинам, о которых мы поговорим чуть позже, прототип системы, безопасной согласно теории информации, называется одноразовым ключом. Идея проста: текстовое сообщение представляется в виде двоичной строки p, над которой производится операция исключающего «или» (xor) со случайной двоичной ключевой строкой k той же длины. То есть зашифрованный текст c равен p ⊕ k, где знаком ⊕ обозначается побитовое сложение по модулю 2.

Получатель (которому известна k) может расшифровать шифрованное послание при помощи еще одной операции исключающего «или»:

c ⊕ k = p ⊕ k ⊕ k = p.

Для стороны, перехватившей послание и не знающей k, зашифрованный текст – это просто строка случайных бит, поскольку результатом операции исключающего «или» между произвольной строкой (посланием) и случайной строкой является еще одна случайная строка. Проблема с одноразовыми ключами, конечно, в том, что и отправителю, и получателю должен быть известен ключ, не менее длинный, чем само послание. Более того, если один и тот же ключ будет использован для шифрования двух или более посланий, то криптосистема перестанет быть безопасной с точки зрения теории информации. (Отсюда и название – «одноразовый ключ».) Чтобы понять, почему, предположим, что два текста p₁ и p₂ шифруются при помощи одного и того же ключа k и дают в результате шифрованные тексты c₁ и c₂ соответственно. Тогда мы имеем

c₁ ⊕ c₂ = p₁ ⊕ k ⊕ p₂ ⊕ k = p₁ ⊕ p₂,

и, следовательно, перехвативший может получить строку p1 ⊕ p2. Само по себе это может оказаться, а может и не оказаться полезным, но это, по крайней мере, позволяет противнику получить какую-то информацию об исходном тексте. Но ведь это всего лишь математическая диковинка, не правда ли? Ну, в 1940-е годы Советы проявили небрежность и использовали повторно некоторые из своих одноразовых ключей. В результате Агентство национальной безопасности АНБ в рамках проекта VENONA сумело восстановить некоторые (хотя и не все) зашифрованные таким способом сообщения. Кажется, именно так были пойманы Юлиус и Этель Розенберги.

В 1940-е гг. Клод Шеннон доказал, что теоретически надежная криптография требует, чтобы у отправителя и получателя был общий ключ длиной не менее длины того сообщения, которое они хотят передать. Как почти все результаты Шеннона, задним числом этот вывод кажется тривиальным. (Хорошо начинать с самого начала!) Вот его доказательство: если имеются шифрованный текст и ключ, лучше, чтобы исходный текст восстанавливался по этим данным однозначно. Иными словами, при любом фиксированном ключе функции, преобразующей исходный текст в шифрованный, лучше быть инъективной. Но из этого сразу же следует, что для заданного шифрованного текста c число исходных текстов, из которых в принципе мог получиться c, не превышает числа ключей. Иными словами, если возможных ключей меньше, чем исходных текстов, то противник сможет исключить некоторые из исходных текстов – те, из которых c не получится ни при каком значении ключа. Поэтому наша криптосистема не будет совершенно надежной. Следовательно, если мы хотим совершенной надежности, нужно иметь по крайней мере столько же ключей, как и исходных текстов – или, что эквивалентно, ключ должен содержать по крайней мере столько же бит, сколько содержится в исходном тексте.

Я уже упоминал, что передавать друг другу и хранить ключи громадной длины, как правило, непрактично, – даже КГБ не удавалось проделывать это без сучка без задоринки! Потому нам нужна криптосистема, которая позволяет обходиться менее длинными ключами. Конечно, результат Шеннона подразумевает, что такая система не будет надежной с точки зрения теории информации. Но что, если мы немного снизим требования? В частности, что, если мы будем считать, что перехвативший ограничен полиномиальным временем? Этот вопрос естественным образом переводит нас к нашей следующей теме…

Генераторы псевдослучайных последовательностей

Как я упоминал в предыдущей главе, генератор псевдослучайной последовательности PRG – это, по существу, функция, которая принимает на вход короткую, по-настоящему случайную строку и выдает на выходе длинную, кажущуюся случайной строку. В более формальной формулировке, генератор псевдослучайной последовательности – это функция f, которая обладает следующими свойствами:

1. f преобразует n-битную входную строку, именуемую зерном, в p(n)-битную выходную строку, где p(n) – некоторый полиномиал, больший n.

2. f вычислима за полиномиальное по отношению к n время.

3. Для любого полиномиального по времени алгоритма A, именуемого противником, разность

|Pr_{n-битные строки x} [A принимает f(x)] – Pr_{p(n)-битные строки y} [A принимает y]|

пренебрежимо мала – под этим я подразумеваю, что она уменьшается быстрее, чем 1/q (n) для любого полиномиального q. (Разумеется, уменьшение с экспоненциальной скоростью еще лучше.) Или, обычным языком, никакой полиномиальный по времени противник не может отличить выход f от по-настоящему случайной строки с каким бы то ни было непренебрежимым смещением.

Вы можете задаться вопросом: насколько «резиновый» псевдослучайный генератор нам нужен? Чего мы добиваемся? Растянуть n-битное зерно до 2n бит? До n² бит? До n₁₀₀ бит? Оказывается ответ не имеет значения.

Почему? Потому что, даже если у нас есть псевдослучайный генератор f, который всего лишь растягивает n бит в n + 1 бит, мы можем рекурсивно применять его к его собственному выходу и таким образом растянуть n бит в p(n) бит для любого полиномиального p. Более того, если выход этого рекурсивного процесса будет эффективно отличим от случайной p(n)-битной строки, то выход самой f тоже окажется эффективно отличимым от случайной (n + 1)-битной строки, что противоречит первоначальному предположению! Конечно, кое-что здесь нужно доказывать, но это можно доказать, а я на этом остановлюсь[43]43
  Ну хорошо. Если вы жаждете увидеть доказательство, то его, например, можно найти в: Oded Goldreich, Foundations of Cryptography (Volume I: Basic Tools), Cambridge University Press, 2007.


[Закрыть].

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

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

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

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

Для начала тривиальное наблюдение: PRG может существовать только в том случае, если P ≠ NP. Почему?

Верно: потому что если P = NP, то, имея случайную будто бы строку y, мы могли бы за полиномиальное время определить, существует ли короткое зерно x, такое что f(x) = y. Если y случайна, то такого зерна почти наверняка нет, так что если оно все же существует, то мы можем быть почти уверены в том, что строка y не случайна. Таким образом, мы можем отличить выход f от истинной случайности.

Ну хорошо, будем считать, что P ≠ NP. Можем ли мы привести конкретные примеры функций, которые считаются генераторами псевдослучайных последовательностей?

Одним из примеров такой функции может служить так называемый генератор Блюм – Блюма – Шуба[44]44
  L. Blum, M. Blum and M. Shub, A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, 15 (1996), 364–383. (Заметьте, что первый из авторов – женщина. – Прим. пер.).


[Закрыть]. Вот как он работает: выберем большое составное число N. Тогда зерно x будет случайным элементом Z_N. Имея это зерно, сначала вычисляем x² mod N, (x²)²mod N, ((x²)²)² mod N и т. п. Затем объединяем в цепочку младшие биты в двоичных представлениях этих чисел и выдаем все это на выход как псевдослучайную строку f(x).

Блюм с соавторами сумели показать, что если бы у нас был полиномиальный алгоритм различения f(x) и случайной строки, то (опуская некоторые технические подробности) мы могли бы использовать этот алгоритм для разложения N на простые множители за полиномиальное время. Или, что эквивалентно, если разложение на простые множители – трудная задача, то алгоритм Блюм – Блюма – Шуба есть генератор псевдослучайной последовательности. Вот вам еще один пример, когда для «доказательства» того, что какая-то задача является трудной, мы показываем, что если бы она была простой, то простой была бы и какая-то другая задача, которую мы считаем трудной.

Увы, мы не считаем разложение на простые множители трудной задачей, по крайней мере в мире, где существуют квантовые компьютеры! Можем ли мы обосновать надежность наших псевдослучайных генераторов какими-то другими соображениями, более серьезными с квантовой точки зрения? Да, можем. Существует множество способов построения функций – кандидатов на роль псевдослучайных генераторов, и у нас нет причин полагать, что квантовые компьютеры смогут взломать их все. Ведь функцию – кандидата на роль PRG можно построить даже на кажущейся непредсказуемости, скажем, одномерного клеточного автомата, известного как «Правило 110» и описанного Стивеном Вольфрамом в его революционной книге, крушащей основы и сдвигающей парадигму.

Разумеется, нашей мечтой было бы обосновать надежность PRG при помощи наименее слабого из всех возможных предположений – самого P ≠ NP! Но при попытках сделать это математики сталкиваются с двумя интересными проблемами.

Первая проблема состоит в том, что в задаче «P и NP» рассматривается только наихудший случай. Представьте, что вы генерал или президент банка и что кто-то пытается продать вам систему шифрования, у которой, согласно рекламным материалам, существует послание, которое трудно расшифровать. Вы понимаете, в чем тут сложность: и для систем шифрования, и для PRG нам нужны NP-задачи, трудные в среднем, а не только в наихудшем случае. (Технически нам нужны задачи, которые трудны в среднем по отношению к некоторому распределению по входным данным с эффективной выборкой, не обязательно равномерному.) Но никто пока не смог доказать, что такие задачи существуют, даже если принять за факт, что P ≠ NP.

Это не означает, однако, что мы ничего не знаем о трудности в среднем случае. В качестве примера рассмотрим задачу нахождения кратчайшего вектора. В ней задана решетка L в пространстве Rn, состоящая из всех целочисленных линейных комбинаций некоторых заданных векторов v₁, …, v_n в Rⁿ. Задача в том, чтобы аппроксимировать длину кратчайшего ненулевого вектора в L с точностью до некоторого мультипликативного коэффициента k.

Задача нахождения кратчайшего вектора – одна из немногих задач, для которых мы можем доказать эквивалентность наихудшего и среднего случая (то есть что средний случай здесь нисколько не менее труден, чем наихудший), по крайней мере когда коэффициент аппроксимации k достаточно велик. Основываясь на этой эквивалентности, Айтаи, Дворк[45]45
  M. Ajtai and C. Dwork, A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of 29th Annual ACM Symposium on Theory of Computing (New York: ACM, 1997), pp. 284–93.


[Закрыть], Регев[46]46
  O. Regev, On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56:6 (2009), 1–40.


[Закрыть] и др. построили криптосистемы и генераторы псевдослучайных последовательностей, надежность которых опирается на трудность задачи нахождения кратчайшего вектора в наихудшем случае. К несчастью, те же свойства, что позволили нам в данном случае доказать эквивалентность наихудшего и среднего случаев, делают маловероятной NP-полноту задачи для релевантных значений k. Представляется более вероятным, что задача нахождения кратчайшего вектора является промежуточной между P и NP-полными, так же как, по современным представлениям, и задача разложения на простые множители.

Ну хорошо, предположим, что мы просто примем как данность, что NP-полные задачи являются трудными в среднем случае. Даже в этом случае при попытке использовать NP-полные задачи для построения генератора псевдослучайной последовательности возникает еще одна проблема. Дело в том, что задача взлома псевдослучайного генератора, судя по всему, просто имеет неподходящую «форму» для того, чтобы быть NP-полной. Что я имею в виду? Вспомните, как мы доказываем NP-полноту некоторой задачи B: мы берем задачу A, о которой заранее известно, что она NP-полная, и придумываем полиномиальный по времени способ сведения, превращающий «да-случаи» A в «да-случаи» B, а «нет-случаи» A в «нет-случаи» B. В ситуации с задачей взлома PRG «да-случаями», надо полагать, были бы псевдослучайные строки, а «нет-случаями» – истинно случайные строки (или, может быть, наоборот).

Видите здесь проблему? Если нет, позвольте мне разжевать еще подробнее: как нам описать «истинно случайную строку» для того, чтобы сводить к ней? Весь смысл истинной случайности строки в том, что мы не можем описать ее чем бы то ни было более коротким, чем она сама! Правда, в этом аргументе полно дыр, одна из которых состоит в том, что процедура сведения может быть рандомизирована. Тем не менее из этого можно сделать некоторый вывод: если задача взлома PRG NP-полная, то доказывать это нужно как-то совершенно иначе, чем в тех доказательствах NP-полноты, к которым мы привыкли.

Односторонние функции

Односторонние функции – близкие родственники псевдослучайных генераторов. На интуитивном уровне односторонней называется функция, которую легко вычислить, но трудно обратить. Более формально, функция f преобразования из n бит в p(n) бит является односторонней, если выполняется следующее:

1. f вычислима за полиномиальное время от n.

2. Для любого полиномиального по времени противника A вероятность того, что функция A успешно инвертирует f,

Pr_{n-битные строки x} [f(A (f(x))) = f(x)],

пренебрежимо мала, то есть меньше, чем 1/q(n) для любого полиномиального q.

Событие f(A(f(x))) = f(x) фигурирует в определении вместо простого A(f(x)) = x, чтобы учесть тот факт, что f может иметь несколько обратных функций. С таким определением мы рассматриваем алгоритмы A, которые находят хоть что-нибудь в прообразе f(x), не обязательно сам x.

Я утверждаю, что из существования генераторов псевдослучайных последовательностей следует существование односторонних функций (OWF). Можете сказать, почему?

Верно: потому что PRG и есть OWF!

Ну хорошо, тогда можете доказать, что из существования OWF следует существование PRG?

Ага, это чуть посложнее! Основная причина в том, что выход OWF f не обязан выглядеть случайным для того, чтобы f было трудно инвертировать. И в самом деле, потребовалось больше десяти лет работы, – вершиной ее стала огромная статья, опубликованная в 1999 г. Хостадом, Импальяццо, Левиным и Луби[47]47
  J. Håstad, R. Impagliazzo, L. A. Levin and M. Luby, A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28:4 (1999), 1364–96. http://citeseer.ist.psu.edu/hastad99pseudorandom.html


[Закрыть], – чтобы понять, как построить генератор псевдослучайной последовательности из любой односторонней функции. Благодаря работе Хостада и др. мы сегодня знаем, что односторонние функции существуют в том и только том случае, если существуют псевдослучайные генераторы. Доказательство здесь, как можно ожидать, довольно сложное, а сведение не слишком реально, так как коэффициент «растягивания» может быть порядка n40! Из-за таких фокусов термин «полиномиальное время» пользуется дурной репутацией, но к счастью, это исключение, а не правило! Если мы примем, что односторонняя функция – это некоторая перестановка, то доказательство становится намного проще (его провел Яо еще в 1982 г.)[48]48
  A. Chi-Chih Yao, Theory and applications of trapdoor functions [extended abstract]. In Proceedings of 24th Annual IEEE Symposium on Foundations of Computer Science (Silver Spring, MD: IEEE Computer Society Press, 1982), pp. 80–91.


[Закрыть], а сведение идет намного быстрее. Но, разумеется, результат получается менее общий.

До сих пор мы ограничивались рассмотрением криптосистем с закрытым ключом, в которых считается самоочевидным, что отправитель и получатель владеют общим секретным ключом. Но как могли бы вы обрести общий секретный ключ, скажем, с сайтом Amazon.com прежде, чем передадите им номер своей кредитной карты? Вы что, пошлете им ключ по электронной почте? Да… но если вы хотите так поступить, то лучше будет зашифровать свое сообщение при помощи другого секретного ключа, и так далее до бесконечности!

Решение, конечно, состоит в том, чтобы лично встретиться с работником фирмы Amazon в полночь в заброшенном гараже. Нет, погодите… Я хотел сказать, что решение – воспользоваться системой шифрования с открытым ключом.