Lemma di biforcazione: differenze tra le versioni
Vai alla navigazione
Vai alla ricerca
Contenuto cancellato Contenuto aggiunto
Creata dalla traduzione della pagina "Forking lemma" |
numerosi fix, note, portale |
||
| Riga 1: | Riga 1: | ||
Con l'espressione '''lemma di biforcazione''' (o '''forking lemma''') si indica una serie di numerosi [[Lemma (matematica)|lemmi]] correlati nella ricerca [[Crittografia|crittografica]]. Il lemma afferma che se un avversario (di solito è una [[macchina di Turing probabilistica]]), viene lanciato su input tratti da una qualche [[Variabile casuale#Distribuzione di probabilità|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à. |
Con l'espressione '''lemma di biforcazione''' (o '''forking lemma''') si indica una serie di numerosi [[Lemma (matematica)|lemmi]] correlati nella ricerca [[Crittografia|crittografica]]. Il lemma afferma che se un avversario (di solito è una [[macchina di Turing probabilistica]]), viene lanciato su input tratti da una qualche [[Variabile casuale#Distribuzione di probabilità|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<ref> |
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<ref>{{Cita libro|cognome=International Workshop on Practice and Theory in Public Key Cryptography (3rd : 2000 : Melbourne, Vic.)|titolo=Public key cryptography : third International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Melbourne, Victoria, Australia, January 18-20, 2000 : proceedings|url=http://worldcat.org/oclc/43076911|accesso=2020-09-10|data=2000|editore=Springer|OCLC=43076911|ISBN=3-540-66967-1}}</ref><ref>{{Cita pubblicazione|nome=Adam L.|cognome=Young|nome2=Moti|cognome2=Yung|data=2004-09|titolo=Cryptography: Malicious Cryptography – Exposing Cryptovirology|rivista=Computer Law & Security Review|volume=20|numero=5|pp=430|accesso=2020-09-10|doi=10.1016/s0267-3649(04)00079-2|url=http://dx.doi.org/10.1016/s0267-3649(04)00079-2}}</ref>. 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 random|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<ref>{{Cita libro|nome=David|cognome=Pointcheval|nome2=Jacques|cognome2=Stern|titolo=Advances in Cryptology — EUROCRYPT ’96|url=http://dx.doi.org/10.1007/3-540-68339-9_33|accesso=2020-09-10|data=1996|editore=Springer Berlin Heidelberg|pp=387–398|ISBN=978-3-540-61186-8}}</ref>. Il forking lemma è stato successivamente generalizzato da Mihir Bellare e Gregory Neven<ref name=":0">{{Cita pubblicazione|nome=Mihir|cognome=Bellare|nome2=Gregory|cognome2=Neven|data=2006|titolo=Multi-signatures in the plain public-Key model and a general forking lemma|rivista=Proceedings of the 13th ACM conference on Computer and communications security - CCS '06|editore=ACM Press|accesso=2020-09-10|doi=10.1145/1180405.1180453|url=http://dx.doi.org/10.1145/1180405.1180453}}</ref>; è 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<ref>{{Cita pubblicazione|nome=Ali|cognome=Bagherzandi|nome2=Jung-Hee|cognome2=Cheon|nome3=Stanislaw|cognome3=Jarecki|data=2008|titolo=Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma|rivista=Proceedings of the 15th ACM conference on Computer and communications security - CCS '08|editore=ACM Press|accesso=2020-09-10|doi=10.1145/1455770.1455827|url=http://dx.doi.org/10.1145/1455770.1455827}}</ref><ref>{{Cita libro|nome=Javier|cognome=Herranz|nome2=Germán|cognome2=Sáez|titolo=Progress in Cryptology - INDOCRYPT 2003|url=http://dx.doi.org/10.1007/978-3-540-24582-7_20|accesso=2020-09-10|data=2003|editore=Springer Berlin Heidelberg|pp=266–279|ISBN=978-3-540-20609-5}}</ref>. |
||
Communications Security (CCS), [[Alexandria, Virginia]], 2006, pp. 390–399.</ref>; è 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<ref>Ali Bagherzandi, Jung Hee Cheon, Stanislaw Jarecki: |
|||
Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma. 449-458</ref><ref>Javier Herranz, Germán Sáez: |
|||
Forking Lemmas for Ring Signature Schemes. 266-279</ref>. |
|||
== Enunciato == |
== Enunciato == |
||
| ⚫ | Si riporta di seguito la versione generalizzata del lemma<ref name=":0" />: sia ''A'' un algoritmo probabilistico, con input (''x'', ''h''<sub>1</sub>, ..., ''h''<sub>''q''</sub>; ''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<sub>i</sub>'' è tratto secondo la [[Distribuzione discreta uniforme|distribuzione uniforme]] . Sia acc la probabilità che su input distribuiti come descritto, l'uscita ''J'' di ''A'' sia maggiore o uguale a 1. |
||
Si riporta di seguito la versione generalizzata del lemma<ref name="BellareNeven">[[Mihir Bellare]] and Gregory Neven, "[http://portal.acm.org/citation.cfm?id=1180453 Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma]", Proceedings of the 13th [[Association for Computing Machinery]] (ACM) Conference on Computer and |
|||
| ⚫ | |||
Possiamo quindi definire un "algoritmo di biforcazione" ''F<sub>A</sub>'' che procede come segue, sull'ingresso ''x'' : |
Possiamo quindi definire un "algoritmo di biforcazione" ''F<sub>A</sub>'' che procede come segue, sull'ingresso ''x'' : |
||
# Sceglie un nastro a caso ''r'' per ''A.'' |
# Sceglie un nastro a caso ''r'' per ''A.'' |
||
# Sceglie ''h''<sub>1</sub>, ..., ''h''<sub>''q |
# Sceglie ''h''<sub>1</sub>, ..., ''h''<sub>''q''</sub> in modo uniforme da ''H.'' |
||
# Esegue ''A'' sull'input (''x'', ''h''<sub>1</sub>, ..., ''h''<sub>''q''</sub>; ''r'') per produrre (''J'', ''y''). |
# Esegue ''A'' sull'input (''x'', ''h''<sub>1</sub>, ..., ''h''<sub>''q''</sub>; ''r'') per produrre (''J'', ''y''). |
||
# Se ''J'' = 0, restituisce (0, 0, 0). |
# Se ''J'' = 0, restituisce (0, 0, 0). |
||
| Riga 25: | Riga 21: | ||
== Note == |
== Note == |
||
<references/> |
|||
{{References}} |
|||
<nowiki> |
|||
{{Portale|crittografia}} |
|||
[[Categoria:Crittografia]]</nowiki> |
|||
Versione delle 09:18, 10 set 2020
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, h1, ..., hq; 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 hi è 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" FA che procede come segue, sull'ingresso x :
- Sceglie un nastro a caso r per A.
- Sceglie h1, ..., hq in modo uniforme da H.
- Esegue A sull'input (x, h1, ..., hq; r) per produrre (J, y).
- Se J = 0, restituisce (0, 0, 0).
- Scegle h'J, ..., h'q in modo uniforme da H.
- Esegue A sull'input (x, h1, ..., hJ−1, h'J, ..., h'q; r) per produrre (J', y').
- Se J' = J e hJ ≠ h'J allora restituisce (1, y, y '), altrimenti, restituisce (0, 0, 0).
Sia ora frk la probabilità che FA restituisca una tripla che inizia con 1, dato un input x scelto casualmente dalla distribuzione IG . Allora, si ha che:
Note
- ^ 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.
- ^ Adam L. Young e Moti Yung, Cryptography: Malicious Cryptography – Exposing Cryptovirology, in Computer Law & Security Review, vol. 20, n. 5, 2004-09, pp. 430, DOI:10.1016/s0267-3649(04)00079-2. URL consultato il 10 settembre 2020.
- ^ 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.
- ^ a b 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.
- ^ 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.
- ^ 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.
