Можно ли преобразовать CNF в другой CNF такой, чтобы
- Функция может быть вычислена за полиномиальное время из некоторого секретного случайного параметра .
- имеет решение тогда и только тогда, когда имеет решение.
- Любое решение из может быть эффективно преобразовано в решение с помощью .
- Без , решение (или любое другое свойство ) не дает какой - либо помощи в решении .
Если есть такой , то его можно использовать, чтобы заставить других решать вычислительные задачи для нас (возможно, заменив решение CNF другими проблемами - я выбрал CNF, потому что хотел сделать проблему более конкретным), в такой ситуации. таким образом, что они не могут извлечь выгоду из возможного решения, даже если они знают, какую проблему мы использовали для их решения. Например, мы могли бы встроить проблему факторизации в компьютерную игру, которая позволяет игрокам играть, только если они работают над нашей проблемой в фоновом режиме, время от времени отправляя доказательства вычисления. Возможно, программное обеспечение можно даже сделать «бесплатным» таким образом, когда «бесплатное» скрывает (возможно, более высокую) стоимость в счетах за электричество ваших родителей.
Ответы:
Фейгенбаум в книге « Шифрование экземпляров задачи» предлагает определение (определение 1) функции шифрования для задач, завершающих NP, которая удовлетворяет вашим требованиям. Она доказывает, что NP-полная задача «Сравнительные векторные неравенства» допускает такую функцию шифрования. Она завершает основную теорему о том, что все NP-полные задачи, p-изоморфные CNF-SAT, являются шифруемыми.
источник
Упоминаемое вами приложение в литературе называется «доказательством полезной работы», см., Например, эту статью .
Вы можете использовать полностью гомоморфную схему шифрования (где открытый текст - это экземпляр CNF), чтобы делегировать вычисления ненадежной стороне без раскрытия ввода.
Это не отвечает точно на ваш вопрос, так как такая схема не отображает CNF в другой CNF, но она работает для предполагаемого применения.
источник