Lemma di biforcazione

Con l'espressione lemma di biforcazione (o forking lemma) si indica una serie di numerosi lemmi correlati nella ricerca crittografica. Il lemma afferma che se un avversario (di solito è una macchina di Turing probabilistica), viene lanciato su input tratti da una qualche distribuzione, produce un output che ha qualche proprietà con probabilità non trascurabile, allora con probabilità non trascurabile, se l'avversario viene rilanciato su nuovi ingressi ma con lo stesso nastro casuale, anche la sua seconda uscita avrà la medesima proprietà.

Questo concetto è stato introdotto da David Pointcheval e Jacques Stern in un articolo dal titolo "Security proofs for signature schemes", pubblicato negli atti di Eurocrypt 1996[1][2]. Nel loro articolo, il lemma di biforcazione è specificato in termini di un avversario che attacca uno schema di firma digitale istanziato nel modello dell'oracolo casuale. Gli autori dimostrano che se un avversario può falsificare una firma con probabilità non trascurabile, allora c'è una probabilità non trascurabile che lo stesso avversario con lo stesso nastro casuale possa creare una seconda firma falsa in un attacco con un diverso oracolo casuale[3]. Il forking lemma è stato successivamente generalizzato da Mihir Bellare e Gregory Neven[4]; è stato poi utilizzato e ulteriormente generalizzato per dimostrare la sicurezza di una varietà di schemi di firma digitale e altre costruzioni crittografiche basate sugli oracoli casuali[5][6].

Enunciato

Si riporta di seguito la versione generalizzata del lemma[4]: sia A un algoritmo probabilistico, con input (x, h₁, ..., h_q; r) che restituisce una coppia (J, y), dove r si riferisce al nastro casuale di A (cioè le scelte casuali che A farà). Supponiamo, inoltre, che IG sia una distribuzione di probabilità da cui si ricava x, e che H sia un insieme di dimensione h da cui ciascuno dei valori di h_i è tratto secondo la distribuzione uniforme . Sia acc la probabilità che su input distribuiti come descritto, l'uscita J di A sia maggiore o uguale a 1.

Possiamo quindi definire un "algoritmo di biforcazione" F_A che procede come segue, sull'ingresso x :

1. Sceglie un nastro a caso r per A.
2. Sceglie h₁, ..., h_q in modo uniforme da H.
3. Esegue A sull'input (x, h₁, ..., h_q; r) per produrre (J, y).
4. Se J = 0, restituisce (0, 0, 0).
5. Sceglie h'_J, ..., h'_q in modo uniforme da H.
6. Esegue A sull'input (x, h₁, ..., h_J−1, h'_J, ..., h'_q; r) per produrre (J', y').
7. Se J' = J e h_J ≠ h'_J allora restituisce (1, y, y '), altrimenti, restituisce (0, 0, 0).

Sia ora frk la probabilità che F_A restituisca una tripla che inizia con 1, dato un input x scelto casualmente dalla distribuzione IG . Allora, si ha che:

${\displaystyle {\text{frk}}\geq {\text{acc}}\cdot \left({\frac {\text{acc}}{q}}-{\frac {1}{h}}\right).}$

Note

1. International Workshop on Practice and Theory in Public Key Cryptography (3rd : 2000 : Melbourne, Vic.), Public key cryptography : third International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Melbourne, Victoria, Australia, January 18-20, 2000 : proceedings, Springer, 2000, ISBN 3-540-66967-1, OCLC 43076911. URL consultato il 10 settembre 2020.
2. Adam L. Young e Moti Yung, Cryptography: Malicious Cryptography – Exposing Cryptovirology, in Computer Law & Security Review, vol. 20, n. 5, 2004-09, p. 430, DOI:10.1016/s0267-3649(04)00079-2. URL consultato il 10 settembre 2020.
3. David Pointcheval e Jacques Stern, Advances in Cryptology — EUROCRYPT ’96, Springer Berlin Heidelberg, 1996, pp. 387-398, ISBN 978-3-540-61186-8. URL consultato il 10 settembre 2020.
4. Mihir Bellare e Gregory Neven, Multi-signatures in the plain public-Key model and a general forking lemma, in Proceedings of the 13th ACM conference on Computer and communications security - CCS '06, ACM Press, 2006, DOI:10.1145/1180405.1180453. URL consultato il 10 settembre 2020.
5. Ali Bagherzandi, Jung-Hee Cheon e Stanislaw Jarecki, Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma, in Proceedings of the 15th ACM conference on Computer and communications security - CCS '08, ACM Press, 2008, DOI:10.1145/1455770.1455827. URL consultato il 10 settembre 2020.
6. Javier Herranz e Germán Sáez, Progress in Cryptology - INDOCRYPT 2003, Springer Berlin Heidelberg, 2003, pp. 266-279, ISBN 978-3-540-20609-5. URL consultato il 10 settembre 2020.