10
$\begingroup$

Given an interactive zk proof, if we use fiat-shamir to make it nizk proof, does the proof become less secure?

Are there any new attack vectors that get introduced?

Is there any reason to use the interactive version over the non-interative version? Aside from both parties always being online

Are there any complexity theoretic comments that can be made about the distinction between interactive and non-interactive proofs?

$\endgroup$
9
$\begingroup$

When turning an interactive ZK proof into a non-interactive zero-knowledge argument with the Fiat-Shamir transform, the following security issues must be taken into consideration:

  • Even if the interactive ZK proof is a proof system (meaning that it is statistically sound), the Fiat-Shamir transform produces an argument system (where soundness is only computational). In concrete terms, that means that you must in general increase the soundness error of the interactive protocol before making it non interactive. Consider for example an interactive protocol where a cheater has probability at most $2^{-40}$ of producing a convincing proof for an incorrect statement: this can be a perfectly fine security guarantee in many real-world situation. But as soon as you turn this protocol into a NIZK with Fiat-Shamir, the guarantee changes: now, you are only guaranteed that forging an incorrect proofs will take $2^{40}$ computation steps for the malicious prover. But performing $2^{40}$ operations is trivial on any standard computer, hence the scheme would be completely broken. Put differently, a NIZK will in general need to be less efficient than the corresponding interactive ZK proof, in terms of communication and computation, to achieve a sufficient security level.
  • Many interactive ZK proofs naturally satisfy non-transferability: if a prover interacts with a verifier and demonstrates that he knows some value, or that some statement is true, the verifier, even after seeing the proof from the prover, cannot in turn convince another party that he knows the value/that the statement is true. This is because the verifier can at best show the transcript to this other party, but by the zero-knowledge property of the protocol, this transcript could in fact have been generated easily without knowing whether the proof is true (put otherwise: if you know the challenge in advance, it's easy to forge a proof. How could the other party know that the verifier had not colluded with the prover and given him the challenge in advance?). In contrast, NIZKs are naturally transferable, since they are publicly verifiable. Sometimes, non-transferability is crucial: suppose you solve a million-dollar problem, and want to prove to someone that you've found the solution. Using a zero-knowledge proof allows you to convince him that you know the solution without revealing it; but you still do not want this person to be able to use your zero-knowledge proof to convince someone else that he knows the solution, since he could then just use your proof to claim the million dollar prize!
  • As pointed out by Martin Kromm, the Fiat-Shamir transform is not proven secure in the standard model under any known security assumption. It is only proven secure in an idealized model, meaning that the security guarantees it gives are, at best, heuristic indications that breaking it requires doing "something non trivial" with the underlying hash function. Concretely, NIZKs obtained with the Fiat-Shamir transform have never been broken as of today and seem relatively safe, but we have no proof of that, so one should be cautious.

As for the reasons to use interactive proofs over non-interactive proofs (besides the one above, that apply specifically to Fiat-Shamir): If you want an extremely efficient proof, where verification is super fast and the communication is very small, then this can be achieved using an interactive proof using standard and well studied assumption, such as collision-resistant hash functions (this paper), the discrete logarithm problem (this paper), etc. In contrast, if you want such an efficient NIZK, you either only have security in the random oracle model (using Fiat-Shamir), or must rely on exotic and poorly understood assumptions, such as the knowledge-of-exponent assumption.

As for complexity-theoretic discussions on NIZKs versus ZK proofs, I discussed the complexity-theoretic questions related to the round complexity of zero-knowledge proofs in this answer. There is also some discussion on the hardness of building NIZKs from standard assumptions (compared to the relative easiness of building interactive ZK from standard assumptions) in the introduction of my recent paper, which you might find relevant.

$\endgroup$
4
$\begingroup$

The Fiat-Shamir heuristic assumes the Random Oracle Model and there exists zero-knowledge proofs which are proven insecure using the Fiat-Shamir tranformation in the standard model(1).

The problem is theoretical for zero knowledge proofs though since you need to break the random oracle assumption. For most (if not all) practical schemes which rely on the Random Oracle Model there are no breaks known.

The other problem for the Fiat-Shamir transformation is that the function used to model the Random Oracle might be broken. For example, if you use SHA256 as a function modeling the Random Oracle and SHA256 gets broken, then the Fiat-Shamir transformation is obviously also not secure.

There is an advantage for using the non-interactive variant too. You don't need to assume malicious verifiers, they can stay honest in the zero-knowledge proof and you can still use the Fiat-Shamir transformation.

1: Shafi Goldwasser and Yael Kalai: On the (In)security of the Fiat-Shamir Paradigm.

$\endgroup$

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.