# 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.

## Quellen

* ↑ Jan Camenisch, Anna Lysyanskaya: A Signature Scheme with Efficient Protocols. In: Stelvio Cimato, Clemente Galdi, Giuseppe Persiano (Hrsg.): Security in Communication Networks 2002. Band 2576. Springer, Berlin/Heidelberg, ISBN 3-540-00420-3, S. 268–289, doi:10.1007/3-540-36413-7_20.
* ↑ Jan Camenisch, Thomas Groß: Efficient Attributes for Anonymous Credentials. In: Peng Ning, Paul F. Syverson, Somesh Jha (Hrsg.): ACM Conference on Computer and Communications Security 2008. ACM, ISBN 978-1-59593-810-7, S. 345–356, doi:10.1145/1455770.1455814.