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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.