I'm studying the CL (Camenisch-Lysyanskaya) signature: Jan Camenisch and Anna Lysyanskaya, A signature scheme with efficient protocol, in proceedings of SCN 2002.

However, I cannot understand the relationship between special RSA modulus and quadratic residue.

definitions and notations

What is the relationship between Special RSA modulus and quadratic residue?

And please recommend references for special RSA modulus.


1 Answer 1


The standard RSA ($c=m^{e}$ $mod(n)$) is not semantically secure, since it reveals one bit information about the message. This information is jacobi symbol of the message. You can find many resources about jacobi symbol but basically it states that a value is in $QR_n$ or not. In CL signature, we can handle with this situation easilly, since we determine the base values for exponentiation operations. If we choose the base values from $QR_n$, any exponentiation operation using them outputs another value from $QR_n$. Thus, there is no revealed information. Ofcourse, it comes with a disadvantage that any output of exponentiation is in $QR_n$ we decrase the number of possible outputs that we can get.

  • 1
    $\begingroup$ Correction: the Jacobi signal does not state whether a value is a QR or not. A QR (that is relatively prime to n) will always have a Jacobi symbol of 1; however (assuming n is composite) there are also non-QRs that will also have a Jacobi symbol of 1. $\endgroup$
    – poncho
    Commented Aug 22, 2020 at 2:22

Your Answer

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

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