18

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.

domotorp
  • 13,931
  • 37
  • 93
  • 2
    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$. – Marzio De Biasi Dec 29 '17 at 11:31
  • @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. – domotorp Dec 29 '17 at 12:55
  • 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$. – Marzio De Biasi Dec 29 '17 at 13:16
  • @Marzio As things are heading, probably (hyper)graphisomorphism is solvable fast. – domotorp Dec 29 '17 at 19:27
  • Maybe a way to circumvent the isomorphism problem would be to use the isolation lemma on top of the shuffling, so that $\Psi(\mathcal C)$ has at most one (shuffled) solution. – didest Dec 30 '17 at 13:04
  • @Diego I don't see how that would help. For example, suppose that $\mathcal C$ had only one solution to start with. – domotorp Dec 30 '17 at 13:50
  • @domotorp even in that case $\Psi(\mathcal C)$ would be different from $\mathcal C$. The isolation algorithm is randomized, and I'm not sure how easy would it be to compare the CNFs. – didest Dec 30 '17 at 14:40
  • 1
    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. – Mohammad Al-Turkistany Dec 30 '17 at 18:03
  • @Mohammad This interesting conjecture indeed might be related, but I don't see why 3., or even 4. would hold for such an $f$. – domotorp Dec 30 '17 at 20:35
  • Easy, $f$ could be a trapdoor one-way function. – Mohammad Al-Turkistany Dec 30 '17 at 20:41
  • @Mohammad I don't think that helps. In case of 3., just because $\Psi(\mathcal C)$ can be converted, it doesn't mean that the solution can be also inverted. In case of 4., finding $x$ might have already cost an exponential amount of time, and one-way functions only resist polynomial time attacks. – domotorp Dec 31 '17 at 15:51
  • Your post is very interesting and it led me to come up with candidate one-way function $\Psi$ :) – Mohammad Al-Turkistany Dec 31 '17 at 15:59
  • Regarding 4, Are you demanding that it is impossible to solve $\mathcal C$ even in exponential time (if $\mathcal r$ is not given)? – Mohammad Al-Turkistany Jan 03 '18 at 23:04
  • Since $\mathcal C$ is a CNF, it can be solved in exponential time. – domotorp Jan 04 '18 at 08:59
  • Oops my mistake, I mean, Are you demanding that it is impossible to solve $\mathcal C$ unless exponential time is allowed (in case $r$ is not given)? – Mohammad Al-Turkistany Jan 04 '18 at 17:59
  • Kind of, depending on your definition of impossible. – domotorp Jan 04 '18 at 20:27

2 Answers2

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

didest
  • 1,551
  • 16
  • 25
  • Afaik, homomorphic encryption is for making some computation on some numbers. How exactly would you use it for my problem? – domotorp Dec 29 '17 at 20:46
  • 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 https://cs.stackexchange.com/q/72289/627). – didest Dec 29 '17 at 21:41
  • 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. – domotorp Dec 30 '17 at 13:47
  • @domotorp I understand. There is a way to use FHE without circuits, see https://eprint.iacr.org/2013/229.pdf – didest Dec 30 '17 at 14:31
  • @domotorp oh, one thing to note: the agent who generates the CNF only needs to encrypt the CNF. The circuit generation is done by the agent who evaluates the circuit. So avoiding circuits just improves the runtime by a constant. – didest Dec 30 '17 at 18:29
  • I went through this paper but could only find results related to encoding for Turing-machines that run in polynomial time. If you have some specific result that you think could be of use for my question, please let me know which one you have in mind! – domotorp Dec 30 '17 at 19:49
  • @domotorp you're right, I forgot about that detail. But my latter comment still holds: circuit generation and evaluation are run by the untrusted party, so the encryption scheme doesn't impact the time complexity of the protocol. – didest Dec 30 '17 at 20:22
  • 4
    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? – domotorp Feb 09 '18 at 13:13
6

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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 1
    And in the follow up work they conclude that NP-complete problems are unlikely to be encryptable! https://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... – domotorp Feb 10 '18 at 13:03