Security of zero knowledge proof protocols

Question

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?

Answer 1

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