Статус миров Импальяццо?

33

В 1995 году Рассел Импальяццо предложил пять миров сложности:

1- Алгоритмика: со всеми удивительными последствиями.P=NP

2- Эвристика: -полные проблемы трудны в худшем случае ( P N P ), но эффективно решаемы в среднем случае.NPPNP

3- Пессиланд: Существуют -полные проблемы среднего случая, но односторонних функций не существует. Это подразумевает, что мы не можем генерировать сложные случаи N P -полной проблемы с известным решением. NPNP

4- Minicrypt: существуют односторонние функции, но криптографические системы с открытым ключом невозможны

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

Какой мир предпочитают последние достижения в вычислительной сложности? Что является лучшим доказательством выбора?

Рассел Импальяццо, личный взгляд на сложность среднего случая , 1995

Пять миров Импальяццо, блог «Вычислительная сложность»

Мухаммед Аль-Туркистани
источник
2
Мне не хватает эксперта, чтобы ответить, но я подумал, что вам, возможно, хотелось бы узнать, что на первом семинаре «Препятствия в сложности» Impagliazzo призвал к проведению исследовательской программы, в значительной степени соответствующей вашему вопросу. Назовите оракулов, похожих на «земных», в которых содержатся те же теоремы сложности, которые существуют в «реальном» нерелятивизированном мире, в котором мы живем. Затем изучите свойства этих оракулов, которые похожи на настоящую Землю. Итак, в этих рамках ваш вопрос становится следующим: «Что должен удовлетворить оракул, чтобы быть подобным Земле?»
Аарон Стерлинг

Ответы:

26

Около года назад я совместно организовал семинар по сложности и криптографии: состояние миров Импальяццо , и слайды и видео на веб-сайте могут представлять интерес.

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

Возможно, наиболее важной частью новой информации является алгоритм Шора, который показывает, что, по крайней мере, если вы замените P на BQP, наиболее часто используемые криптосистемы с открытым ключом являются небезопасными. Но из-за криптосистем на основе решетки по умолчанию предполагается, что мы живем в криптомании даже в этом случае, хотя, возможно, консенсус здесь немного слабее, чем в классическом случае. Даже в классическом случае, кажется, существует гораздо больше доказательств существования односторонних функций («Minicrypt»), чем существование шифрования с открытым ключом («Cryptomania»). Тем не менее, учитывая усилия, которые люди потратили на попытки взломать различные криптосистемы с открытым ключом, есть и существенные доказательства для последней.

Боаз Барак
источник
Эта ссылка может работать лучше: archive.dimacs.rutgers.edu/Workshops/Cryptography/program.html
Тимоти Чоу
18

Хороший вопрос, но ученые не смогли даже отделить «Алгоритмику» от остальных случаев, не говоря уже о том, чтобы решить, в каком именно мире мы живем.

Тем не менее, есть несколько исследовательских работ по этому вопросу. См. Например: О возможности обоснования криптографии на предположении, что P! = NP Гольдрайха и Гольдвассера, и их ссылок.

См. Также Об основании односторонних функций на NP-твердости Ади Акавиа и соавт.

Кроме того, хорошо известно, что декодирование некоторых криптосистем является NP-сложным (см., Например, криптосистему McEliece или криптографию на основе решетки ). Я не знаю, почему это НЕ решает проблему, так как я не знаком с такими криптосистемами. Смотрите комментарии Питера Шора ниже.

Я также предлагаю вам взглянуть на обсуждение в Stackoverflow . Обзор литературы, которая цитирует работу Импальяццо, также может быть поучительным.

РЕДАКТИРОВАТЬ: Следующие результаты могут представлять интерес:

Фейгенбаум и Фортноу. Случайно-самовосстанавливаемость полных множеств. SIAM Journal of Computing, 22: 994–1005, 1993.

Богданов и Тревизан. О сокращениях от наихудшего к среднему для задач NP. В материалах 44-го ежегодного симпозиума IEEE по основам компьютерных наук, стр. 308–317, 2003.

Акавиа, Гольдрайх, Гольдвассер и Мошковиц. Об односторонних функциях на основе NP-твердости

Гутфройнд и Та-Шма. Новые связи между дерандомизацией, сложностью наихудшего случая и сложностью среднего случая. Tech. Отчет TR06-108, Электронный коллоквиум по вычислительной сложности, 2006.

Богданов и Тревизан. Средняя сложность. Нашел. Теория тенденций. Вычи. Sci. 2, 1 (октябрь 2006 г.), 1-106. DOI = http://dx.doi.org/10.1561/0400000004

М.С. Дусти
источник
5
Криптосистема Мак-Элиса не является криптосистемой; это целое семейство криптосистем, в зависимости от того, какой класс кодов с исправлением ошибок вы используете в нем. Если вы используете произвольные коды с исправлением ошибок, то NP-трудно сломать, но также NP-трудно декодировать сообщение. Если вы используете класс кодов с исправлением ошибок, который имеет алгоритм декодирования за полиномиальное время, то действительно декодировать сообщение действительно нужно за полиномиальное время, но у нас больше нет доказательств того, что взлом криптосистемы является NP трудным. Ситуация с решеточной криптографией лучше, но все же не сложно взломать.
Питер Шор
@Peter: Большое спасибо! Вы решили загадку, которая меня давно заинтриговала!
MS Dousti
На самом деле, похоже, что для некоторых семейств кодов с исправлением ошибок криптосистема Мак-Элиса была взломана, но не для кодов Гоппы, которые были в первоначальном предложении Мак-Элиса.
Питер Шор