2
$\begingroup$

I have read in many places that Fiat Shamir technique is used to convert constant round interactive protocols to non-interactive arguments. What would be the problem in applying Fiat Shamir to poly-round protocols?

$\endgroup$
4
$\begingroup$

Yes, there are examples of non-constant round interactive protocols that are unsound when the Fiat-Shamir transform is applied even in the random-oracle model. Note that for constant-round protocols soundness in the random oracle model was proved by Pointcheval and Stern [PS00] -- that is, any constant round interactive protocol (that has negligible soundness error) is also sound when the Fiat-Shamir transform is applied to it given the hash function is modelled as a random oracle.

One simple counter-example is to consider the sequential composition, say $n$ times, of a constant-round protocol that has constant soundness error. By amplification theorem, the resultant protocol has negligible soundness error --- inverse-exponential in $n$ to be precise --- but the Fiat-Shamir transformed protocol is totally insecure as argued next. Since the soundness error is constant a malicious prover can basically sample (in constant-many attempts in expectation) "favourable" messages for each round and with high probability come up with a cheating proof: see this lecture (around 11 minutes) by Ron Rothblum for more details.

[PS00] Pointcheval and Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.

| improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.