# Fiat-Shamir for $(2n + 1)$

Consider the following $$(2n+1)$$ protocol:

$$\mathcal{P}$$ and $$\mathcal{V}$$ engage in an interaction where $$\mathcal{P}$$ consecutively sends a message $$a_i$$ answered by $$\mathcal{V}$$ with a random challenge $$b_i$$ for $$i = 1,\dots,n$$. Finally $$\mathcal{P}$$ gives a final answer $$z$$ and $$\mathcal{V}$$ outputs either $$1$$ or $$0$$ (i.e., accepts or rejects the proof) checking the conversation $$(x,\{a_i\}_{i=1}^n,\{b_i\}_{i=1}^n,z)$$.

The protocol verifies the following properties:

• Completeness: If an honest prover $$\mathcal{P}$$ knows a valid witness $$w$$ and follows the protocol, then an honest verifier $$\mathcal{V}$$ always accepts the conversation.

• $$k$$-Special Soundness: From $$k$$ valid conversations $$\{(x,\{a_i^j\}_{i=1}^n,\{b_i^j\}_{i=1}^n,z^j)\}_{j=1}^k$$, and $$\{b_i^j\}_{i=1}^n \neq \{b_i^{j'}\}_{i=1}^n$$ for all $$j \neq j'$$, it is possible to efficiently extract a witness $$w$$.

• Honest-Verifier Zero-Knowledge: There exists a polynomial-time simulator that takes $$x$$ and random $$\{b_i\}_{i=1}^n$$ and output a valid conversation $$(x,\{a_i\}_{i=1}^n,\{b_i\}_{i=1}^n,z)$$ with the same probability distribution as conversations between honest $$\mathcal{P}$$ and $$\mathcal{V}$$.

This is a non-standard zero-knowledge protocol which I am trying to apply the Fiat-Shamir Heuristic to turn it into non-interactive. I am struggling with the soundness property, since is quite different from a typicial protocol.

Is there anything in the literature that generalizes the Fiat-Shamir Heuristic to finite $$(2n+1)$$ protocols? Maybe that can help to solve this problem.

## 1 Answer

You can find the security proofs for 5-round Fiat-Shamir:

• Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe: From 5-pass MQ-based identification to MQ-based signatures. Asiacrypt 2016. https://eprint.iacr.org/2016/708
• Özgür Dagdelen, David Galindo, Pascal Véron, Sidi Mohamed El Yousfi Alaoui, and Pierre-Louis Cayrel. Extended security arguments for signature schemes. Designs, Codes and Cryptography, 78(2):441–461, 2016. https://link.springer.com/article/10.1007/s10623-014-0009-7

Their proof (may) contain (2n+1)-round Fiat-Shamir.

• The second paper did the trick – Lecter May 25 '20 at 11:21