17
$\begingroup$

Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that

  1. The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$.
  2. $\Psi(\mathcal C)$ has a solution if and only if $\mathcal C$ has a solution.
  3. Any solution $x$ of $\Psi(\mathcal C)$ can be efficiently converted into a solution of $\mathcal C$ using $r$.
  4. Without $r$, the solution $x$ (or any other property of $\Psi(\mathcal C)$) does not give any help in solving $\mathcal C$.

If there is such a $\Psi$, then it can be used to make others to solve computational challenges for us (with possibly replacing solving a CNF with other problems - I chose CNF because I wanted to make the problem more specific), in such a way that they cannot profit from a possible solution even if they know what problem we've used them to solve. For example, we could embed a factorization problem into a computer game, which enables players to play only if they work on our problem in the background, from time to time sending back proofs of computation. Maybe software can be even made "free" this way, where "free" hides a (possibly higher) cost in your parents' electricity bill.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Typo " ... does not give any help in solving $\mathcal C$" ?. By the way, if you're not worried about the structure of $\Psi$ i.e. the "player" has not access to $\Psi(\mathcal C)$ but only to the solution $x$, then a simple random permutation of the sign of the variables ($\pi_{\ell}(\ell_i) = \pm \ell_i$) and a random permutation of the indexes of the variables should make a solution $x$ of $\Psi(\mathcal C)$ totally unusable for solving $\mathcal C$. $\endgroup$ – Marzio De Biasi Dec 29 '17 at 11:31
  • $\begingroup$ @Marzio Thx, fixed typo. But I don't understand your comment - do you assume that the "player" has no access to $\Psi(\mathcal C)$ but only to $x$? It should be clear from the description that she has. $\endgroup$ – domotorp Dec 29 '17 at 12:55
  • $\begingroup$ yes the simple "shuffle literals and variable indexes" surely works if player has no access to the structure of $\Psi(\mathcal C)$ (mine was only a quick comment). But perhaps the "shuffle" idea could be extended in this way: if $\mathcal C$ is 3-CNF then there are only $(2n)^3$ possible distinct clauses and knowing $\Psi(\mathcal C)$ (a shuffled version of $\mathcal C$) could be helpful only knowing an efficient way to find an isomorphism between $\Psi(\mathcal C)$ and $\mathcal C$. $\endgroup$ – Marzio De Biasi Dec 29 '17 at 13:16
  • $\begingroup$ @Marzio As things are heading, probably (hyper)graphisomorphism is solvable fast. $\endgroup$ – domotorp Dec 29 '17 at 19:27
  • 1
    $\begingroup$ Have look at the encrypted complete set conjecture. It suggests that your proposal is plausible. It states that there is injective length-increasing $2^{n^\epsilon}$-secure one-way function $f$ such that SAT and $f(SAT)$ are not p-isomorphic. $\endgroup$ – Mohammad Al-Turkistany Dec 30 '17 at 18:03
5
+100
$\begingroup$

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-SAT are encryptable.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ And in the follow up work they conclude that NP-complete problems are unlikely to be encryptable! doi.org/10.1016/0022-0000(89)90018-4 These papers are just what I was looking for. I wonder why I can understand them so much better than recent results in cryptography - maybe the field has diverged too much from complexity theory since then... $\endgroup$ – domotorp Feb 10 '18 at 13:03
8
$\begingroup$

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 CNF into another CNF, but it does work for the intended application.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Afaik, homomorphic encryption is for making some computation on some numbers. How exactly would you use it for my problem? $\endgroup$ – domotorp Dec 29 '17 at 20:46
  • $\begingroup$ FHE is defined for boolean circuits. Treat the CNF instance as a bit vector. Given an input size, you can construct a boolean circuit that outputs an assignment if there is any (see cs.stackexchange.com/q/72289/627). $\endgroup$ – didest Dec 29 '17 at 21:41
  • $\begingroup$ I think that the difference is that in your solution, while the privacy is preserved, the encoding is quite costly compared to the task we want to solve. I would like to encode in polynomial time an exponential amount of work. $\endgroup$ – domotorp Dec 30 '17 at 13:47
  • $\begingroup$ @domotorp I understand. There is a way to use FHE without circuits, see eprint.iacr.org/2013/229.pdf $\endgroup$ – didest Dec 30 '17 at 14:31
  • 4
    $\begingroup$ As more and more users are upvoting your answer, maybe it contains something that I've missed. Are you claiming right now that it works for my question or just for the application? I've also looked at the paper, but it's non so easy to grasp. Could you tell me which specific result/theorem would be applicable in my case? $\endgroup$ – domotorp Feb 9 '18 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.