Assume that we have the following signature scheme CL Signature:

  • Choose a cyclic group $G = \langle g \rangle$ of order $q$.
  • Uniformly and randomly choose two elements $x,y \in \mathbb{Z}_q$, and compute $X = g^x$ and $Y = g^y$.
  • The secret key is $sk = (x,y)$, while the public key is $pk = (q, G, g, X, Y)$.
  • On input a message $m \in \mathbb{Z}_q$, secret key $sk$ and public key $pk$, choose a random $a \in G$ and output the signature: $$\sigma = (a, a^y, a^{x + xym}).$$

In the same paper, they ensure that $\sigma$ is NOT information-theoretically independent of the message $m$ being signed and propose an alternative that achieves this independent notion $$\sigma = (a, a^z, a^y, a^{zy}, a^{x + xy(m + zr)}),$$ where $z,r \in \mathbb{Z}_q$ are another uniformly random elements such that $Z = g^z$ is also part of the public key $pk$.

Several questions arises on that:

  1. What exactly means to be information-theoretically independent?
  2. Why it is not achieved by the first scheme?
  3. What happens if we change $a^{x + xy(m + zr)}$ with $a^{x + xy(m + r)}$?

Intuitively, I think that being information-theoretically independent means that the signature reveals no information about the message $m$. Then, why the first one reveals something about the message $m$?


1 Answer 1


Note that in the first variant given a signature and knowing the public key, the message $m$ is uniquely determined. Information-theoretically dependent means what you assume it means. An unbounded adversary who can compute all discrete logs, can thus easily figure out the unique $m$ in the first scheme.

In the second variant, the message is information-theoretically hidden (even for unbounded adversaries). Note that $m+zr$ is basically „an encryption“ with a secret key $r$ (and $r$ does not appear anywhere else). So for $v=m+zr$ you can always find a suitable $r‘$ for any possible choice of $m‘$. This information-theoretically hides the message.

The problem with your modification is as follows. In the second variant a message is $(m,r)$. If you modify it to $a^{x+xy(m+r)}$ then you can open your signature to any message $m‘$ by computing $r‘=(m+r)-m‘$ and providing $(m‘,r‘)$ as the new message. This clearly will verify. Thus, your modification does not yield an unforgeable signature scheme. For the second variant of the CL signatures, however, the scheme can be shown to be unforgeable as $z$ basically commits you to the $r$ value.

  • $\begingroup$ Thanks for the answer. Anyways, do you have any intuition why the first signature is not good in practice? The mentioned problem is a realistic "problem" inside the post-quantum world. $\endgroup$
    – Bean Guy
    Dec 4, 2020 at 14:31
  • $\begingroup$ I think one cannot say that it is "not good in practice" without having a concrete application in mind. Sure if you want to hide messages unconditionally when seeing only signatures without messages even if you have a powerful quantum computer, then the second scheme makes sense. But note that you could achieve that with any signature scheme by simply signing an unconditionally hiding commitment to the message instead of the message itself. Do you have a concrete application in mind? $\endgroup$
    – DrLecter
    Dec 4, 2020 at 15:15
  • $\begingroup$ The CL Signature is used for anonymous credentials. I think unconditionally hiding is needed here because you are identified through commitments. If you use $g^x$ as your "identification" for different organizations, then they will obviously know that they are interacting with the same user (since they know $g$). $\endgroup$
    – Bean Guy
    Dec 4, 2020 at 15:31
  • $\begingroup$ Yes, sure in this case you want to have commitments to the values and so the second variant is the one to go for. $\endgroup$
    – DrLecter
    Dec 4, 2020 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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