В 1868 году математик Чарльз Доджсон (более известный как Льюис Кэрролл) заявил, что схема шифрования под названием «шифр Виженера» является «невзламываемой». У него не было доказательств, однако имелись убедительные подтверждения этой веры: математики безуспешно пытались его взломать более трёх сотен лет.
Была лишь одна небольшая проблема: на самом деле, пятью годами ранее её взломал немецкий пехотный офицер Фридрих Касиски, описав решение в книге, привлёкшей на тот момент мало внимания.
Криптографы играли в эти «кошки-мышки», создавая и взламывая шифры, ещё с тех пор, как люди впервые начали передавать секретную информацию. «Тысячи лет люди пытались найти ответ на вопрос: сможем ли мы разорвать этот круг?», — рассказывает криптограф Рафаэль Пасс из Cornell Tech и Корнеллского университета.
Пять десятилетий назад криптографы сделали широкий шаг в этом направлении. Они продемонстрировали, что можно создавать доказуемо защищённые шифры, если есть доступ к единственному ингредиенту — односторонней функции, которую легко вычислить, но сложно обратить. С тех пор исследователи придумали широкий спектр вариантов односторонних функций, от одиночных операций, основанных на умножении, до более сложных геометрических или логарифмических процедур.
Сегодня подобные функции используются в Интернет-протоколах для выполнения таких задач, как передача номеров кредитных карт и цифровых подписей. «Основная часть используемой в реальном мире криптографии может быть основана на односторонних функциях», — объясняет криптограф Юваль Исхаи [Uval Ishai] из Техниона (Хайфа, Израиль).
Но это достижение не положило конец игре в «кошки-мышки», а лишь сузило её рамки. Теперь криптографам не нужно беспокоиться о защищённости всех аспектов криптографической схемы, им достаточно лишь заниматься лежащей в её основе функцией. Но ни для одной из ныне используемых функций не было определённо доказано, что они являются односторонними, мы даже не знаем точно, существуют ли истинные односторонние функции. Криптографы доказали, что если их нет, то защищённая криптография невозможна.
В условиях отсутствия доказательств криптографам остаётся лишь надеяться на то, что пережившие все атаки функции на самом деле являются надёжными. У исследователей нет обобщённой методики изучения защищённости этих функций, поскольку, по словам Исхаи, каждая функция «взята из своей предметной области и разработана своей командой специалистов».
Криптографы уже давно задавались вопросом, существует ли более обобщённая методика изучения. «Существует ли некая главная задача, которая позволит нам понять, возможна ли криптография в принципе?», — задаётся вопросом Пасс.
Недавно они с аспирантом Корнеллского университета Яньи Лю [Yanyi Liu] доказали, что она существует. Эти учёные доказали, что существование истинных односторонних функций зависит от самой старой и фундаментальной задачи в другой области computer science под названием «теория сложности», или «вычислительная сложность». Эта задача, называемая колмогоровской сложностью, касается определения того, насколько сложно отличить случайные строки чисел от строк, содержащих некую информацию.
Лю и Пасс доказали, что если конкретная версия колмогоровской сложности является сложновычисляемой, то истинные односторонние функции существуют и есть чёткий способ построения такой функции. Если же эту версию колмогоровской сложности вычислить легко, то односторонних функций не может существовать. «Оказалось, что эта задача, возникшая ещё до того, как люди придумали односторонние функции, полностью их характеризует», — рассказывает Пасс.
Из этого вывода следует, что вместо того, чтобы подыскивать варианты односторонних функций, криптографы могут просто сосредоточить свои усилия на понимании колмогоровской сложности. «Всё зависит от этой задачи», — говорит Исхаи. Доказательство стало «качественно новой работой в фундаментальной криптографии».
Статья стимулирует к более тесному сотрудничеству криптографов и специалистов по теории сложности, вызвав всплеск активности по объединению их методик. «Несколько исследовательских групп уже работают над более глубоким изучением проблемы», — сообщил специалист по computer science Райан Уильямс из Массачусетского технологического института.