1
$\begingroup$

I want to implement Camenisch-Lysyanskaya Signatures based on the strong RSA (SRSA) assumption using python. However, I have a question. Here public key of the signature PK=(n,a,b,c) and private key SK=p But while signing the message, only the parameters from public key is used. Am I missing something because for signing the message private key is required? Or is it a specialty of the Camenisch-Lysyanskaya Signature? Holder can generate signature without Issuer's private key.

From the article:

2.2 The Scheme

Key generation. On input $1^k$, choose a special RSA modulus $n = pq$, $p = 2p′ + 1$, $q = 2q′ + 1$ of the length $n = 2k$. Choose, uniformly at random, $a, b, c \in QR_n$. Output $PK = (n, a, b, c)$, and $SK = p$.

Message space. Let $\ell_m$ be a parameter. The message space consists of all binary strings of length $\ell_m$. Equivalently, it can be thought of as consisting of integers in the range $[0, 2^m)$.

Signing algorithm. On input $m$, choose a random prime number $e$ of length $e \ge \ell_m + 2$, and a random number $s$ of length $\ell_s = \ell_n + \ell_m + l$, where $l$ is a security parameter. Compute the value $v$ such that$$v^e \equiv a^m\,b^s\,c \pmod n$$

Verification algorithm. To verify that the tuple $(e, s, v)$ is a signature on message $m$ in the message space, check that $v^e \equiv a^m\,b^s\,c \pmod n$, and check that $2^{\ell_e} > e > 2^{\ell_e-1}$.

$\endgroup$
1
  • 1
    $\begingroup$ The problem it's that the description of the signing algorithm unhelpfully just states "compute something for which the verification equation holds". To actually compute that, you'll need $p$ (or some equivalent information). $\endgroup$
    – Maeher
    Nov 6, 2022 at 9:47

1 Answer 1

3
$\begingroup$

As pointed in comment, while the private key is not used in the signature step in the citation, that's only because $v^e=a^m\,b^s\,c\pmod n$ is the verification equation, and gives no way to compute $v$ for one knowing the public key $(n,a,b,c)$, and able to choose the nonces $e$, $s$, and the message $m$. That's actually required: in any secure signature scheme, it is not possible to sign a message using the public key.

$v$ can be computed as in textbook RSA decryption, that is

  • $\lambda\gets(n-p-n/p+1)/2\,$. Note: Given the form of $p$ and $q$, that $\lambda$ is $2\,p'\,q'$, the Carmichael function for $n$ †.
  • $d\gets e^{-1}\bmod\lambda$
  • $z\gets a^m\,b^s\,c\bmod n$
  • $v\gets z^d\bmod n$

This is what the authors have in mind when, in a setup with parameters‡ $\ell_n=1024$, $\ell_m=160$, $\ell_e=162$, $\ell_s=1346$, they estimate the cost of signing as [my comments]:

this signature scheme requires one short (160-bit [for $a^m\bmod n$]) and two long (1024 [for $z^d\bmod n$]) and 1346 [for $b^s\bmod n$]) exponentiations for signing.

For better performance we can rewrite the last two steps as

  • $v\gets a^{(m\,d\bmod\lambda)}\,b^{(s\,d\bmod\lambda)}\,c^d\bmod n$,

which allows using Shamir's trick during the simultaneous exponentiation. In it's simplest form that simultaneously scans the bits of the three exponents $m\,d\bmod\lambda$, $s\,d\bmod\lambda$, and $d$, and proceed by the square and multiply binary modular exponentiation method except it's multiplied by one of $2^3=8$ precomputed values $a\,b\,c\bmod m\,$, $a\,b\bmod m\,$, $a\,c\bmod m\,$, $a\,$, $b\,c\bmod m\,$, $b\,$, $c\,$, $1$ according to if the three exponent bits are 111, 110, 101, 100, 011, 010, 001, 000. Cost is about $\ell_n$ modular squarings and $\ell_n$ modular multiplications, a saving by a factor $>2$.

But if speed of signature is really a concern (and the cost of generating the random prime $e$ not dominating) we may use the CRT method for a further saving by a factor $>3$:

  • one-time precomputations:
    • $q\gets n/p$
    • $q_\text{inv}\gets q^{-1}\bmod p$
    • $a_p\gets a\bmod p$ and $a_q\gets a\bmod q$
    • $b_p\gets b\bmod p$ and $b_q\gets b\bmod q$
    • $c_p\gets c\bmod p$ and $c_q\gets c\bmod q$
  • signature, after drawing $e$ and $s$
    • $d_p\gets e^{-1}\bmod(p-1)$ and $d_q\gets e^{-1}\bmod(q-1)$
    • $v_p\gets a_p^{\left(m\,d_p\bmod(p-1)\right)}\,b_p^{\left(s\,d_p\bmod(p-1)\right)}\,c_p^{d_p}\bmod p$, possibly per Shamir's trick
    • $v_q\gets a_q^{\left(m\,d_q\bmod(q-1)\right)}\,b_q^{\left(s\,d_q\bmod(q-1)\right)}\,c_q^{d_q}\bmod q$, possibly per Shamir's trick
    • $v\gets\bigl((v_p-v_q)\,q_\text{inv}\bmod p\bigr)\,q+v_q$

Note: especially when using the CRT method, the signature should be verified before being revealed, in order to avoid fault attacks. Also, side-channel attacks are to be feared.


If there's a much faster technique, I want to know.


We could use Euler's totient $\phi=(p-1)(q-1)$ as in the original RSA article;. But $\lambda=\operatorname{lcm}(p-1,q-1)$ is mathematically satisfying: $e\,d\equiv1\bmod\lambda$ is a necessary and sufficient condition for a valid $(e,d)$, when $e\,d\equiv1\bmod\phi$ is sufficient but no necessary. Using $\lambda$ is allowed by the de-facto RSA standard PKCS#1-v2.2, and mandated in FIPS 186-4.

This choice of parameters is dated, nowadays we'd want at least $\ell_n=2048$, $\ell_m=256$.

$\endgroup$
5
  • $\begingroup$ Thank you for the reply. From traditional RSA Φ=(1-p)(1-q) then de=1 mod Φ . However, from your post λ=n-p-[n/p]+1. Could you explain the difference? $\endgroup$ Nov 6, 2022 at 14:48
  • $\begingroup$ From your reply, I guess that the value of e and d both are hidden from the user (Alice) by the Issuer. However, for selective disclosure (an advantage of CL signature), user (Alice) must know the value of d. But that creates the contradiction. user (Alice) can generate the original signature without the private key of the issuer. Please explain this problem. Reference: medium.com/finema/… $\endgroup$ Nov 6, 2022 at 15:21
  • $\begingroup$ Originally, I want to implement the anonymous credential with selective disclosure using CL signature. I checked this article Efficient Attributes for Anonymous Credentials, author Jan Camenisch and Thomas Groß but could not understand. The reference article is helpful but not clear about the point explained on the top comment section. $\endgroup$ Nov 6, 2022 at 16:34
  • 1
    $\begingroup$ @user1850484: I added a note on the use of $\lambda$. Sorry I'm not fully getting the rationale of Camenisch-Lysyanskaya Signature, and can't answer your other comments. $\endgroup$
    – fgrieu
    Nov 6, 2022 at 17:10
  • $\begingroup$ Thank you. Could you explain this line: p, q primes (usual DL setup: q|p − 1). What is the relation between p and q ? Could you give an example. $\endgroup$ Nov 6, 2022 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.