[Перевод] В какой вычислительной вселенной мы живем?
Криптографы хотят знать, в каком из пяти возможных миров мы живем, что покажет, возможна ли вообще по-настоящему безопасная криптография.
Многие учёные занимаются решением сложных вычислительных задач. Но есть одна область информатики, в которой сложность является преимуществом: криптография, где вам нужны жёсткие препятствия между вашими противниками и вашими секретами.
К сожалению, мы не знаем, действительно ли существует безопасная криптография. На протяжении тысячелетий люди создавали шифры, которые казались нерушимыми до тех пор, пока их не взломали. Сегодня наши интернет-транзакции и государственные секреты охраняются методами шифрования, которые кажутся надежными, но вполне могут дать сбой в любой момент.
Чтобы создать действительно безопасный (и постоянный) метод шифрования, нам нужна вычислительная задача, которая достаточно сложна, чтобы создать доказуемо непреодолимый барьер для злоумышленников. Мы знаем о многих вычислительных задачах, которые кажутся сложными, но, возможно, мы просто недостаточно умны, чтобы решить их. Или, может быть, некоторые из них сложны, но их сложность не позволяет использовать их в безопасном шифровании. По сути, криптографы задаются вопросом: достаточно ли сложности во Вселенной, чтобы сделать криптографию возможной?
В 1995 году Рассел Импальяццо из Калифорнийского университета в Сан-Диего разбил вопрос о сложности на набор подвопросов, которые специалисты по информатике могли решать по одному за раз. Чтобы обобщить состояние знаний в этой области, он описал пять возможных миров — причудливо названных Алгоритмика, Эвристика, Пессиландия, Миникрипт и Криптомания — с возрастающими уровнями сложности и криптографической возможности. Любой из них может быть миром, в котором мы живем.
Алгоритмика
В этом мире самые естественные вычислительные вопросы решаются легко, что делает криптографию невозможной. Здесь набор проблем с эффективными решениями — набор под названием P — содержит не только проблемы, которые мы уже придумали, как решить. Он также включает в себя все задачи из иного набора, называемого NP, который состоит из задач, для которых легко проверить предложенное решение.
На первый взгляд, P и NP кажутся разными категориями. Например, возьмем задачу по проверке, поместятся ли в ваших чемоданах все предметы, которые вы хотите упаковать для поездки. Если друг упаковывает вещи для вас, легко проверить, все ли он упаковал — просто проверьте, не пропустил ли он чего-нибудь. Таким образом, проблема упаковки чемодана в NP. Но упаковать чемоданы самостоятельно намного сложнее — возможно, вам придется перепробовать много разных способов. Неясно, существует ли эффективный алгоритм, решающий эту задачу для всех возможных комбинаций предметов и чемоданов. То есть мы не знаем, есть ли эта проблема в P.
Проблема расшифровки схемы шифрования расположена в NP. В конце концов, если у вас есть зашифрованное сообщение, а друг утверждает, что расшифровал его, вы можете проверить, загрузив его расшифрованное сообщение в шифровальную машину и посмотрев, соответствует ли результат исходному зашифрованному сообщению. (Конечно, для этого у вас должна быть одна из шифровальных машин, но криптографы не считают схему безопасной, если она не может противостоять атакам врага, завладевшего одной из машин.)
В Алгоритмике P и NP — это один и тот же набор задач. Доказательство этого было бы великолепной новостью, поскольку это означало бы, что существуют быстрые алгоритмы для таких вещей, как упаковка чемодана и всех иных, казалось бы, сложных задач в NP. Но это было бы катастрофой для криптографов, поскольку одна из проблем, которую мы могли бы эффективно решить, — это расшифровка.
Большинство учёных считают, что P отличается от NP по той простой причине, что в NP так много проблем, которые мы не можем эффективно решить. Но никому так и не удалось доказать (или опровергнуть) это, хотя вопрос «P против NP» считается самой известной проблемой в теоретической информатике на протяжении пяти десятилетий. С иной стороны, Юваль Ишай из Техниона в Хайфе, Израиль, сказал, — «помимо постоянных неудач самых умных людей, у нас нет доказательств того, что трудно показать, что P не равно NP».
Эвристика
В этом мире есть проблемы в NP, которые нелегко решить, но каждая проблема в NP является легкой «в среднем», что означает, что в большинстве случаев ее можно решить эффективно. Например, если мы находимся в Эвристике, то существует эффективный алгоритм упаковки чемоданов, который почти всегда срабатывает, но может дать сбой для нескольких редких комбинаций чемоданов и вещей, которые необходимо упаковать. (Эти быстрые и обычно успешные алгоритмы обычно называют «эвристиками».)
С точки зрения криптографии большой разницы между Эвристикой и Алгоритмикой нет. Если мы придумаем схему шифрования в Эвристике, можно изобрести какой-то быстрый метод расшифровки, который сможет обработать почти каждое сообщение, что сделает схему бесполезной для практических целей.
Пессиландия
Это худший из всех возможных миров. В Пессиландии некоторые задачи в NP сложны даже в среднем. Для этих задач любой эффективный алгоритм будет давать сбой не только время от времени, но и часто. Тем не менее, эти сложные проблемы не из тех, которые полезны в целях сокрытия секретной информации.
«Мы точно не хотим жить в Пессиландии», — сказал Эрик Аллендер из Университета Ратгерса. «Здесь мы получаем все плохие аспекты вычислительной сложности, но без каких-либо преимуществ, таких как криптография».
Миникрипт
В этом мире некоторые задачи в NP в среднем сложны, и этой сложности достаточно, чтобы построить самый фундаментальный строительный блок криптографии: «одностороннюю функцию», это такая функция, которая может быть выполнена эффективно, но не может быть эффективно обращена вспять. Криптографы показали, что безопасная криптография требует односторонних функций. И если они у нас есть, мы получаем множество криптографических плюсов, таких как шифрование с секретным ключом, цифровые подписи и генераторы псевдослучайных чисел.
«Существуют ли односторонние функции, без сомнения, самая важная проблема в криптографии», — сказал Рафаэль Пасс из Корнельского университета и Корнельского технологического института. «Если у нас их нет, все эти вещи могут быть сломаны».
Криптомания
В этом мире у нас достаточно сложности, чтобы создать всё из Миникрипт, а также даже более продвинутые криптографические протоколы, такие как шифрование с открытым ключом (в котором люди могут отправлять зашифрованные сообщения, не зная секретного ключа).
Исключая миры
По словам Ишай, большинство криптографов считают, что по крайней мере какая-то криптография существует, поэтому мы, вероятно, живем в криптомании или миникрипте. Но они не ждут доказательств этого в ближайшее время. Такое доказательство потребовало бы исключения трех иных миров, а исключение лишь Алгоритмики уже требует решения проблемы «P против NP», над которой учёные бьются десятилетиями.
Однако недавно Пасс и его аспирант Яньи Лю нашли новый подход к изучению этих миров. Впервые они определили естественную проблему — названную колмогоровской сложностью с ограничением по времени, или сокращенно Kt, — уровень сложности которой создаёт яркую разделительную линию между мирами, включающими криптографию, и мирами, в которые она не входит. Если Kt в среднем проста, как показали Лю и Пасс, то безопасная криптография не может существовать, поэтому мы находимся в Алгоритмике, Эвристике или Пессиландии. Но если Kt в среднем сложна, то мы можем создавать односторонние функции, так что мы как минимум в Миникрипте, а возможно и в Криптомании.
Этот новый результат означает, что учёные могут исключить Пессиландию — худший из миров — если они смогут доказать ещё одно утверждение: если Kt в среднем легка, то такова и любая задача в NP. В этом случае мы сузим список до миров, где Kt в среднем сложна (Миникрипт и Криптомания), и тех, где Kt — и любая другая проблема в NP — в среднем легка (Алгоритмика и Эвристика).
По словам Райана Уильямса из Массачусетского Технологического Института, учёные уже какое-то время пытаются разобраться в Пессиландии. «Я думаю, что все согласны с тем, что Пессиландию можно исключить, но через какое время мы это сделаем, я не знаю».
Криптографы также хотели бы исключить Эвристику, что потребовало бы доказательства того, что если Kt в среднем проста, то каждая проблема в NP проста во всех случаях (не только в среднем). Исключение этих двух миров означало бы, что мы либо живём в Алгоритмике, где всё всегда просто, либо у нас достаточно сложности для базовой криптографии.
Криптографы называют эту цель Святым Граалем в этой области. Ишай не ожидает, что проблему решат при его жизни, но даже это неизвестно. «Когда сложные проблемы решаются, иногда мы видим новые горизонты, а иногда нет», — сказал он. «Определенно, наш лучший шанс — это новое направление работы».
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
