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



You must log in to answer this question.

Browse other questions tagged .