8

The application you mention is called "proof of useful work" in the literature, see for instance this article. You can use a fully homomorphic encryption scheme (where the plaintext is the CNF instance) to delegate the computation to an untrusted party without disclosing the input. This doesn't answer exactly your question, since such scheme doesn't map a ...


8

(Note: Andreas Björklund suggested a solution in the comments that I believe is better than the one described below. See http://eprint.iacr.org/2017/203, by Ball, Rosen, Sabin, and Vasudevan. In short, they give proofs of work based on problems like Orthogonal Vectors whose hardness is well understood and to which many problems (e.g., k-SAT) can be reduced ...


5

Feigenbaum in, Encrypting Problem Instances, proposes a definition (Def. 1) of encryption function for NP-complete problems which satisfies your requirements. She proves that the NP-complete problem Comparative Vector Inequalities admits such encryption function. She concludes with the main theorem that all NP-complete problems that are p-isomorphic to CNF-...


Only top voted, non community-wiki answers of a minimum length are eligible