Почему не было алгоритма шифрования, основанного на известных проблемах NP-Hard?

109

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

Кен Ли
источник

Ответы:

76

PNPPNP

Отличное чтение - классика Рассела Импальяццо, «Персональный взгляд на сложность среднего случая» , 1995.

Отличный обзор - Сложность среднего случая Богданова и Тревизана, Основы и тенденции в теоретической информатике. 2, № 1 (2006) 1–106

Мухаммед Аль-Туркистани
источник
1
Разве нам не нужна твердость в лучшем случае? В конце концов, все наши ключи должны быть в безопасности. Или мы можем эффективно (и действенно) предотвратить лучший случай?
Рафаэль
7
NP-hard
@ Рафаэль, этого должно быть достаточно, если вероятность получить нежелательный «хороший» случай достаточно мала. Если, скажем, меньше, чем вероятность угадать правильный ключ желаемого «плохого» случая, этот риск следует считать приемлемым ИМХО.
quazgar
49

Там были.

Одним из таких примеров является криптосистема Мак-Элиса, основанная на сложности декодирования линейного кода.

Второй пример - NTRUEncrypt, основанный на кратчайшей векторной проблеме, которая, как я считаю, известна как NP-Hard.

Другой - криптосистема ранца Меркле-Хеллмана, которая была взломана.

Примечание: я понятия не имею, сломаны ли первые два / насколько они хороши. Все, что я знаю, это то, что они существуют, и я получил их от поиска в сети.

Арьябхата
источник
6
Для целей криптоанализа McEliece, вероятно, не следует рассматривать как одну криптосистему; для каждого класса эффективно декодируемых линейных кодов, которые вы подключаете, вы обязательно должны придумать другую стратегию, чтобы сломать его. Он был сломан для некоторых классов кодов, но (как говорится в статье в Википедии) не для кодов Гоппы, которые были первоначальным предложением Мак-Элиса.
Питер Шор
Из этого списка я бы сказал, что NTRU выглядит наиболее многообещающе, его еще предстоит всесторонне протестировать, как тестировали RSA на основе того, о чем я читал до сих пор.
Кен Ли
Криптосистема Меркля-Хеллмана не является подходящим примером. Вершины рюкзака Меркля-Хеллмана являются лишь подмножеством всех векторов рюкзака, поэтому задача о рюкзаке Меркля-Хеллмана не может быть NP трудной. Я не думаю, что это NP-жесткий, по крайней мере, я не знаю ни одной бумаги, которая показывает это.
чудо173
25

Я могу думать о четырех основных препятствиях, которые не являются полностью независимыми:

  • NP-твердость только дает вам информацию о сложности в пределе . Для многих NP-полных задач существуют алгоритмы, которые решают все интересующие случаи (в определенном сценарии) достаточно быстро. Другими словами, для любого фиксированного размера задачи (например, данного «ключа») проблема не обязательно является сложной только потому, что она NP-сложная.
  • NP-твердость учитывает только худшее время. Многие, даже большинство случаев могут быть легко решены с помощью существующих алгоритмов. Даже если бы мы знали, как охарактеризовать трудные случаи (агаик, мы не знаем), нам все равно пришлось бы их находить.
  • 2n(n1)nn
  • Вам нужна какая-то обратимость. Например, любое целое число однозначно описывается его первичной факторизацией. Изображение мы хотели бы использовать TSP в качестве метода шифрования; учитывая все кратчайшие туры, можете ли вы (заново) построить график, из которого они были получены уникальным образом?

Обратите внимание, что у меня нет опыта в криптографии; это просто алгоритмические соотв. Теоретические сложности возражения.

Рафаэль
источник
Отличное резюме. Но учтите, что BQP-жесткость имеет те же предостережения, что и ваши первые два пункта.
Митч
14

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

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

Имея это в виду, легко построить примитивную криптосистему, основанную на любой односторонней перестановке люка.

  1. Алиса раздает публике одностороннюю перестановку и держит люк при себе.
  2. Боб поместил свой вход в перестановку и передал результат Алисе.
  3. Алиса использует люк, чтобы инвертировать перестановку с выводом Боба.

PNP

PNPNPINPNPNPINP

NPNPNP

Хайнц Фидлер
источник
RSA, да, это функция люка. Я не уверен, что dlog - это TDF (в одну сторону)
111
Если бы NP-промежуточные задачи были NP-сложными, они были бы NP-полными, противоречие.
Мирия
0

Просто чтобы дать эвристический аргумент, основанный на практическом опыте.

Почти все случаи, почти все NP-полные проблемы, легко решить. Есть проблемы, когда это не так, но их трудно найти, и трудно быть уверенным, что у вас такой класс.

Это встречалось на практике несколько раз, когда люди пытаются написать генераторы случайных задач для какого-нибудь известного NP-полного класса, такого как Constraint Programming, SAT или Traveling Salesman. Позднее кто-то находит метод решения почти всех случаев, которые генератор случайных чисел производит тривиально. Конечно, если бы это было так для системы шифрования, у нас были бы серьезные проблемы!

Крис Джефферсон
источник
-1

Криптосистемы Меркля-Хеллмана основаны на бинарных ранцевых задачах (сумма подмножеств).

user13675
источник
Можете ли вы дать ссылку?
Рафаэль
" en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem ", а также монография: постквантовая криптография (Springer).
user13675