4
$\begingroup$

I have a couple of questions on ZK-SNARK:

  1. Based on what I understand, a ZK-SNARK is an "Argument of knowledge". That means that it should be equivalent to Sigma Protocols like Fiat-Shamir and Pederson committments, RSA Accumulators, and even attribute-based encryption, correct?

  2. I've read in a few places, like Prof. Bill Buchanan's intro, that a ZK-SNARK could be used to "delegate" a function in order to have a 3rd-party (call her Alice) to calculate a function without her knowing what she is calculating. For example, we can calculate the function aX + bY, if X and Y are private to Alice. We can do this by using homomorphic encryption around Enc(aX + bY), to which we can calculate Enc(aX) * Enc(aY), given that a and b are public. In this case, we will know the result of aX + bY without knowing X and Y. Is that a correct representation of Zk-snark (AKA: Secure Function Evaluation)?

Did I mix up too many categories together?

Many thanks in advance

$\endgroup$

1 Answer 1

5
$\begingroup$

Did I mix up too many categories together?

Yes :)

A ZK-SNARK is a method to let a prover demonstrate to a verifier that some statement is true (e.g. "this ciphertext encrypts a number between 3 and 5"), with the following properties:

  • correctness and soundness: (assuming the prover has bounded computational power) the proof is convincing if and only if the statement is true
  • zero-knowledge: the proof only leaks the information that the statement is true, nothing more
  • non-interactivity: the proof is a single message from the prover to the verifier
  • succinctness: the size of the proof is much smaller than the size of the witness for the statement (e.g. in my previous example, the "witness" could be the secret key of the encryption scheme), and verifying the proof is much faster than directly checking the statement, even given the witness.

A $\Sigma$-protocol is a zero-knowledge proof as well, but with very different properties:

  • unlike a ZK-SNARK, it is interactive (three moves)
  • unlike a ZK-SNARK, it is not fully zero-knowledge (but only honest-verifier zero-knowledge)
  • unlike a ZK-SNARK, it is not succinct

On the positive side, $\Sigma$-protocols exist unconditionally (ZK-SNARK require ultra strong assumptions) and do not need any trusted setup (ZK-SNARKs require a common reference string).

Now, regarding the many things you mentioned:

  • Fiat-Shamir is not a $\Sigma$-protocol, it is a technique to transform a $\Sigma$-protocol into a non-interactive zero-knowledge proof (NIZK). Note that $\Sigma$-protocol + Fiat-Shamir does not give a ZK-SNARK, because the NIZK is not succinct in general.
  • Pedersen commitments are not $\Sigma$-protocols, they are commitments - a "cryptographic box" in which you can put a message so that it stays hidden, but which cannot be opened to a different message. They are used a lot to construct the statements we want to prove with $\Sigma$-protocols in high level applications. Typically, you will put many secret values involved in the protocol in these "cryptographic boxes", and use $\Sigma$-protocols to demonstrate that these (hidden) values satisfy some relations.
  • ZK-SNARKs are not "used to delegate functions", but they are useful when you have a delegation scheme and want to make sure that the server was honest. However, we usually don't really care about the ZK part for this application; what we care about is the succinctness. Here is a typical example: there is a super complex function $f$, you have $x$ and want to compute $f(x)$, but it costs too much. So, you send $x$ to a powerful server, who computes $y = f(x)$ for you and send you the result. But you do not trust the server, so to convince you that the result is correct, the server also sends you a proof that the statement $y = f(x)$ is correct. Here, the core property for this scheme to be useful is that checking the proof should be much faster than computing $f(x)$ yourself (otherwise there would be no point in delegating the computation in the first place).

Note that $\Sigma$-protocols are not succinct, so they are useless for the application to delegation of computation. Secure function evaluation has also nothing to do with that. Secure function evaluation is used in delegation when you want to hide the input $x$ from the server (so the server should compute $f(x)$ for you without seeing $x$). This is an orthogonal problem; what ZK-SNARK solve is the problem of letting the server prove that he computed the right value. This can be done independently of whether the server is doing the computation "blindly" (using some secure function evaluation technique, e.g. homomorphic encryption) or in the clear. Hence, SFE and ZK-SNARKs are just completely different, both can be used to solve different problems related to delegation.

RSA accumulators and attribute-based encryption have nothing to do with all of that. If you have ZK-SNARKs, you can build accumulators, but that's it. RSA accumulators are just a specific type of accumulators, and one that does not use ZK-SNARKs. Attribute-based encryption is an advanced cryptographic primitive that might use other simpler primitives in some existing constructions, but in general it has no formal relations to ZK-SNARKs.

$\endgroup$

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.