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. 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. Il forking lemma è stato successivamente generalizzato da Mihir Bellare e Gregory Neven; è 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.

Enunciato

Si riporta di seguito la versione generalizzata del lemma: 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:

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