Forking lemma

rdf:langString Lemma di biforcazione

rdf:langString 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.