Challenges of Fiat-Shamir Transformation of ZK Proof / Sigma Protocol

Question

Let $\Sigma$ be a sigma protocol whose commitment, challenge and response phases are $\Sigma_1, \Sigma_2, \Sigma_3$, respectively.

In Fiat-Shamir Transformation, the challenges are $H(\Sigma_1)$ where $H$ is some hash function.

However, in some literature, instead of having $H(\Sigma_1)$ it is $H(x \parallel \Sigma_1)$, where $\parallel$ denotes concatenation and $x$ is the common input. For example, if $\Sigma$ is the graph 3-coloring protocol, $x$ would be the corresponding graph.

1. Why consider the concatenation with $x$? Is $x$ there in order to prevent malleable attacks?

2. Consider a language $L \in$ NP and suppose that a prover P wants to prove to a verifier V that $x \in L$. We use the classical reductions of $x$ to a SAT instance and then to a G3C instance. Call this reduction $t$. In this way, $x \in L$ iff $t(x)$ is a 3-colorable graph. Now we can apply the Fiat-Shamir Transformation, and the challenges become $H(t(x) \parallel \Sigma_1)$. Is it possible to make the challenges $H(x \parallel \Sigma_1)$ instead of $H(t(x) \parallel \Sigma_1)$, thus avoiding increase of the input of $H$?

Thanks in advance.

Answer 1

If the challenge is calculated as $H(\Sigma_1)$ the transform is called the weak Fiat-Shamir (wFS) transform. On the other hand, when the challenge is computed as $H(x\mathbin\Vert \Sigma_1)$ the transform is called the strong Fiath-Shamir (sFS) transform.

1. In scenarios where the attacker can choose adaptively the statement she would like to prove, the proof system is not secure anymore, ie. it is not a proof-of-knowledge anymore. For instance, this leads to many practical attacks against the Helios voting system. Let's consider the Schnorr identification as an example where the wFS transform is not secure.

In a group $\mathbb{G}$ of order $q$ generated by $G$, it proves knowledge of an exponent $x$ satisfying the equation $X = G^{x}$ for a known $X$. Viewing $(x, X)$ as a signing/verification key pair and including a message in the hash input yields a signature of knowledge. To create a proof, the prover picks a random $a\leftarrow \mathbb{Z}_q$ and computes $A = G^a$. She then hashes $A$ to create a challenge $c=H(A)$. Finally she computes $f=a+cx$; the proof is the pair $(c, f)$ and the verification procedure consists in checking the equation $c = H\Big(\frac{G^f} {X^c}\Big)$.

However, if the goal of the adversary is to build a valid triple $(X, c, f)$ for any $X$ of her choice, then this protocol is not a proof of knowledge anymore unless the discrete logarithm problem is easy in $\mathbb{G}$. Suppose indeed that there is an extractor $K$ that, by interacting with any prover $P$ that provides a valid triple $(X, c, f)$, extracts $x = \log_G(X)$. This extractor can be used to solve an instance $Y$ of the discrete logarithm problem with respect to $(\mathbb{G}, G)$ as follows: use $Y$ as the proof commitment, compute $c = H(Y )$, choose $f\leftarrow \mathbb{Z}_q$ and set $X = \Big(\frac{G^f}{Y}\Big)^{1/c} $. Since the proof $(Y, c, f)$ passes the verification procedure for statement $X$, the extractor $K$ should be able to compute $x = \log_G(X)$ by interacting with our prover. We now observe that, by taking the discrete logarithm in base $G$ on both sides of the definition of $X$, we obtain the solution $\log_G(Y ) = f − cx$ to the discrete logarithm challenge.

A nice paper describing the pitfalls of the wFS transform can be found here.

2. Since this is an instance of the sFS transform, your proposed change yields a secure ZKP, for proof see Section 4. in the above linked paper.

However, I'm not aware of any practical deployment of ZKPs which would use such reduction techniques. Generic ZKPs for NP-complete languages are overkill and inefficient in most application scenarios. In my opinion, those results are mostly considered as theoretical results to show that there exists ZKPs for all NP languages.