В 1868 году математик Чарльз Доджсон (более известный как Льюис Кэрролл) заявил, что схема шифрования под названием «шифр Виженера» является «невзламываемой». У него не было доказательств, однако имелись убедительные подтверждения этой веры: математики безуспешно пытались его взломать более трёх сотен лет.

Была лишь одна небольшая проблема: на самом деле, пятью годами ранее её взломал немецкий пехотный офицер Фридрих Касиски, описав решение в книге, привлёкшей на тот момент мало внимания.

Криптографы играли в эти «кошки-мышки», создавая и взламывая шифры, ещё с тех пор, как люди впервые начали передавать секретную информацию. «Тысячи лет люди пытались найти ответ на вопрос: сможем ли мы разорвать этот круг?», — рассказывает криптограф Рафаэль Пасс из Cornell Tech и Корнеллского университета.

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

Сегодня подобные функции используются в Интернет-протоколах для выполнения таких задач, как передача номеров кредитных карт и цифровых подписей. «Основная часть используемой в реальном мире криптографии может быть основана на односторонних функциях», — объясняет криптограф Юваль Исхаи [Uval Ishai] из Техниона (Хайфа, Израиль).

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

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

Криптографы уже давно задавались вопросом, существует ли более обобщённая методика изучения. «Существует ли некая главная задача, которая позволит нам понять, возможна ли криптография в принципе?», — задаётся вопросом Пасс.

Недавно они с аспирантом Корнеллского университета Яньи Лю [Yanyi Liu] доказали, что она существует. Эти учёные доказали, что существование истинных односторонних функций зависит от самой старой и фундаментальной задачи в другой области computer science под названием «теория сложности», или «вычислительная сложность». Эта задача, называемая колмогоровской сложностью, касается определения того, насколько сложно отличить случайные строки чисел от строк, содержащих некую информацию.


Криптограф Cornell Tech и Корнеллского университета Рафаэль Пасс помог найти вопрос, ответ на который позволит выяснить, действительно ли существуют односторонние функции, а значит, и вся современная криптография.

Лю и Пасс доказали, что если конкретная версия колмогоровской сложности является сложновычисляемой, то истинные односторонние функции существуют и есть чёткий способ построения такой функции. Если же эту версию колмогоровской сложности вычислить легко, то односторонних функций не может существовать. «Оказалось, что эта задача, возникшая ещё до того, как люди придумали односторонние функции, полностью их характеризует», — рассказывает Пасс.

Из этого вывода следует, что вместо того, чтобы подыскивать варианты односторонних функций, криптографы могут просто сосредоточить свои усилия на понимании колмогоровской сложности. «Всё зависит от этой задачи», — говорит Исхаи. Доказательство стало «качественно новой работой в фундаментальной криптографии».

Статья стимулирует к более тесному сотрудничеству криптографов и специалистов по теории сложности, вызвав всплеск активности по объединению их методик. «Несколько исследовательских групп уже работают над более глубоким изучением проблемы», — сообщил специалист по computer science Райан Уильямс из Массачусетского технологического института.

Вычисление сложности

Обычно сложность задачи является препятствием. Однако в криптографии, где её можно использовать против своих противников, это благословение. В 1976 году Уитфилд Диффи и Мартин Хеллман написали новаторскую статью в которой написали, что высокая сложность односторонних функций — это именно то, что нужно криптографам в условиях зарождающейся компьютерной эпохи. «Мы стоим на пороге революции в криптографии», — заявили они.


Мартин Хеллман (в центре) и Уитфилд Диффи (справа), написавшие историческую статью, связавшую односторонние функции с криптографией. Фото 1977 года, слева Ральф Меркл.

