В какой вычислительной вселенной мы живем?

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

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

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

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

В 1995 году Рассел Импальяццо из Калифорнийского университета в Сан-Диего разбил вопрос о сложности на набор подвопросов, которые специалисты по информатике могли решать по одному за раз. Чтобы обобщить состояние знаний в этой области, он описал пять возможных миров – причудливо названных Алгоритмика, Эвристика, Пессиландия, Миникрипт и Криптомания – с возрастающими уровнями сложности и криптографической возможности. Любой из них может быть миром, в котором мы живем.

Алгоритмика

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

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

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

В Алгоритмике P и NP — это один и тот же набор задач. Доказательство этого было бы великолепной новостью, поскольку это означало бы, что существуют быстрые алгоритмы для таких вещей, как упаковка чемодана и всех иных, казалось бы, сложных задач в NP. Но это было бы катастрофой для криптографов, поскольку одна из проблем, которую мы могли бы эффективно решить, – это расшифровка.

Большинство учёных считают, что P отличается от NP по той простой причине, что в NP так много проблем, которые мы не можем эффективно решить. Но никому так и не удалось доказать (или опровергнуть) это, хотя вопрос «P против NP» считается самой известной проблемой в теоретической информатике на протяжении пяти десятилетий. С иной стороны, Юваль Ишай из Техниона в Хайфе, Израиль, сказал, – «помимо постоянных неудач самых умных людей, у нас нет доказательств того, что трудно показать, что P не равно NP».

Эвристика

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

С точки зрения криптографии большой разницы между Эвристикой и Алгоритмикой нет. Если мы придумаем схему шифрования в Эвристике, можно изобрести какой-то быстрый метод расшифровки, который сможет обработать почти каждое сообщение, что сделает схему бесполезной для практических целей.

Пессиландия

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

«Мы точно не хотим жить в Пессиландии», – сказал Эрик Аллендер из Университета Ратгерса. «Здесь мы получаем все плохие аспекты вычислительной сложности, но без каких-либо преимуществ, таких как криптография».

Миникрипт

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

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

Криптомания

В этом мире у нас достаточно сложности, чтобы создать всё из Миникрипт, а также даже более продвинутые криптографические протоколы, такие как шифрование с открытым ключом (в котором люди могут отправлять зашифрованные сообщения, не зная секретного ключа).

Исключая миры

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

Однако недавно Пасс и его аспирант Яньи Лю нашли новый подход к изучению этих миров. Впервые они определили естественную проблему – названную колмогоровской сложностью с ограничением по времени, или сокращенно K^t, – уровень сложности которой создаёт яркую разделительную линию между мирами, включающими криптографию, и мирами, в которые она не входит. Если K^t в среднем проста, как показали Лю и Пасс, то безопасная криптография не может существовать, поэтому мы находимся в Алгоритмике, Эвристике или Пессиландии. Но если K^t в среднем сложна, то мы можем создавать односторонние функции, так что мы как минимум в Миникрипте, а возможно и в Криптомании.  

Этот новый результат означает, что учёные могут исключить Пессиландию – худший из миров – если они смогут доказать ещё одно утверждение: если K^t в среднем легка, то такова и любая задача в NP. В этом случае мы сузим список до миров, где K^t в среднем сложна (Миникрипт и Криптомания), и тех, где K^t – и любая другая проблема в NP — в среднем легка (Алгоритмика и Эвристика).

По словам Райана Уильямса из Массачусетского Технологического Института, учёные уже какое-то время пытаются разобраться в Пессиландии. «Я думаю, что все согласны с тем, что Пессиландию можно исключить, но через какое время мы это сделаем, я не знаю».

Криптографы также хотели бы исключить Эвристику, что потребовало бы доказательства того, что если K^t в среднем проста, то каждая проблема в NP проста во всех случаях (не только в среднем). Исключение этих двух миров означало бы, что мы либо живём в Алгоритмике, где всё всегда просто, либо у нас достаточно сложности для базовой криптографии.

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

Автор перевода @arielf

НЛО прилетело и оставило здесь промокод для читателей нашего блога:

— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.