Существуют ли алгоритмы криптографии с открытым ключом, которые доказуемо NP-трудно победить?[закрыто]

Question

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

Редактировать:

Пожалуйста, ознакомьтесь с разделом "Квантовые вычисления в теории вычислительной сложности" на статья вики о квантовых компьютерах. Это указывает на то, что класс задач, на которые могут ответить квантовые компьютеры (BQP), считается строго более простым, чем NP-полный.

Правка 2:

"Основано на NP-complete" - плохой способ выразить то, что меня интересует.

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

Answer 1

Я отвечаю на эту старую тему, потому что это очень распространенный и важный вопрос, и все ответы здесь неточны.

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

Здесь многое нужно прояснить, поэтому давайте начнем со значения "на основе NP-полной задачи". Общепринятой интерпретацией этого является:"может быть доказана безопасность в конкретной формальной модели, предполагая, что для NP-полных задач не существует алгоритмов с полиномиальным временем".Чтобы быть еще более точным, мы предполагаем, что не существует алгоритма, который всегда решает NP-полную задачу.Это очень безопасное предположение, потому что это действительно сложная задача для алгоритма - казалось бы, намного проще придумать алгоритм, который решает случайные случаи проблемы с хорошей вероятностью.

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

Теорема: Эта схема шифрования доказуемо безопасна, предполагая, что не существует алгоритма полиномиального времени для решение случайных экземпляров некоторой задачи X.

Обратите внимание на часть "случайные экземпляры".Для конкретного примера мы могли бы предположить, что не существует алгоритма полиномиального времени для разложения произведения двух случайных n-разрядных простых чисел на множители с некоторой хорошей вероятностью.Это сильно отличается (менее безопасно) от предположения, что не существует алгоритма с полиномиальным временем для всегда факторинг ВСЕ произведения двух случайных n-разрядных простых чисел.

Проблема "случайных экземпляров" по сравнению с "экземплярами наихудшего случая" - это то, что сбило с толку нескольких респондентов выше.Схемы шифрования типа McEliece основаны на совершенно особой случайной версии декодирования линейных кодов, а не на фактической версии наихудшего случая, которая является NP-полной.

Выход за рамки этой проблемы "случайных экземпляров" потребовал некоторых глубоких и красивых исследований в области теоретической информатики.Начиная с работы Миклоша Айтая, мы обнаружили криптографические алгоритмы, в которых предположение о безопасности является предположением "наихудшего случая" (safer) вместо предположения о случайном случае.К сожалению, наихудшие предположения относятся к задачам, которые, как известно, не являются NP-полными, и некоторые теоретические данные свидетельствуют о том, что мы не можем адаптировать их для использования NP-полных задач.Для тех, кому интересно, посмотрите "криптография на основе решетки".

Answer 2

Были предложены некоторые криптосистемы, основанные на NP-трудных задачах (таких как Меркл-Хеллман криптосистема, основанная на задаче о сумме подмножеств, и Naccache-криптосистема ранца Stern основываясь на проблеме с рюкзаком), но все они были сломаны.Почему это происходит?Лекция 16 Скотта Ааронсона Великие идеи в теоретической информатике говорит кое-что по этому поводу, что, я думаю, вы должны воспринять как окончательное.В нем говорится следующее:

В идеале мы хотели бы создать [Криптографический генератор псевдослучайных чисел] или криптосистему, безопасность которой была бы основана на NP-полной задаче.К сожалению, проблемы с NP-завершением всегда связаны с наихудшим случаем.В криптографии это было бы переведено в утверждение типа “там существует сообщение, которое трудно расшифровать”, что не является хорошей гарантией для криптографической системы!Сообщение должно быть трудно расшифруемым с подавляющей вероятностью.Несмотря на десятилетия усилий, до сих пор не было обнаружено способа связать наихудший случай со средним для NP-полных задач.И вот почему, если мы хотим получить криптосистемы, защищенные в вычислительном отношении, нам нужно сделать более сильные предположения, чем P≠ NP.

Answer 3

В 1998 году этот вопрос был открытым:

О возможности основывать криптографию на предположении, что P != NP автор: Одед Голдрайх, Реховот Исраэль, Шафи Голдвассер

Из аннотации:"Наш вывод заключается в том, что вопрос остается открытым".

-- Интересно, изменилось ли это за последнее десятилетие?

Редактировать:

Насколько я могу судить, вопрос все еще открыт, учитывая недавний прогресс в направлении ответа на то, что такого алгоритма не существует.

Ади Акавия, Одед Голдрайх, Шафи Голдвассер и Дана Мошковиц опубликовали эту статью в ACM в 2006 году: Об основывании односторонних функций на NP-твердости "Наши основные выводы заключаются в следующих двух отрицательных результатах".

