Given input string S, and transformation (i.e. computer program) T, is it possible to provide a succinct proof that another binary string S' is identical to the output T(S)?

By "succinct", I basically mean significantly less computationally intensive than repeating the original transformation. Also, I am ok with limiting the operations that can be performed by T to a specific set, but ideally this set should be Turing-complete.

I am encouraged by what I have read about zk-SNARKs that this type of thing is at least within the realm of the conceivable, but much of the underlying cryptography is currently unfamiliar territory to me, and it is not clear whether this type of proof is something I can use in my code, how much effort this would take, and how much compute power would be necessary for sizable input data sets.

Ideally, I'd like to leverage a reasonably friendly API to a well-written cryptographic library, but I am also willing to do a fair amount of the grunt work and open-source what I come up with.

Direct answers, as well as any helpful resources, will be much appreciated.

  • $\begingroup$ That seems possible for some T, but not any T. Is the former of interest ? $\endgroup$ – fgrieu Sep 23 '15 at 17:32
  • 3
    $\begingroup$ Yes, doing this with a Turing-complete set would appear to be equivalent to the halting problem. $\endgroup$ – poncho Sep 23 '15 at 18:06

Terminology: "public-coin" means the verifier does not need to keep any of its
randomness secret, and "private-coin" means "not necessarily public coin".

By IP = PSPACE, the correctness of operations can be interactively verified by a public-coin verifier whose runtime scales with the amount of space used for the transformation.
Such protocols can be modified so that additionally the verifier only needs an amount
of space that is logarithmic in the amount of space used for the transformation,
at the cost of becoming private-coin and the resulting protocol's number
being something like the square of the original protocol's number of rounds.

This paragraph is about protocols which emphasize the verifier using very little space.
Theorem 1 of Interactive Proofs for Muggles gives such a protocol in which the
verifier is public-coin. ​ These two papers apparently give up [public-coin]ness (at least
my search didn't find any reference to the property) in return for more efficiency gains.

I do not know of any way to combine the IP=PSPACE results with
the low-space results or even achieve any tradeoff between them.

Although you only asked about proofs, you mentioned SNARKs,
so the rest of this answer is about arguments rather than proofs.

By this paper, collision-resistant hash families are enough for all T with a public-coin
verifier and a constant number of rounds. ​ By this paper, fully-homomorphic encryption
is enough for all T with a private-coin verifier and 4 messages (2 in each direction).

Theorem 2 of Interactive Proofs for Muggles claims that a PIR scheme with bounded communication is enough for uniform low-depth T with a private-count verifier and
2 messages (1 in each direction). ​ However, as far as I can see, they also need
the PIR scheme to be 2-message (which all current candidates I'm aware of are).

This paper's results are similar to the previous paragraph. ​ Based on the title,
I imagine that SNARKs for C is the most practical candidate SNARK scheme.

| improve this answer | |

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.