5
$\begingroup$

Quesstion:

Suppose Peggy claims to have a Turing Machine (TM) such that when the tape starts with I the machine will halt with tape O for one or more (I, O) pairs.

Peggy would like to prove to Victor that she know the TM, but would like to convince him via a Zero-Knowledge Proof (ZKP).

Is there an algorithm $\Pi$ that Peggy and Victor can run that will accomplish this? If so what is it?

Example:

Let's say that I write a function $f(x)$ in some programming language. Now I would like to prove to you that $\forall x f(x) = 2 x^2-x+5$ but I don't want to disclose any information about the source code. (I know that this is a silly example but you could imagine that $f(x)$ is a much more complicated function)

Ideas:

Maybe there is a way to convert this into another problem that we have a algorithm to proof in zero-knowledge

Clarifications:

Let's start with an application for an example.

Peggy is a student and Victor is a teacher. Victor assigns a homework in which Peggy is supposed to design a TM to compute some function, $f(x)$. Peggy designs a very elegant solution and no longer wants to disclose her TM to Victor. (Maybe Peggy is afraid that Victor will steal her idea) Instead she wants to convince him that she did the assignment via a ZKP so she can get credit.

Another example is proprietary software. A company wants to convince its users that their software does what the users expects it to so. One popular solution is currently to release the software (e.g. open-source), but this allows anyone to easily steal the software. An alternate could be to provide a ZKP that the software satisfies certain properties.

What information do Peggy and Victor have?

  • Peggy and Victor know all the (I,O) pairs.
  • Peggy knows some TM such that $\forall i \forall o ((i \in {\bf I} \wedge o \in {\bf O}) \rightarrow {\bf TM}(i) = o)$
  • Algorithm $\Pi$ should ideally run in polynomial time of the runtime of the TM
  • Ideally Victor should not learn the number of states of the TM or the number of steps needed to compute the function, but if there is an algorithm that works except for these properties that would still be great.
    • Learning some upper bound of the number of states or runtime is fine though
  • If needed Peggy and Victor have access to a Random Oracle
Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Victor hands Peggy several input combinations, and Peggy hands Victor the output that shows the TM halted. Peggy continues this exchange until Victor is satisfied. This probably isn't the best example, but hopefully it gives some context for those better able to answer than I. Also, please state whether this is a homework assignment or not, and please include the work you've done to try answering your own question. $\endgroup$
    – floor cat
    Commented Jun 8, 2017 at 18:51
  • 2
    $\begingroup$ @floorcat: that is not a solution; it's not zero knowledge (in that Victor learns the output of several inputs), and in addition, there's nothing preventing Peggy from making up the outputs (rather than running the TM) $\endgroup$
    – poncho
    Commented Jun 8, 2017 at 19:10
  • 3
    $\begingroup$ If the list of (I, O) pairs is finite, and if the list is public (known to both Peggy and Victor), then Peggy needn't prove anything; it's trivial to put together a turing machine that does a fixed mapping, and so she needn't prove anything. So, how are you going to extend what Peggy needs to prove in order to make this nontrivial? $\endgroup$
    – poncho
    Commented Jun 8, 2017 at 21:11
  • $\begingroup$ @poncho I assumed Victor would know whether his input is valid or not, and what the expected output is. The analogy I'm working from is as if Victor hands Peggy two cans, one of coca cola and the other pepsi as a way to challenge if Peggy can taste the difference. Along these lines, Victor is able to give inputs to Peggy which he knows will not halt, as a way to test Peggy's claims. $\endgroup$
    – floor cat
    Commented Jun 8, 2017 at 21:19
  • 1
    $\begingroup$ @floorcat: This is not an assignment, I came up with this on my own. $\endgroup$
    – edggy
    Commented Jun 10, 2017 at 0:06

1 Answer 1

Reset to default
7
$\begingroup$

In principle, any language in NP can be proven in zero knowledge. Furthermore, any language in NP can be proven with a zero knowledge proof of knowledge. Thus, in order to answer your question, the only issue remaining is whether or not the language you have defined is in NP. In order to verify this, one needs to define a relation that can be verified in polynomial time. The way you have formalized the question is such that this is not the case. In particular, you have not included a requirement that the machine run in polynomial time. However, even if you do add this, it has to be done carefully. If you define: $(I,O)\in L$ iff there exists a polynomial time TM $M$ such that $M(I)=O$, then what you are really writing is $(I,O)\in L$ iff there exists a polynomial $q$ and a TM $M$ that runs in time $q(|x|)$ upon input $x$ such that $M(I)=O$. However, in this case there is no fixed polynomial-time upper bound on the running-time of the verifier (since the polynomial $q$ in the witness can be any polynomial). This can be solved by either defining the language $L_q$ to be $(I,O)\in L_q$ iff there exists a TM $M$ running in time $q$ such that $M(I)=O$. Alternatively, one can define $(I,O,1^t)\in L$ iff there exists a TM $M$ such that $M(I)$ outputs $O$ within $t$ steps. Since these languages are in NP, you can prove a zero-knowledge proof of knowledge and get what you want.

I note that in fact any language in $IP=PSPACE$ can be proven in zero knowledge, but then the proof isn't efficient.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ If Peggy needs to declare $q$, it's not zero-knowledge... $\endgroup$
    – poncho
    Commented Jun 9, 2017 at 16:33
  • 2
    $\begingroup$ If $q$ is part of the language definition then it is zero knowledge. $\endgroup$
    – Yehuda Lindell
    Commented Jun 11, 2017 at 5:19
  • $\begingroup$ True, however it does mean you've changed the problem. Now, I suspect that the problem in its original form is, in fact, unsolvable (however, I haven't been able to prove it), and so answered a slightly different problem is not unreasonable, but you ought to be clear that you're doing so $\endgroup$
    – poncho
    Commented Jun 11, 2017 at 12:40
  • $\begingroup$ @poncho I don't understand. I explicitly wrote in my answer that the way the problem has been stated it is not in NP. Thus, there is certainly no efficient-prover solution to the problem. Regarding whether or not it's possible in PSPACE, I am not sure. $\endgroup$
    – Yehuda Lindell
    Commented Jun 12, 2017 at 4:28
  • $\begingroup$ One thing I was thinking was what was the variable that the solution is polynomial (or NP) in? If we naively set it the size of the unary input then we can't solve this in NP. But if we set in in regards to the runtime of the TM then it is feasible to do it in NP. For example if Peggy had a TM that solved a problem in EXPTIME even just to show Victor would take too much time, let alone in ZK. But if we do the latter then there might be a solution. It makes sense too since we want to measure the ZK protocol with respect to the non-ZK counterpart i.e. just giving the TM to Victor $\endgroup$
    – edggy
    Commented Jul 16, 2017 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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