# Private key not used in a signature scheme

I'm trying to understand the following signature scheme (Camenisch-Lysanskaya):

Key generation: $$n = pq$$ special RSA modulus, $$a, b, c \in QR_n$$. $$PK = (n, a, b, c), SK = p$$.

Signing algorithm:

• $$m$$ message.
• $$e$$ random prime number (with some for this question unimportant length restriction).
• $$s$$ random number with very big length (unimportant for my question).
• Compute $$v^e \equiv a^m b^s c \bmod n$$. Output $$(e,s,v)$$.

Verification algorithm: Check that $$v^e \equiv a^m b^s c \bmod n$$ and check the length restriction of $$e$$.

I don't see why this is a valid signing algorithm. The secret key is not used for signing (or calculating $$e$$ or $$s$$). So everyone could make a signature like this and not just the one who created the public key.

Edit: If I understand it right, it's all about the hard computation of a $$v$$ and $$e$$ if you just have $$a^m b^s c$$. But how does it help there to know the factorization of $$n$$?

• Compute $$v^e \equiv a^m b^s c \pmod n$$. Output $$(e,s,v)$$.

• Solve $$v^e \equiv a^m b^s c \pmod n$$ for $$v$$. Output $$(e,s,v)$$.
If you can solve $$v^e \equiv u \pmod n$$ for $$v$$ without using $$p$$ in general, you have found a major breakthrough in cryptanalysis!
• Yes that is, what I also read. But how does it help for the calculation to know the factorization of $n$?
• Or the other way around: why can I solve the factorization problem if I would have found some $e, v$ to a given $u, n$ s.t. $v^e \equiv u \bmod n$?
• How does knowing the factorization of $n$ help to find $v$? If you know $p$ and $q$ so that $n = pq$, you can compute $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ and solve $e d \equiv 1 \pmod{\lambda(n)}$ for $d$ and compute $v \equiv (a^m b^s c)^d \pmod n$ as in RSA.  How does finding $v$ help to find the factorization of $n$? We don't know, except in the cases of even exponents, since knowing two distinct square roots $y$ and $y'$ of a common square $x\equiv y^2\equiv (y')^2\pmod n$ so that $(y+y')(y-y')=kn$ for some $k$ reveals the factorization of $n$ by $\gcd(n, y \pm y')$. Mar 25, 2019 at 16:24
• From a cursory glance, the security of this system seems to rely on the RSA problem, not directly on factorization. The RSA problem—inverting $x^e \bmod n$ for uniform random $x$ and appropriate choice of $e$—is certainly not harder than factoring, but it may be easier. Mar 25, 2019 at 16:27