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

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

Это был открытый вопрос в 1998 году:

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

Из реферата: "Мы пришли к выводу, что вопрос остается открытым".

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

Edit:

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

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

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

Ответ 4

В то время как многие формы были сломаны, проверьте Merkle-Hellman на основе формы NP-полной "проблемы с рюкзаком".

Ответ 5

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

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

Также см. примечания к лекции в http://www.cs.ucsd.edu/~daniele/CSE207C/ и читайте ссылки для книги, если хотите.

Ответ 6

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

Еще один ложноположительный Google find: Криптоанализ криптосистемы Goldreich-Goldwasser-Halevi от Crypto'97. Из реферата:

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

Ответ 7

Существует веб-сайт, который может иметь отношение к вашим интересам: Post-Quantum Cryptography.

Ответ 8

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

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

(ii) Если в NP и co-NP есть 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 --- который считается ложным.)

Ответ 9

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

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

Ответ 10

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

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

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

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

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

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

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

Ответ 11

Так как никто действительно не ответил на вопрос, я должен дать вам намек: "McEliece". Сделайте некоторые поиски на нем. Его проверенный алгоритм шифрования NP-Hard. Нужно O (n ^ 2) время шифрования и дешифрования. Он также имеет открытый ключ размера O (n ^ 2), что плохо. Но есть улучшения, которые снижают все эти границы.