miniatura|Protocol d'identificació Fiat-Shamir. El diagrama de seqüència del protocol d'identificació Fiat-Shamir. La imatge s'ha creat amb gedit (un editor de text). En criptografia, l'heurística de Fiat-Shamir, o transformació de Fiat-Shamir, és una tècnica per prendre una prova interactiva de coneixement i crear una signatura digital basada en ella. D'aquesta manera, algun fet (per exemple, el coneixement d'un cert número secret) es pot demostrar públicament sense revelar la informació subjacent. La tècnica es deu a Amos Fiat i Adi Shamir (1986). Perquè el mètode funcioni, la prova interactiva original ha de tenir la propietat de ser public-coin, és a dir, les monedes aleatòries del verificador es fan públiques al llarg del protocol de prova.
Visió general L'heurística es va presentar originalment sense una prova de seguretat; més tard, Pointcheval i Stern van demostrar la seva seguretat contra atacs de missatges escollits en el model d'oracle aleatori, és a dir, assumint que existeixen oracles aleatoris. Aquest resultat va ser generalitzat a l' oracle aleatori accessible quànticament (QROM) per Don, Fehr, Majenz i Schaffner, i simultàniament per Liu i Zhandry. En el cas que no existeixin oracles aleatoris, Shafi Goldwasser i Yael Tauman Kalai han demostrat que l'heurística Fiat-Shamir no és segura. L'heurística de Fiat-Shamir demostra, doncs, una aplicació important dels oracles aleatoris. Més generalment, l'heurística de Fiat-Shamir també es pot veure com la conversió d'una prova de coneixement interactiva de moneda pública en una prova de coneixement no interactiva. Si la prova interactiva s'utilitza com a eina d'identificació, la versió no interactiva es pot utilitzar directament com a signatura digital utilitzant el missatge com a part de l'entrada a l'oracle aleatori.
Exemple Per a l'algoritme especificat a continuació, els lectors haurien d'estar familiaritzats amb els grups multiplicatius , on q és un nombre primer, i el teorema totient d'Euler sobre la funció totient d'Euler φ.
Aquí teniu una demostració interactiva del coneixement d'un logaritme discret en , basat en la signatura de Schnorr. Els valors públics són i un generador g de , mentre que el valor secret és el logaritme discret de y a la base g.
La Peggy vol demostrar-li a en Víctor, el verificador, que sap satisfactori sense revelar . La Peggy tria un a l'atzar , calcula i envia al Víctor. En Víctor tria una a l'atzar i l'envia a la Peggy. La Peggy calcula i retorna al Víctor. En Víctor comprova si . Això és cert perquè i .
L'heurística de Fiat-Shamir permet substituir el pas 3 interactiu per un accés aleatori a oracle no interactiu. A la pràctica, podem utilitzar una funció hash criptogràfica. Insereix un paràgraf
La Peggy vol demostrar que ho sap de tal manera que sense revelar. La Peggy tria un a l'atzar i calcula. La Peggy calcula, on és una funció hash criptogràfica. La Peggy calcula. La demostració resultant és el parell. Qualsevol pot utilitzar aquesta demostració per calcular i comprovar si.
Si el valor hash utilitzat a continuació no depèn del valor (públic) de y, la seguretat de l'esquema es veu debilitada, ja que un demostrador maliciós pot seleccionar un cert valor t de manera que el producte cx sigui conegut.
Extensió d'aquest mètode Sempre que es pugui construir un generador aleatori fix amb les dades conegudes per ambdues parts, qualsevol protocol interactiu es pot transformar en un de no interactiu.
Referències
Categoria:Criptografia