Ternary forking lemma and its application to~the~analysis of one code-based signature

K. D. Tsaregorodtsev

Prikladnaâ diskretnaâ matematika, no. 1 (2023), pp. 58-71.

Résumé

The paper is devoted to the generalization of the so-called “forking lemma” to the case when the hash function returns a tuple of trits (trit is a variable that can take one out of the three values 0, 1, 2). It can be stated as follows. Let $\mathcal{A}(par, b)$ be an algorithm that, when run on randomly chosen ${par \leftarrow^{\mathrm{R}}}$ Params and ${b \leftarrow^{\mathrm{R}} \{0, 1, 2\}^{\delta}}$, successfully stops and returns the correct answer $x$ with probability $\epsilon$. Then there exists an algorithm $\mathcal{B}$ that uses $\mathcal{A}$ as a subroutine and returns a triple $(x_1, x_2, x_3)$, where $x_i \gets \mathcal{A}(par, b^i)$, $i=1, 2, 3$, with the additional condition that there exists a position $j$ such that $\{ b^1_j, b^2_j, b^3_j \} = \{ 0, 1, 2\}$ (i.e., all trits in this position are different); the success probability of $\mathcal{B}$ can be bounded from above as follows: ${p_{\mathcal{B}} \ge \varepsilon^3 - \varepsilon ({17}/{27})^{\delta/2}}$, and the running time of $\mathcal{B}$ does not exceed $4 t_{\mathcal{A}}$, where $t_{\mathcal{A}}$ is the time complexity of $\mathcal{A}$. The lemma is then applied to the analysis of code-based signature based on Stern identification protocol in the (standard) SUF-CMA model (with the outer hash function modelled as a programmable random oracle). First, we show that the SUF-CMA model can be reduced to the NMA model (in which the adversary makes no sign queries, only random oracle queries), thanks to the zero-knowledge property of the original Stern identification scheme and the programmability of an oracle. We then show that in the NMA model we can restrict attention only to the case, where the adversary makes a single random oracle query. The $b$ value from the forking lemma acts as the random oracle’s answer to the adversarial query. Using the lemma, we are able to fork the process of forging a signature. Having three valid signatures for the same message, we can to extract a secret key (or to find a collision of an inner hash function). Hence, we can bound from above the probability of successful forgery in terms of the probability of successful execution of collision finding and syndrome decoding algorithms.

Détail

Keywords: forking lemma, digital signature, provable security.

Bibliographie

[1] Pointcheval D. and Stern J., “Security proofs for signature schemes”, EUROCRYPT'96, LNCS, 1070, 1996, 387–398 | MR

[2] Damgård I., On $\Sigma$-protocols, Lecture Notes, University of Aarhus, Department of Computer Science, 2002

[3] Fiat A. and Shamir A., “How to prove yourself: Practical solutions to identification and signature problems”, LNCS, 263, 1987, 186–194 | MR

[4] Cheremushkin A. V., “Cryptographic protocols: main properties and vulnerabilities”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2009, no. 2, 115–150 (in Russian)

[5] Bellare M. and Neven G., “Multi-signatures in the plain public-key model and a general forking lemma”, Proc. 13th ACM Conf. CCM'06, 2006, 390–399

[6] Vysotskaya V. V. and Chizhov I. V., “The security of the code-based signature scheme based on the Stern identification protocol”, Prikladnaya Diskretnaya Matematika, 57 (2022), 67–90 | MR

[7] Stern J., “A new identification scheme based on syndrome decoding”, LNCS, 773, 1993, 13–21

[8] Katz J. and Lindell Y., Introduction to Modern Cryptography, 3d Ed., Chapman Hall/CRC Cryptography and Network Security Series, 2021, 628 pp. | MR

[9] Berlekamp E., McEliece R., and Van Tilborg H., “On the inherent intractability of certain coding problems”, IEEE Trans. Inform. Theory, 24:3 (1978), 384–386 | DOI | MR

[10] Bellare M. and Rogaway P., “Random oracles are practical: A paradigm for designing efficient protocols”, Proc. 1st ACM Conf. CCS'93, 1993, 62–73

[11] Fischlin M., Lehmann A., Ristenpart T., et al., “Random oracles with (out) programmability”, LNCS, 6477, 2010, 303–320 | MR

[12] Shoup V., Sequences of Games: a Tool for Taming Complexity in Security Proofs, Cryptology Archive, Paper 2004/332, 2004

[13] Esser A. and Bellini E., Syndrome Decoding Estimator, Cryptology Archive, Paper 2021/1243, 2021 | MR

[14] Syndrome Decoding Estimator, , 2021 https://github.com/Crypto-TII/syndrome_decoding_estimator