Camenisch-Lysyanskaya-Signaturverfahren

Das Camenisch-Lysyanskaya-Signaturverfahren, oft auch als CL-Signaturverfahren bezeichnet, ist ein kryptographisches Verfahren zum Erstellen digitaler Signaturen. Es wurde von den Kryptographen Jan Camenisch und Anna Lysyanskaya entwickelt und im Jahr 2002 publiziert.

Verfahren

Im Folgenden wird das Signaturverfahren im Detail beschrieben. Die Beschreibung weicht in Details von der Originaldarstellung ab und folgt der Darstellung von Camenisch und Groß.

Verwendete Parameter

Zuerst werden folgende Parameter festgelegt:

• $\ell _{n}$: Länge des verwendeten RSA-Moduls; typische Werte sind 1536 oder 2048.
• $\ell _{m}$: Maximale Länge der zu signierenden Nachrichten.
• $L$: Anzahl der mit einer Signatur signierbaren Nachrichten.
• $\ell _{e}$: Sicherheitsparameter; muss $>\ell _{m}+2$ sein.
• $\ell _{v}$: Sicherheitsparameter; typische Werte sind 80 oder 128.

Schlüsselerzeugung

Die Schlüsselerzeugung werden nun folgende Schritte durchlaufen:

• Man wählt zwei große Primzahlen $p,q$ gleicher Bitlänge $\ell _{n}/2$, für welche ${\frac {p-1}{2}},{\frac {q-1}{2}}$ ebenfalls prim sind. Man definiert $n=pq$. (Siehe hierzu Sophie-Germain-Primzahl.)
• Man wählt zufällige $S,Z,R_{1},\dots ,R_{L}\in QR_{n}$, wobei $QR_{n}$ die quadratischen Reste modulo $n$ beschreibt.

Der private Signaturschlüssel ist $(p,q)$, der öffentliche Verifikationsschlüssel besteht aus $(n,S,Z,R_{1},\dots ,R_{L})$.

Signieren einer Nachricht

Ein Tupel von Nachrichten $(m_{1},\dots ,m_{L})\in (-2^{\ell _{m}},2^{\ell _{m}})^{L}$ wird folgendermaßen signiert:

• Man wählt eine zufällige Primzahl $e$ mit Länge $\ell _{e}>\ell _{m}+2$, und $v\in [0,2^{\ell _{n}+\ell _{m}+\ell _{v}})$.
• Man berechnet $A=\left({\frac {Z}{S^{v}\prod _{i=1}^{L}R_{i}^{m_{i}}}}\right)^{1/e}\mod n$.

Die Signatur besteht dann aus $(e,A,v)$.

Verifizieren einer Signatur

Eine Signatur $(e,A,v)$ für ein Tupel $(m_{1},\dots ,m_{L})$ ist gültig falls:

• $m_{i}\in (-2^{\ell _{m}},2^{\ell _{m}})$ für alle $i=1,\dots ,L$,
• $2^{\ell _{e}-1}<e<2^{\ell _{e}}$, sowie
• $Z=A^{e}S^{v}\prod _{i=1}^{L}R_{i}^{m_{i}}\mod n$.

Sicherheit

Das Verfahren ist unter der starken RSA-Annahme sicher. Diese besagt, dass für einen zufälligen Modul $n$ der oben beschriebenen Form, und einem zufälligen $y\in \mathbb {Z} _{n}^{*}$ es nicht möglich ist, effizient ein $x\in \mathbb {Z} _{n}^{*}$ sowie ein $1<e\in \mathbb {N}$ zu finden, sodass $y=x^{e}\mod n$ gilt.

Verwendung

CL-Signaturen werden aufgrund ihrer Eigenschaften häufig als Bausteine für anonyme Authentifizierungsprotokolle verwendet, wie zum Beispiel für Idemix oder Direct Anonymous Attestation.