Camenisch-Lysyanskaya signature method

The Camenisch-Lysyanskaya signature process , often also referred to as the CL signature process, is a cryptographic process for creating digital signatures . It was developed by the cryptographers Jan Camenisch and Anna Lysyanskaya and published in 2002.

Procedure

The signature process is described in detail below. The description differs in details from the original representation and follows the representation of Camenisch and Groß.

Used parameters

First the following parameters are set:

• ${\displaystyle \ell _{n}}$: Length of the RSA module used ; typical values ​​are 1536 or 2048.
• ${\displaystyle \ell _{m}}$: Maximum length of the messages to be signed.
• ${\displaystyle L}$: Number of messages that can be signed with a signature.
• ${\displaystyle \ell _{e}}$: Security parameters; must be. ${\displaystyle >\ell _{m}+2}$
• ${\displaystyle \ell _{v}}$: Security parameters; typical values ​​are 80 or 128.

Key generation

The key generation will now run through the following steps:

• One chooses two large prime numbers of the same bit length , for which are also prime. One defines . (See Sophie-Germain-Prime number .) ${\displaystyle p,q}$ ${\displaystyle \ell _{n}/2}$ ${\displaystyle {\frac {p-1}{2}},{\frac {q-1}{2}}}$ ${\displaystyle n=pq}$
• One chooses random , with the quadratic residues modulo describes. ${\displaystyle S,Z,R_{1},\dots ,R_{L}\in QR_{n}}$ ${\displaystyle QR_{n}}$ ${\displaystyle n}$

The private signature key is , the public verification key consists of . ${\displaystyle (p,q)}$ ${\displaystyle (n,S,Z,R_{1},\dots ,R_{L})}$

Sign a message

A tuple of messages is signed as follows: ${\displaystyle (m_{1},\dots ,m_{L})\in (-2^{\ell _{m}},2^{\ell _{m}})^{L}}$

• One chooses a random prime number with length , and . ${\displaystyle e}$ ${\displaystyle \ell _{e}>\ell _{m}+2}$ ${\displaystyle v\in [0,2^{\ell _{n}+\ell _{m}+\ell _{v}})}$
• One calculates . ${\displaystyle A=\left({\frac {Z}{S^{v}\prod _{i=1}^{L}R_{i}^{m_{i}}}}\right)^{1/e}\mod n}$

The signature then consists of . ${\displaystyle (e,A,v)}$

Verifying a signature

A signature for a tuple is valid if: ${\displaystyle (e,A,v)}$ ${\displaystyle (m_{1},\dots ,m_{L})}$

• ${\displaystyle m_{i}\in (-2^{\ell _{m}},2^{\ell _{m}})}$for all , ${\displaystyle i=1,\dots ,L}$
• ${\displaystyle 2^{\ell _{e}-1}<e<2^{\ell _{e}}}$, such as
• ${\displaystyle Z=A^{e}S^{v}\prod _{i=1}^{L}R_{i}^{m_{i}}\mod n}$.

safety

The procedure is safe under the strong RSA assumption. This means that for a random module of the form described above and a random one, it is not possible to efficiently find one and one , so that . ${\displaystyle n}$ ${\displaystyle y\in \mathbb {Z} _{n}^{*}}$ ${\displaystyle x\in \mathbb {Z} _{n}^{*}}$ ${\displaystyle 1<e\in \mathbb {N} }$ ${\displaystyle y=x^{e}\mod n}$

use

Due to their properties, CL signatures are often used as building blocks for anonymous authentication protocols, such as for Idemix or Direct Anonymous Attestation .

swell

1. ↑ January Camenisch, Anna Lysyanskaya: A Signature Scheme with Efficient Protocols . In: Stelvio Cimato, Clemente Galdi, Giuseppe Persiano (eds.): Security in Communication Networks 2002 . tape 2576 . Springer, Berlin / Heidelberg, ISBN 3-540-00420-3 , pp. 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 (Eds.): ACM Conference on Computer and Communications Security 2008 . ACM, ISBN 978-1-59593-810-7 , pp. 345-356 , doi : 10.1145 / 1455770.1455814 .