Сайт в Стэнфорде Зоопарк сложности полезно расшифровать, что означают эти два отрицательных результата.

Answer 4

Хотя многие формы были нарушены, ознакомьтесь Меркл-Хеллман, основанный на форме NP-полной "Задачи о рюкзаке".

Answer 5

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

Я могу порекомендовать прочитать вводный раздел http://eprint.iacr.org/2008/521 а затем гоняться за ссылками на криптосистемы.

Кроме того, смотрите конспекты лекций по адресу http://www.cs.ucsd.edu /~даниэле/CSE207C/, и ищите ссылки для книги, если хотите.

Answer 6

Поиск в Google NP-complete и шифрования с открытым ключом приводит к ложным срабатываниям ...которые на самом деле небезопасны.Это мультяшный PDF- файл появляется, чтобы показать алгоритм шифрования с открытым ключом, основанный на задача о минимальном доминирующем множестве.Читая дальше , он затем признает , что лжет о том , что алгоритм безопасен ...основная проблема заключается в NP-завершении, но его использование в алгоритме PK не сохраняет сложности.

Еще одна ложноположительная находка Google: Криптоанализ криптосистемы Голдрайха-Голдвассера-Халеви из Crypto '97.Из аннотации:

На Crypto '97 Голдрайх, Голдвассер и Халеви предложили криптосистему с открытым ключом, основанную на задаче ближайшего вектора в решетке, которая, как известно, является NP-трудной.Мы показываем, что в конструкции схемы есть серьезный недостаток, который имеет два последствия:любой зашифрованный текст пропускает информацию об открытом тексте, и проблема дешифрования зашифрованных текстов может быть сведена к специальной задаче о приближении вектора, которая намного проще, чем общая задача.

Answer 7

Существует веб-сайт, который может соответствовать вашим интересам: Постквантовая криптография.

Answer 8

Вот мои рассуждения.Поправьте меня, если я ошибаюсь.

(i) `Взлом" криптосистемы обязательно является проблемой в NP и co-NP.(Взлом криптосистемы включает в себя инвертирование функции шифрования, которая является однозначной и вычислимой за полиномиальное время.Итак, учитывая зашифрованный текст, открытый текст представляет собой сертификат, который может быть проверен за полиномиальное время.Таким образом, запрос открытого текста на основе зашифрованного текста выполняется в NP и в co-NP.)

(ii) Если существует NP-сложная задача в NP и co-NP, то NP = co-NP.(Эта проблема была бы NP-полной и в co-NP.Поскольку любой NP-язык сводим к этому co-NP-языку, NP является подмножеством co-NP.Теперь используйте симметрию:любой язык L в co-NP имеет -L (его дополнение) в NP, откуда -L находится в co-NP ---то есть L = -L находится в NP.)

(iii) Я подумай что обычно считается, что NP != co-NP, так как в противном случае существуют доказательства полиномиального размера того, что булевы формулы невыполнимы.

Заключение:Гипотезы теории сложности подразумевают, что NP-жестких криптосистем не существует.

(В противном случае у вас возникает NP-сложная проблема в NP и co-NP, откуда NP = co-NP--- что считается ложным.)

Answer 9

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

(Ранее я неправильно говорил, что квантовые компьютеры ускорят решение NP-полных задач, но это неправда.Я остаюсь исправленным.)

Answer 10

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

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

В шифровании ElGamal или RSA для его взлома требуется взломать дискретный логарифм, поэтому посмотрите на это википедия Статья.

Не известно эффективного алгоритма для вычисления общих дискретных логарифмов logbg.Наивный алгоритм состоит в том, чтобы повышать b до все более высоких степеней k, пока не будет найдено искомое g;иногда это называют пробным умножением.Этот алгоритм требует, чтобы время выполнения было линейным по размеру группы G и, следовательно, экспоненциальным по количеству цифр в размере группы.Однако благодаря Питеру Шору существует эффективный квантовый алгоритм (http://arxiv.org/abs/quant-ph/9508027).

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

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

Широко распространено мнение, что они NP-полны, но, возможно, это невозможно доказать.Обратите внимание, что квантовые компьютеры могут эффективно взламывать криптографию!

Answer 11

Поскольку никто на самом деле не ответил на этот вопрос, я должен дать вам подсказку:"Макэлис".Проведите по нему несколько поисков.Это проверенный NP-жесткий алгоритм шифрования.Для этого требуется O (n ^ 2) времени на шифрование и дешифрование.У него тоже есть открытый ключ размером O (n ^ 2), что плохо.Но есть улучшения, которые снижают все эти границы.