Successful Cryptanalysis Research/Attacks on Zero-Knowledge Proofs?

Question

A robust implementation of any cryptosystem (E.g., AES) has a comprehensive cryptanalysis research/attacks on it.

Are there any successful cryptanalysis research/attacks on zero-knowledge proofs?

Answer 1

For most symmetric cryptosystems, such as AES, the best way to study their security is to design various types of attacks, and to analyze the resistance of the primitive to these attacks. With zero-knowledge proofs, things are in general a bit different:

• Zero-knowledge proofs are, in some sense, a "higher level" primitive, which means that they can be (and are, in general) constructed from other primitives.
• Unlike symmetric cryptosystems, where the number of "standard primitives" is relatively small, there are hundreds of proposals for zero-knowledge proofs. This means that getting confidence in their security using cryptanalysis would require designing attacks for hundreds of different, non-standardized (and not much used in practice) primitives. That would be kind of a waste of effort.

For the above reasons, the usual (and best) approach to study the security of zero-knowledge proofs is through provable security. Usually, this is done by reducing the security properties of the zero-knowledge proof to the underlying lower level primitive it was built from. This way, cryptanalysts can simply focus on this underlying primitive to give us confidence in the security of the proof. Roughly, the zero-knowledge proofs we know of belong to four categories:

• Some have unconditional security. This means that we can prove that they satisfy completeness, soundness, and zero-knowledge, without making any assumption. This is the case e.g. for the standard proof for graph isomorphism, or for the famous Schnorr protocol for knowledge of a discrete logarithm (which only satisfies honest-verifier zero-knowledge). For these proofs, no cryptanalysis is needed.
• Some can be reduced to generic assumptions. For examples, the general solution to zero-knowledge proofs for NP from the seminal paper of Goldwasser, Micali, and Rackoff, can be based on any one-way function. This means, in particular, that we can build a proof for any NP statement, whose security (here, soundness is unconditional and zero-knowledge is computational, but we can also get the reverse) would reduce to the assumption that AES is secure. Hence, we can use all cryptanalytic efforts on AES (or SHA3, or any symmetric primitive you can think of) to our advantage when constructing a ZK proof.
• Some proofs reduce to specific, well known assumptions. This is usually the case for more "advanced" zero-knowledge proofs. For example, Jen Groth's sublinear zero-knowledge arguments, which allow to prove statements from linear algebra with communication $O(\sqrt{N})$ ($N$ is the size of the statement), is secure under the discrete logarithm assumption. This means that cryptanalytic efforts can focus on algorithms for solving the discrete logarithms, if we want to study the security of these protocols.
• Finally, some recent zero-knowledge proofs have more ad-hoc underlying assumptions. This is in general the case of zk-SNARKs, where we give up the reduction to standard and well-known assumptions, in exchange for extreme efficiency (i.e., the proof is non-interactive and of constant size). For these "extreme" proofs, it would make sense to have a specific cryptanalytic research, but as the area is still very young, there are not much results in this direction at the moment.