Firma de Lamport-Diffie

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

Para ${\displaystyle 1\leq i\leq n}$ y ${\displaystyle j\in \{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:

${\displaystyle f(s_{i})=z_{i,m_{i}}}$ para todo  ${\displaystyle 1\leq i\leq n}$.

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.