In crittografia, la trasformata di Fiat-Shamir (anche nota come euristica di Fiat-Shamir) è una tecnica utilizzata per trasformare una dimostrazione interattiva di conoscenza e creare una firma digitale basata su di essa. La tecnica originale è dovuta ad Amos Fiat e Adi Shamir (1986). Affinché il metodo funzioni, la dimostrazione interattiva originale deve essere "a moneta pubblica", ovvero i valori casuali generati dal verificatore durante l'esecuzione dell'algoritmo sono resi pubblici nel protocollo.
Tra le sue applicazioni più importanti si trova la creazione di firme digitali.
Panoramica La trasformata originale è stata presentata come un'euristica, ovvero senza una dimostrazione formale della sua sicurezza. Pointcheval e Stern in seguito la dimostrano sicura contro gli attacchi con messaggi scelti nel modello dell'oracolo random. Questo risultato è stato generalizzato all'oracolo random accessibile quantisticamente (QROM) da Don, Fehr, Majenz e Schaffner, e contemporaneamente da Liu e Zhandry. Shafi Goldwasser e Yael Tauman Kalai dimostrano che la trasformata è insicura senza l'utilizzo di oracoli random.
La trasformata di Fiat-Shamir può essere utilizzata per convertire una qualunque dimostrazione interattiva a moneta pubblica in una dimostrazione di conoscenza non interattiva. Ad esempio, se la dimostrazione interattiva originale viene utilizzata come protocollo di identificazione, la sua versione non interattiva può essere utilizzata direttamente come firma digitale utilizzando il messaggio come parte dell'input per l'oracolo casuale. In questo caso il protocollo interattivo sta dimostrando la conoscenza della chiave privata da parte del dimostratore, che diventa il firmatario del messaggio.
Esempio: la firma di Schnorr Partendo da una dimostrazione interattiva della conoscenza di un logaritmo discreto in , è possibile costruire la firma Schnorr.
Il valore segreto è , il logaritmo discreto di in base . I valori pubblici sono e un generatore di . Definiamo il seguente protocollo interattivo tra Peggy ("prover", dimostratore) e Victor ("verifier", verificatore):
Peggy vuole dimostrare a Victor, il verificatore, che conosce tale che senza rivelare . Peggy sceglie a caso , calcola e invia a Victor. Victor sceglie a caso e lo invia a Peggy. Peggy calcola , dove è la funzione di Eulero, e restituisce a Victor. Victor verifica se . Se questo vale, Victor acquisisce confidenza sul fatto che Peggy conosca .
Se Peggy conosce davvero il protocollo funziona, perché dove abbiamo usato il fatto che, per costruzione, .
La trasformata di Fiat-Shamir consente di sostituire il passaggio interattivo del protocollo (3) con un accesso casuale non interattivo ad un oracolo random. Questo consente di rendere il ruolo di Victor passivo, e viene fatto utilizzando una funzione crittografica di hash.
Peggy vuole dimostrare di conoscere tale che senza rivelare . Peggy sceglie a caso e calcola . Peggy calcola , Dove è una funzione hash crittografica. Peggy calcola , e rende pubblica la coppia . Chiunque, anche Victor, può usare questa coppia per calcolare e verificare se .
L'esecuzione di quest'ultimo algoritmo non richiede alcun lavoro da parte di Victor. Chiunque può verificare che , dati i valori pubblici, l'equazione nel punto 5 è corretta.
Notiamo che se la funzione di hash nel punto 3 non dipende dal valore (pubblico) di lo schema ha sicurezza ridotta. Un attaccante che provi ad impersonare Peggy senza conoscere il valore segreto di potrebbe comunque provare a selezionare uno specifico valore t in modo da conoscere il prodotto .|https://eprint.iacr.org/2016/771.pdf
Note
Voci correlate
Lemma di biforcazione Oracolo random Dimostrazione a conoscenza zero
Categoria:Crittografia Categoria:Firma digitale