Firma de Lamport-Diffie

La Firma de Lamport es un esquema de firma digital de un solo uso, inventada por Leslie Lamport en 1979.^[1]​ La firma se aplica sobre mensajes sin efectuar ninguna modificación previa de los mismos.

La esquema de firma de Lamport utiliza un juego de claves, compuesto por una clave privada y una clave pública. La clave privada es un conjunto de ${displaystyle 2*n}$ elementos privados. La clave pública es otro conjunto de ${displaystyle 2*n}$ elementos, formados, generalmente, por la aplicación de una función hash a cada elemento privado. Para firmar un documento, se aplica una función hash al documento del que se obtienen ${displaystyle n}$ bits, y se utilizan para seleccionar ${displaystyle n}$ elementos de la clave pública.

La firma de Lamport se debe utilizar una sola vez por cada juego de claves. Sin embargo, combinado el esquema de firma de Lamport con un Árbol de Merkle, un solo juego de claves podría usarse para firmar varios mensajes, lo que la convierte en un esquema de firma digital bastante eficiente.

El desarrollo potencial de la computación cuántica amenaza la seguridad de muchas formas comunes de criptografía como RSA, pero se cree que las firmas de Lamport estarían seguras si se usan, como componentes de las claves, valores de tamaño adecuado.

A continuación se muestra una descripción de como funciona una firma Lamport, en notación matemática. Notar que el "mensaje" en esta descripción es un bloque de ${displaystyle n}$ datos siendo posiblemente (pero no necesariamente) el resultado de aplicar una función hash al mensaje que realmente se quiere firmar.

Sea ${displaystyle n}$ un entero positivo y sea ${displaystyle f:,Y ightarrow Z}$ una función unidireccional.

Para ${displaystyle 1leq ileq n}$ y ${displaystyle jin {0,1}}$ el firmante elige aleatoriamente ${displaystyle y_{i,j}in Y}$ y luego calcula ${displaystyle z_{i,j}=f(y_{i,j})}$.

La clave privada, ${displaystyle Y}$, consiste en ${displaystyle 2n}$ valores ${displaystyle y_{i,j}}$. La clave pública,${displaystyle Z}$, consiste en otros ${displaystyle 2n}$ valores ${displaystyle z_{i,j}}$.

Sea ${displaystyle M}$ el bloque descriptor del mensaje: ${displaystyle M=f({mensaje})in {0,1}^{n}}$

${displaystyle M=m_{1}ldots m_{n}}$

La firma del mensaje es:

${displaystyle operatorname {S} (m_{1}ldots m_{n})=(y_{1,m_{1}},ldots ,y_{n,m_{n}})=(s_{1},ldots ,s_{n})}$.

Quien necesite validar la firma debe verificar que:

Se debe conservar los elementos privados que forman la firma, la clave pública y el mensaje original para futuras validaciones.

Para que Eva pueda falsificar una firma, debe poder invertir los valores de la clave pública. Y esto se asume como un problema computacionalmente inviable si se usan valores de tamaño adecuado.

El primer inconveniente es que se debe utilizar cada juego de claves una sola vez. La razón es que al firmar se hacen visibles los ${displaystyle n}$ elementos privados que generaron los ${displaystyle n}$ elementos públicos. Es decir, se exponen el 50% de los elementos que forman la clave privada, por lo tanto una vez que se firma un documento no se debe reutilizar el juego de clave pública y privada. Además se debe destruir el 50% remanente de elementos privados que forman la clave privada y no que fueron expuestos.

Otro inconvenientes es el de la excesiva longitud de las claves y la firma.