0
$\begingroup$

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.

$\endgroup$

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.