Why private key is not used in Camenisch-Lysyanskaya Signature generation?

Question

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}$.

Answer 1

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$.}