Lamport-Diffie Einmal-Signaturverfahren

Das Lamport-Diffie Eimal-Signaturverfahren (engl. Lamport-Diffie One-Time Signature Scheme, kurz: LD-OTS) ist ein Signaturverfahren, dass 1979 von Leslie Lamport und Whitfield Diffie entwickelt wurde. Es verwendet eine Einwegfunktion $H \!\,$, welche eine kollisionresistente Hashfunktion darstellt.

$H : \begin{Bmatrix}0,1\end{Bmatrix}^n \rightarrow \begin{Bmatrix}0,1\end{Bmatrix}^n, n \in \mathbb{N}$

LD-OTS verwendet zwei Schlüssel, einen Signaturschlüssel $x \!\,$ und einen Verifikationsschlüssel $y \!\,$. Um später ein Dokument mit $y \!\,$ zu verifizieren, muss außerdem die verwendete Einwegfunktion $H \!\,$ bekannt sein.

Schlüsselerzeugung

Der Signaturschlüssel ist ein String

$x = \Bigl(x(0,1), x(1,1), x(0,2), x(1,2), ..., x(0,n), x(1,n)\Bigr) \in \begin{Bmatrix}0,1\end{Bmatrix}^{2n}$

Der entsprechende Verifikationsschlüssel ist der String

$y = \Bigl(y(0,1), y(1,1), y(0,2), y(1,2), ..., y(0,n), y(1,n)\Bigr)\!\,$

    $= \Bigl(H(x(0,1)), H(x(1,1)), H(x(0,2)), H(x(1,2)), ..., H(x(0,n)), H(x(1,n))\Bigr) \!\,$

Erzeugung der Signatur

Die Signatur eines Dokuments $d = (d_\text{1}, ..., d_\text{n}) \in \begin{Bmatrix}0,1\end{Bmatrix}^n$ ist

$s = (s_{1}, ...,s_{n}) = (x(d_{1},1)), ..., x(d_{n},n)) \!\,$

Verifikation

Der Verifizierer kennt die Einwegfunktion $H \!\,$, den Verifikationsschlüssel $y \!\,$, das Dokument $d = (d_{1}, ..., d_{n}) \!\,$ und die Signatur $s = (s_{1}, ..., s_{n}) \!\,$.
Wenn

$(H(s_{1}), ..., H(s_{n}) = (y(d_{1},1), ..., y(d_{n},n)) \!\,$

gilt, dann ist die Signatur korrekt.

Sicherheit

Literatur

• Johannes Buchmann: Einführung in die Kryptographie. 5. Auflage. Springer Verlag, 2010, ISBN 978-3-642-11185-3, S. 220 ff..