Skip to main content
added 89 characters in body
Source Link
pintor
  • 558
  • 3
  • 14

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

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.


[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

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

Source Link
pintor
  • 558
  • 3
  • 14

Second challenge in Fiat-Shamir for 5-round schemes

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.


[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