1
$\begingroup$

zkSNARK is a technique composed with the following features:

  1. zk: zero-knowledge
  2. S: Succinct
  3. N: Non-interactive
  4. ARK: ARgument of Knowledge

Everywhere I look on the web for material on cryptographic arguments of knowledge I find techniques that mush these four features together. I am only interested in feature 4, that is a technique with no conditions on features 1, 2, or 3, for Alice to prove to Bob that she correctly performed a computation without Bob needing to perform the computation. Could I find literature under a more commonly used name for this technique than 'argument of knowledge'? Can you please point me to some literature on this technique?

I am curious which of the 4 features are at the core of the research in this area. Is it feature 1 that makes these cryptographic techniques so hard? or features 2 or 3? If the difficulty of current research is in solving a combination of features 1, 2, and 3, then shouldn't there exist simpler, more successful techniques that only need to solve feature 4? If so, I'd like to learn about these techniques. Ideally I'd get a response like "sure, if you don't need features 1, 2, or 3, simply ...".

Improve this question
$\endgroup$
6
  • $\begingroup$ an argument of knowledge is just proof that you know a witness that satisfies some relation, but with soundness holding only computationally. an argument of knowledge can then be thought of as a concept slightly weaker than a proof. there’s literature regarding proof systems but an argument of knowledge for a statement such as ‘i know x such that x^2 = 9 could be constructed by me just sending you the witness, be it 3 or -3. $\endgroup$
    – bekah
    Nov 13, 2017 at 23:26
  • $\begingroup$ computation soundness I think is what most techniques use and that is sufficient. But in your example, the verifier must check the witness by redoing the computation. I'm thinking of statements transformed into polynomials and having the prover convince the verifier that an input evaluates to an output without the verifier needing to evaluate the entire polynomial. $\endgroup$
    – Joseph Johnston
    Nov 14, 2017 at 8:10
  • $\begingroup$ Actually, given $x,y$ and checking whether $x^2=y$ is much, much easier than computing the discrete square root of some value. A verifier has to actually do some kind of verification - and that implies to evaluate some function, and there isn't much, which is faster than evaluating a simple polynomial, unless you transform the entire problem into a 3-SAT instance. $\endgroup$
    – tylo
    Nov 14, 2017 at 13:58
  • $\begingroup$ For the specific case of polynomials, there are efficient batch solutions, meaning that the prover can show that he correctly evaluated a polynomial P on $n$ distinct values, and the verification requires only a single evaluation of the polynomial, plus small operations per instance. But for efficient verification in single-instance settings, existing solutions are indeed more complex. $\endgroup$
    – Geoffroy Couteau
    Nov 14, 2017 at 14:08
  • $\begingroup$ @GeoffroyCouteau Could you please point to more info on this batch solution? $\endgroup$
    – Joseph Johnston
    Nov 14, 2017 at 18:19

1 Answer 1

Reset to default
0
$\begingroup$

The zero-knowledge property is not the core feature, in the sense that it's already very challenging to come up with a construction satisfying 2-4, and once it's done, adding zero-knowledge usually comes almost for free.

The property 4 is necessary, as it is implied by the property 3: if you want succinctness, you cannot hope to get unconditional soundness. The intuition between this is that if we have a proof of size $n$ for (say) 3-SAT, then we can slove 3-SAT in time $2^n$, by doing exhaustive search over possible proofs (the formal result is a bit more involved as it also considers interactive proofsm but that's the main idea). Therefore, $n$ cannot be much smaller than the witness size, otherwise we would get a subexponential time algorithm for 3-SAT (which would be a major breakthrough).

The property 2 is essentially the one you want to keep: succinctness usually means that the size of the proof and the computation time of the verifier are sublinear in the witness size. And this is exactly what is hard to get :)

Eventually, non-interactivity is usually not the core issue if you are ok with working in the random oracle model - although that's not always the case, most constructions of succinct proofs can be made non-interactive in the random oracle model.

From your question, I guess that what you are looking for is not a succinct proof for all NP language, but only for proofs of languages in P, where the verifier could in principle redo the entire computation himself, but this would be too expensive. Proving correct computation is easier than proving all statements in NP. This was studied a lot (I'm giving keywords here) in the context of delegation of computation. I think one of the seminal papers in this area (you can also look via Google Scholar the papers that cite it) is this one. A more recent, really cool paper in this area is this one. If you provide us more details about the exact specifications of your problem, I might also be able to give you more pointers; delegation is an active research area, with many papers providing efficient solutions in many settings.

Summing up, if you only want succinctness and languages in P, this is indeed easier than building a zk-snark for all of NP, but that remains far from easy.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I appreciate your clarification. I find this paper (which cites both papers you mentioned) appealing, and I like its concreteness. Is Eli considered a leader in the field? $\endgroup$
    – Joseph Johnston
    Nov 14, 2017 at 23:09
  • $\begingroup$ Eli Ben-Sasson? I do not know him personally, but he is a very good and respectable researcher, with strong contributions in the field. As I notice that you're mentioning the first author of the paper, it might be worth noting that in the crypto community, there is no such thing as "first author": the authors on the papers are ordered alphabetically, and no one is considered as the main author. $\endgroup$
    – Geoffroy Couteau
    Nov 15, 2017 at 0:02

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.