Firma de Lamport-Diffie

La Firma de Lamport és un esquema de firma digital d'un sol us, inventada per Leslie Lamport en 1979. La firma s'aplica sobre mensages sense efectuar cap modificació prèvia dels mateixos.

L'esquema de firma de Lamport utilisa un joc de claus, compost per una clau privada i una clau pública. La clau privada és un conjunt de $2*n$ elements privats. La clau pública és un atre conjunt de $2*n$ elements, formats, generalment, per l'aplicació d'una funció hash a cada element privat. Per a firmar un document, s'aplica una funció hash al document del que s'obtenen $n$ bits, i s'utilisen per a seleccionar $n$ elements de la clau pública.

Representació de la seqüència per a firmar un document en una firma de Lamport.

La firma de Lamport es deu utilisar una sola volta per cada joc de claus. No obstant, combinat l'esquema de firma de Lamport en un Arbre de Merkle, un sol joc de claus podria usar-se per a firmar varis mensages, lo que la convertix en un esquema de firma digital prou eficient.

El desenroll potencial de la computació quàntica amenaça la seguritat de moltes formes comunes de criptografia com RSA, pero es creu que les firmes de Lamport estarien segures si s'usen, com a components de les claus, valors de tamany adequat.

Descripció formal

A continuació es mostra una descripció de cóm funciona una firma Lamport, en notació matemàtica. Notar que el "mensage" en esta descripció és un bloc de $n$ senyes sent possiblement (pero no necessàriament) el resultat d'aplicar una funció hash al mensage que realment es vol firmar.

Claus

Siga $n$ un sancer positiu i siga $f:Y\to Z$ una funció unidireccional.

Per a $1\le i\le n$ i $j\in \{0,1\}$ el firmant elegix aleatoriamente $y_{i,j}\in Y$ i després calcula $z_{i,j}=f(y_{i,j})$.

La clau privada, $Y$, consistix en $2n$ valors $y_{i,j}$. La clau pública,$Z$, consistix en atres $2n$ valors $z_{i,j}$.

Firma d'un mensage

Siga $M$ el bloc descriptor del mensage: $M=f(mensaje)\in \{0,1{\}}^n$

$M=m_1\dots m_n$

La firma del mensage és:

$\mathrm{S}(m_1\dots m_n)=(y_{1,m_1},\dots ,y_{n,m_n})=(s_1,\dots ,s_n)$.

Verificació de la firma

Qui necessite validar la firma deu verificar que:

$f(s_i)=z_{i,m_i}$ para tot  $1\le i\le n$.

Es deu conservar els elements privats que formen la firma, la clau pública i el mensage original per a futures validació.

Per a que Eva puga falsificar una firma, deu poder invertir els valors de la clau pública. I açò s'assumix com un problema computacionalment inviable si s'usen valors de tamany adequat.

Inconvenients

El primer inconvenient és que es deu utilisar cada joc de claus una sola volta. La raó és que en firmar es fan visibles els $n$ elements privats que varen generar els $n$ elements públics. És dir, s'exponen el 50% dels elements que formen la clau privada, per lo tant una volta que es firma un document no es deu reutilisar el joc de clau pública i privada. Ademés es deu destruir el 50% remanente d'elements privats que formen la clau privada i no que varen ser exposts.

Un atre inconvenients és el de l'excessiva llongitut de les claus i la firma.