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.^[1]

Verfahren Bearbeiten

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ß.^[2]

Verwendete Parameter Bearbeiten

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

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

[1] 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.

[2] 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.

[1]

[2]