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.


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.

| improve this answer | |
  • $\begingroup$ The second paper did the trick $\endgroup$ – Lecter May 25 at 11:21

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.