Нет. Мало того, что нет общий способ построить криптосистему на основе проблемы принятия решения, не существует ни одной известной проблемы принятия решения, которая:
- является NP-полным, и
- мы можем построить криптографию из
«Любая криптография» может показаться несколько расплывчатой, но ее можно довольно легко конкретизировать — известно, что большинство примитивов с симметричным ключом (односторонние функции, псевдослучайные функции/генераторы и непредсказуемые функции) эквивалент, в том смысле, что если у вас есть один (скажем, OWF), вы можете легко построить другие, и наоборот.
Почему на основе этого предположения не была построена криптография? Основной причиной является «тривиальная теорема», которая:
Если существует безопасный (OWF/PRG/PRF/UF), то $P\neq НП$
Это связано с тем, что для любого разумного понятия «безопасность» проблема взлома OWF/PRG/PRF/UF заключается в следующем:
- Легко в NP («угадай» секретный ключ, тогда любое понятие безопасности упрощается)
- Не в П (иначе боеспособный противник мог бы его сломать, так что он не был бы "надежным").
Помимо этого, есть (связанный) вопрос о
Как мне использовать знание конкретной сложной проблемы для построения криптографии?
Ответ несколько сложен. Если вы можете построить стандартный криптографический примитив (PRG/PRF/OWF/UF или OWF с лазейкой), все очень быстро становится очень простым.
Кроме того, я хотел бы отметить, что если вы можете построить «стандартные примитивы», которые являются «гомоморфными», вещи также становятся довольно простыми.
Но общая история все еще прорабатывается — шифрование на основе решетки было впервые предложено примерно 25 лет назад, но потребовалось примерно десятилетие назад, чтобы были разработаны подписи на основе решетки.
Это означает, что знание того, как разработать шифрование (с открытым ключом), не привело к подписям «бесплатно» (несмотря на то, что PKE является «более сложным примитивом для создания» в определенном формальном смысле).
Был достигнут некоторый прогресс в понимании того, какие общие конструкции получаются при построении определенных примитивов (это то, что делает статья, на которую я ссылаюсь), но все это довольно недавно.
