В 1995 году Рассел Импальяццо предложил пять миров сложности:
1- Алгоритмика: со всеми удивительными последствиями.
2- Эвристика: -полные проблемы трудны в худшем случае ( P ≠ N P ), но эффективно решаемы в среднем случае.
3- Пессиланд: Существуют -полные проблемы среднего случая, но односторонних функций не существует. Это подразумевает, что мы не можем генерировать сложные случаи N P -полной проблемы с известным решением.
4- Minicrypt: существуют односторонние функции, но криптографические системы с открытым ключом невозможны
5- Криптомания: существуют криптографические системы с открытым ключом и возможна безопасная связь.
Какой мир предпочитают последние достижения в вычислительной сложности? Что является лучшим доказательством выбора?
Рассел Импальяццо, личный взгляд на сложность среднего случая , 1995
источник
Ответы:
Около года назад я совместно организовал семинар по сложности и криптографии: состояние миров Импальяццо , и слайды и видео на веб-сайте могут представлять интерес.
Короткий ответ заключается в том, что мало что изменилось в том смысле, что большинство исследователей все еще считают, что мы живем в «криптомании», и у нас все еще есть более или менее одно и то же свидетельство этого, и не так много прогресса в разрушении любого из миров друг для друга.
Возможно, наиболее важной частью новой информации является алгоритм Шора, который показывает, что, по крайней мере, если вы замените P на BQP, наиболее часто используемые криптосистемы с открытым ключом являются небезопасными. Но из-за криптосистем на основе решетки по умолчанию предполагается, что мы живем в криптомании даже в этом случае, хотя, возможно, консенсус здесь немного слабее, чем в классическом случае. Даже в классическом случае, кажется, существует гораздо больше доказательств существования односторонних функций («Minicrypt»), чем существование шифрования с открытым ключом («Cryptomania»). Тем не менее, учитывая усилия, которые люди потратили на попытки взломать различные криптосистемы с открытым ключом, есть и существенные доказательства для последней.
источник
Хороший вопрос, но ученые не смогли даже отделить «Алгоритмику» от остальных случаев, не говоря уже о том, чтобы решить, в каком именно мире мы живем.
Тем не менее, есть несколько исследовательских работ по этому вопросу. См. Например: О возможности обоснования криптографии на предположении, что 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
источник