Why is this signature independent of the message?

Question

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$?

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.