За последующие десятилетия исследователи выяснили, как создавать из односторонних функций широкий спектр криптографических инструментов, в том числе шифрование с приватным ключом, цифровые подписи, генераторы псевдослучайных чисел и доказательства с нулевым разглашением (в которых один человек может убедить другого, что утверждение истинно, не раскрывая доказательства). По словам Пасса, статья Диффи и Хеллмана «походила на пророчество». Из единственного кирпичика односторонних функций криптографы смогли создать «свои сверхсложные и красивые творения».

Чтобы понять, как работают односторонние функции, представьте, что кто-то попросил вас перемножить два простых числа, допустим, 6547 и 7079. Вычисление результата (46346213) может оказаться немного трудоёмким, но вполне посильным. Однако если бы кто-то показал вам число 46346213 и спросил его простые множители, то вы могли бы и не найти их. На самом деле, для чисел с достаточно большими простыми множителями у нас нет эффективного (известного нам) способа нахождения этих множителей. Поэтому умножение стало многообещающим кандидатом на звание односторонней функции: если начинать с достаточно больших простых чисел, процесс легко выполнить, но сложно обратить. Но мы не знаем наверняка, так ли это. В любой момент кто-нибудь может найти быстрый способ разложения чисел на множители.

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

В 1985 году специалист по computer science Леонид Левин из Бостонского университета ответил на этот вопрос в формальном виде, продемонстрировав «универсальную» одностороннюю функцию, которая гарантированно была бы односторонней функцией, если они вообще существуют. Однако, по словам специалиста по computer science Эрика Эллендера из Ратгерского университета, эта конструкция была «очень искусственной». «Изучать её можно только для того, чтобы получить такой результат».

На самом деле криптографы стремились найти универсальную одностороннюю функцию, возникшую из некой естественной задачи; она могла бы дать истинное понимание того, существуют ли односторонние функции. Исследователи давно думали о конкретной задаче, появившейся в 1960-х: колмогоровской сложности, являющейся мерой случайности. Однако её связь с односторонними функциями была слабой и ускользающей.

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

Пасс попытался убедить многих аспирантов исследовать этот вопрос вместе с ним, но ни один из них не захотел заниматься тем, что может оказаться бесплодным проектом. Потом аспирантом Корнеллского университета стал Яньи Лю. «Яньи был бесстрашен», — вспоминает Пасс. Вместе они погрузились в изучение задачи.

Что такое случайность?

Концепцию случайности, по самой её природе, сложно объяснить. Есть комикс про Дилберта, в котором на экскурсии по офисам компании Дилберту показывают «генератор случайных чисел» бухгалтерского отдела. Тот оказывается монстром, постоянно повторяющим число 9. «Вы уверены, что он случаен?», — спрашивает Дилберт. «В этом-то и есть проблема случайности — точно никто не знает», — отвечает его гид.


Яньи Лю работал с Пассом над выявлением значимой связи между односторонними функциями и колмогоровской сложностью.

Если кто-то покажет вам строки чисел 99999999999999999999 и 03729563829603547134, и скажет, что их выбрали случайно, то вы не сможете опровергнуть это заявление со всей определённостью: при выборе случайных чисел вероятность создания обеих строк одинакова. Однако вторая строка определённо кажется более случайной.

«Мы считаем, что знаем, что имеем в виду, когда говорим „это случайные данные“. Однако до появления концепции колмогоровской сложности у нас не было математически значимого определения», — говорит Эллендер.

Чтобы прийти к понятию случайной строки чисел, в 1960-х годах Андрей Колмогоров решил сосредоточиться не на процессе генерации строк, а на простоте их описания. Строку 99999999999999999999 можно кратко записать как «20 девяток», однако у строки 03729563829603547134 может и не быть более короткого описания, чем сама строка.

Колмогоров определил сложность строки как длину кратчайшей возможной программы, создающей на выходе эту строку. Если мы имеем дело, допустим, со строками из тысячи цифр, некоторые из них имеют очень короткие программы, например, «напечатать тысячу девяток» или «напечатать число 2³³¹⁹» или «напечатать тысячу знаков пи при помощи следующей формулы...». Другие строки невозможно описать кратко и мы не можем получить программы короче, чем так, которая просто записывает строку целиком и приказывает компьютеру её вывести. А для некоторых строк длина программ находится где-то посередине.

