Security of zero knowledge proof protocols

When designing a protocol based on zero knowledge proofs, be it based on the discrete log problem, or on a Hamiltonian cycle in a graph, or something else, I assume there are security considerations, like there are security considerations in the use of conventional ciphers.

For example, when using AES (or any block cipher for that matter), one has to make sure that the IV is random, and a good block cipher mode is chosen.
When using RSA, one has to use a secure padding scheme, pick a high, but not too high exponent (0x10001, for example).

I wonder whether there exist this kind of considerations for several ZKP systems too; e.g., on how to generate a "good" graph for the Hamiltonian path problem.
I.e. I wonder how to make sure that Victor cannot gain Peggy's knowledge, using side channels, timing attacks, statistical attacks, or something alike? Has there been interesting publications to read upon this topic?

• Actually, for RSA, $e=3$ works just fine (assuming that you do the padding properly; $e=3$ is more fragile is you don't do the padding properly...) Jun 8, 2017 at 18:03
• I've been recommending ZKPs as interesting solutions to problems on the WorldBuilding.SE for a while. I too have been curious what sort of heuristics can be applied to identify a "good" key for standard ZKP constructs like the Hamiltonian Path/graph Isomorphism proof. I always feel bad suggesting an answer which may not actually hold up due to bad key choices, even if its for a fictional world like WB produces. Jun 8, 2017 at 18:29
• In your AES and RSA examples, a bad design cannot be proven secure (and in fact can trivially be proven insecure). ZK protocols, however, tend to come with a security proof. Of course, if you don't implement it correctly, all bets are off. Jun 9, 2017 at 4:29
• @fkraiem, that's interesting already; build upon that, what "insecure" designs exist out there, and how are they secured w.r.t. ZKP? And would you have material to read in terms of a ZKP security proof? I seem to have difficulties finding such information. Jun 9, 2017 at 6:21
• For example any block ciper in ECB mode can trivially be proven insecure wrt most definitions of security for encryption schemes, which can be found in any standard textbook. Likewise for material relating to ZK protocols. Jun 9, 2017 at 18:15

1 Answer

I will try to answer your question in three parts. Before I start, let me introduce a somewhat more formal notation to ease the explanation. In particular, let $L = \{x ~|~ \exists~w : (x,w) \in R\}$ be the NP language with associated witness relation $R$ and we will always assume that we have a proof system for that language.

1. Informally speaking, one proves that a particular proof system satisfies the zero-knowledge property by showing that when setting up the proof system in a special way (indistinguishable from the original setup) one can build an efficient simulator $\cal S$ which can produce proofs for statements in the language which are indistinguishable from real proofs output by the actual prover - but $\cal S$ runs without knowing a corresponding witness. Very roughly, this then shows that - under the assumption which was used to prove zero-knowledge - no information about the witness is contained in the proof.
2. It is important to note that a zero-knowledge proof only guarantees that the proof itself does not contain information about the witness. However, if $L$ is so that finding witnesses for statements in $L$ is easy, one can always directly compute the witness without looking at the proof at all. More precisely, the problem under which the zero-knowledge property of the used proof system is proven is not necessarily connected to the problem associated to finding a witness for some element in $L$. Speaking in terms of your example: "generating a good graph for the Hamiltonian graph problem" is something which is independent of the zero-knowledge proof system and only depends on your application.
3. To your question regarding other attacks: of course, the zero-knowledge property does not rule out attacks on the implementation level. For example, if the prover leaks something about the witness upon proof computation via some side channel, one might be able to find out something about the witness. For further reading, I would just recommend standard literature on side channel attacks (e.g., [1]). Alternatively you may also have a look at [2], who explicitly mention how they address implementation-level issues in the context of zero-knowledge proofs.

References

[1] Stefan Mangard, Elisabeth Oswald, Thomas Popp: Power analysis attacks - revealing the secrets of smart cards. Springer 2007, ISBN 978-0-387-30857-9, pp. I-XXIII, 1-337

[2] Endre Bangerter, Stefania Barzan, Stephan Krenn, Ahmad-Reza Sadeghi, Thomas Schneider, Joe-Kai Tsay: Bringing Zero-Knowledge Proofs of Knowledge to Practice. Security Protocols Workshop 2009: 51-62