0
$\begingroup$

I'm not sure how to compute the second challenge when applying FS to a 5-round protocol. I've seen TWO different formulas (with and without including the first challenge) and don't know which one is correct.

Suppose we have 5-round interactive protocol for some statement $st$:

$P$ → $V$: $x$ means prover sent $x$ to verifier.

$P$ ← $V$: $y$ means verifier sent $y$ to prover.

  1. $P$ → $V$: $\alpha_1$ // 1st commitment
  2. $P$ ← $V$: $ch_1$ // 1st challenge
  3. $P$ → $V$: $\alpha_2$ // 1st answer
  4. $P$ ← $V$: $ch_2$ // 2nd challenge
  5. $P$ → $V$: $\alpha_3$ // 2nd answer

Now we can apply Fiat-Shamir transform to get a non-interactive proof.

Question: how we compute $ch_2$?:

a) $ch_2 = Hash(st|\alpha_1|\alpha_2|aux)$

b) $ch_2 = Hash(st|\alpha_1|\alpha_2|ch_1| aux)$ ← includes $ch_1$

On the one hand, $ch_2$ should be independent of $ch_1$, right? An original article of Pointcheval and Stern[2], article by Kiltz et. al[1], plus some answers here use formula a.

On the other hand, there are articles [3],[4] where the formula b is used.

UPD: Will the fact of whether $ch1$ included or not matter for the Forking Lemma?

[1] Tightly-Secure Signatures from Five-Move Identification Protocols by Eike Kiltz, Julian Loss, and Jiaxin Pan https://eprint.iacr.org/2017/870.pdf

[2] Security Arguments for Digital Signatures and Blind Signatures by David Pointcheval and Jacques Stern https://www.di.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf

[3] From 5-pass MQ-based identification to MQ-based signatures by Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe https://eprint.iacr.org/2016/708.pdf

[4] Extended Security Arguments for Signature Schemes by Sidi Mohamed El Yousfi Alaoui, Özgür Dagdelen, Pascal Véron, DavidGalindo, Pierre-Louis Cayrel https://hal.inria.fr/hal-00684486/document

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

These are equivalent. Given that the first challenge is a deterministic function of the statement and $\alpha_1$, it makes no difference. What is crucial is just to include the statement, and the entire transcript to that point. (Note that anything that is deterministically dependent on other things doesn't have to be included in the transcript.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Practically yes sure. But what happens if we apply the Forking Lemma to prove soundness, will the fact that ch1 included or not matter? $\endgroup$
    – pintor
    Commented Feb 6, 2020 at 15:08
  • 1
    $\begingroup$ It should not matter. If you are rewinding back behind $\alpha_2$ then you can change $ch1$ anyway, and if you are rewinding to after $\alpha_2$ then you can change $ch2$ anyway (since you are running the random oracle). $\endgroup$
    – Yehuda Lindell
    Commented Feb 6, 2020 at 15:10
  • $\begingroup$ Thank you very much! By any chance, do you know any book/article that talks about the possibility of excluding deterministically dependent values from the transcripts? $\endgroup$
    – pintor
    Commented Feb 14, 2020 at 10:09
  • $\begingroup$ No sorry. I think you may just have to work through the proof. I don't know. $\endgroup$
    – Yehuda Lindell
    Commented Feb 14, 2020 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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