<p>The application you mention is called "proof of useful work" in the literature, see for instance <a href="https://eprint.iacr.org/2017/203.pdf" rel="noreferrer">this article</a>.</p>

<p>You can use a <a href="https://en.wikipedia.org/wiki/Homomorphic_encryption#Fully_homomorphic_encryption" rel="noreferrer">fully homomorphic encryption</a> scheme (where the plaintext is the CNF instance) to delegate the computation to an untrusted party without disclosing the input.</p>

<p>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.</p>

CC BY-SA 3.0
2017-12-29T20:46:28.293Z
Afaik, homomorphic encryption is for making some computation on some numbers. How exactly would you use it for my problem?
domotorp
CC BY-SA 3.0
2017-12-29T21:41:59.473Z
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
CC BY-SA 3.0
2017-12-30T13:47:08.630Z
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
CC BY-SA 3.0
2017-12-30T14:31:58.570Z
@domotorp I understand. There is a way to use FHE without circuits, see https://eprint.iacr.org/2013/229.pdf
didest
CC BY-SA 3.0
2017-12-30T18:29:53.873Z
@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
CC BY-SA 3.0
2017-12-30T19:49:46.553Z
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
CC BY-SA 3.0
2017-12-30T20:22:10.200Z
@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
CC BY-SA 3.0
2018-02-09T13:13:49.493Z
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
CC BY-SA 3.0
2017-12-29T19:17:53.490Z
2017-12-30T21:40:31.610Z
2017-12-30T21:40:31.610Z
didest
<p>Feigenbaum in, <a href="https://link.springer.com/chapter/10.1007%2F3-540-39799-X_38" rel="noreferrer">Encrypting Problem Instances</a>, 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.</p>

CC BY-SA 3.0
2018-02-10T13:03:46.550Z
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
CC BY-SA 3.0
2018-02-10T08:24:32.730Z
2018-02-10T19:26:07.560Z
2018-02-10T19:26:07.560Z
Mohammad Al-Turkistany
<p>Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that</p>

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

<p>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.</p>

CC BY-SA 3.0
2017-12-29T11:31:30.203Z
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
CC BY-SA 3.0
2017-12-29T12:55:56.423Z
@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
CC BY-SA 3.0
2017-12-29T13:16:20.667Z
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
CC BY-SA 3.0
2017-12-29T19:27:57.280Z
@Marzio As things are heading, probably (hyper)graphisomorphism is solvable fast.
domotorp
CC BY-SA 3.0
2017-12-30T13:04:30.667Z
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
CC BY-SA 3.0
2017-12-30T13:50:51.390Z
@Diego I don't see how that would help. For example, suppose that $\mathcal C$ had only one solution to start with.
domotorp
CC BY-SA 3.0
2017-12-30T14:40:55.300Z
@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
CC BY-SA 3.0
2017-12-30T18:03:16.377Z
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
CC BY-SA 3.0
2017-12-30T20:35:59.613Z
@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
CC BY-SA 3.0
2017-12-30T20:41:35.933Z
Easy, $f$ could be a trapdoor one-way function.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-12-31T15:51:04.913Z
@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
CC BY-SA 3.0
2017-12-31T15:59:15.137Z
Your post is very interesting and it led me to come up with candidate one-way function $\Psi$ :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2018-01-03T23:04:30.803Z
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
CC BY-SA 3.0
2018-01-04T08:59:38.570Z
Since $\mathcal C$ is a CNF, it can be solved in exponential time.
domotorp
CC BY-SA 3.0
2018-01-04T17:59:17.710Z
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
CC BY-SA 3.0
2018-01-04T20:27:37.617Z
Kind of, depending on your definition of impossible.
domotorp
<cc.complexity-theory><cr.crypto-security><one-way-function><cryptojacking>
Is it possible to encrypt a CNF?
domotorp
# Is it possible to encrypt a CNF?

(Asked by: username_0 on 2017-12-29)

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.

**Tags:** cc.complexity-theory, cr.crypto-security, one-way-function, cryptojacking
> **Comments:**
> **username_1**: 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$.  
> **username_0**: @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.  
> **username_1**: 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$.  
> **username_0**: @Marzio As things are heading, probably (hyper)graphisomorphism is solvable fast.  
> **username_2**: 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.  
> **username_0**: @Diego I don't see how that would help. For example, suppose that $\mathcal C$ had only one solution to start with.  
> **username_2**: @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.  
> **username_3**: 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.  
> **username_0**: @Mohammad This interesting conjecture indeed might be related, but I don't see why 3., or even 4. would hold for such an $f$.  
> **username_3**: Easy, $f$ could be a trapdoor one-way function.  
> **username_0**: @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.  
> **username_3**: Your post is very interesting and it led me to come up with candidate one-way function $\Psi$ :)  
> **username_3**: Regarding 4,  Are you demanding that it is impossible to solve $\mathcal C$ even in exponential time (if $\mathcal r$ is not given)?  
> **username_0**: Since $\mathcal C$ is a CNF, it can be solved in exponential time.  
> **username_3**: 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)?  
> **username_0**: Kind of, depending on your definition of impossible.  

---

## 2 answers

### Answer by username_3 on 2018-02-10. Score: 6 | Accepted answer

Feigenbaum in, [Encrypting Problem Instances](https://link.springer.com/chapter/10.1007%2F3-540-39799-X_38), 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.

> **Comments:**
> **username_0**: 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...  

---

### Answer by username_2 on 2017-12-29. Score: 8

The application you mention is called "proof of useful work" in the literature, see for instance [this article](https://eprint.iacr.org/2017/203.pdf).

You can use a [fully homomorphic encryption](https://en.wikipedia.org/wiki/Homomorphic_encryption#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.

> **Comments:**
> **username_0**: Afaik, homomorphic encryption is for making some computation on some numbers. How exactly would you use it for my problem?  
> **username_2**: 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).  
> **username_0**: 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.  
> **username_2**: @domotorp I understand. There is a way to use FHE without circuits, see https://eprint.iacr.org/2013/229.pdf  
> **username_2**: @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.  
> **username_0**: 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!  
> **username_2**: @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.  
> **username_0**: 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?  

---