Колмогоровская сложность быстро стала одной из базовых концепций computer science. Это понятие настолько фундаментально, что в 1960-х его по отдельности обнаруживали несколько раз. По словам Пасса, это «глубокая задача, не просто о случайности и математике, но и о науке в целом».

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

Чтобы понять это, представим, что у нас есть программа, способная вычислить колмогоровскую сложность любой строки. Назовём эту программу K. Теперь давайте найдём наименьшую строку чисел (назовём её S), колмогоровская сложность которой вдвое больше длины K. Чтобы перейти к конкретике, представим, что K состоит из 1 миллиона символов, поэтому мы будем искать строку S, колмогоровская сложность которой равна 2 миллионам (то есть кратчайшая программа, выводящая S, содержит 2 миллиона символов).


Благодаря наличию программы K вычислить S легко (хоть и необязательно быстро): мы можем написать новую программу под названием P. По сути, программа P приказывает: «Пройди по всем строкам по порядку, используя программу K для вычисления их колмогоровской сложности, пока не найдёшь первую, колмогоровская сложность которой равна 2 миллионам». При создании программы P нам потребуется использовать программу K, поэтому суммарно P будет немного больше 1 миллиона символов. Однако эта программа выводит S, а мы определили S как строку, кратчайшая программа которой содержит 2 миллиона символов. Мы пришли к противоречию.

Однако это противоречие испаряется, если вместо поиска кратчайшей программы, выводящей строку, мы будем искать кратчайшую достаточно эффективную программу, выводящую строку (и
здесь нам нужно указать, что означает «достаточно»). В конечном итоге, для выполнения программы P потребуется огромное количество времени, ведь ей нужно проверить очень много строк. Если мы запретим такие сложные программы, то придём к понятию «ограниченной по времени» колмогоровской сложности. Эта версия колмогоровской сложности вычисляема — мы можем вычислить ограниченную по времени колмогоровскую сложность для любой возможной строки, по крайней мере, теоретически. И в некотором смысле эта концепция столь же естественна, как и сама колмогоровская сложность. Ведь в конечном итоге, по словам Пасса, на самом деле нас волнует только следующий вопрос: «Можно ли сгенерировать строку, пока мы ещё живы, или пока существует Вселенная?»

Так как ограниченная по времени колмогоровская сложность вычисляема, естественно возникает следующий вопрос: насколько сложно её вычислить. И Лю с Пассом доказали, что в этом вопросе скрывается ключ к ответу о существовании односторонних функций. «Это замечательное открытие», — утверждает Эллендер.

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

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


И если их функцию можно сделать практичной, её следует предпочесть другим кандидатам на роль односторонних функций, основанным на умножении и других математических операциях. Если уж односторонняя функция существует, то она будет такой. «Если мы сможем сломать подобную схему, то и все остальные схемы тоже могут быть сломаны», — утверждает Пасс.

Расширение теории

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

Теперь у криптографии и теории сложности появилась общая цель и каждая из областей предлагает свежий взгляд на неё: у криптографов есть причины считать, что односторонние функции существуют, а у специалистов по теории сложности есть столь же весомые причины думать, что ограниченная по времени колмогоровская сложность является сложной задачей. Благодаря новым исследовательским результатам обе эти гипотезы подкрепляют друг друга.

«Если вы верите, что задача колмогоровской сложности сложна, то верите и в существование односторонних функций. А если вы верите в криптографию, то вам придётся поверить, что эта версия ограниченной по времени колмогоровской сложности обязана быть сложной».

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

Всё это намекает нам на то, что истинную пользу открытия мы узнаем в будущем. «Это семя, которое, вероятно, разовьётся в гораздо более обширную теорию», — считает Исхаи.