Исследователи выявили «главную проблему», лежащую в основе всей криптографии

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

Введение

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

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

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

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

Сегодня интернет-протоколы, используемые для таких задач, как передача номеров кредитных карт и цифровых подписей, зависят от этих функций. «Большая часть криптовалюты, используемой в реальном мире, основана на односторонних функциях», — сказал Юваль Ишай, криптограф из Техниона в Хайфе, Израиль.

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

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

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

Теперь он и Яньи Лю, аспирант Корнеллского университета, доказали, что ответ — да. Они доказали, что существование истинных односторонних функций зависит от одной из старейших и важнейших проблем в другой области компьютерных наук, называемой теорией сложности, или вычислительной сложностью. Эта проблема, известная как сложность Колмогорова, касается того, насколько сложно отличить случайные строки чисел от строк, содержащих некоторую информацию.

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

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

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

Использование твердости

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Более богатая теория

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

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

«Если вы считаете, что эта проблема [колмогоровской сложности] сложна… то вы верите в односторонние функции», — сказал Уильямс. «И если вы вообще верите в криптографию, то вы как бы должны верить, что эта версия ограниченной по времени колмогоровской сложности должна быть сложной».

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

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

Источник: www.quantamagazine.org