# Proving the possession of signature in zero-knowledge

Does anybody know an efficient mechanism to prove the possession of a digital signature (e.g. RSA) on a certain attribute (message) in zero-knowledge? That is, without revealing the actual signature (against tracking, for privacy) prove that you have one? Thanks a lot in advance!

• It would be trivial if you could generate the signature in question. Is this your scenario? – rath May 5 '14 at 13:05
• My scenario is that the attribute is signed by another party. That is, I can not generate the signature. Instead, I'd like to prove I have this signature without revealing it. This should happen in such a way that two different proof session are unlinkable to each other. – OnTarget May 5 '14 at 13:22
• If both of you possess the signature you could ask for a nonce and reply with the hash of the nonce and the signature. I take it only one party has the signature? – rath May 5 '14 at 13:29
• Are you familiar with the concept of multi-show (unlinkable) anonymous credentials? They are built upon re-randomizable signature schemes which have the properties you require and are used in exactly the way you want it. Well known candidates are CL credentials Strong RSA or Pairing based or built upon the pairing based BBS signature scheme. – DrLecter May 5 '14 at 13:36
• I meant, the requirement of user anonymity (with respect to user-side secrets) against the issuer during the issuance of the credential. Verifier and Issuer are parts of one system in my case, so they do communicate with each other. With respect to "one-show" I really meant "multi-show and unlinkable". Since both CL and BBS are fairly complex, I would like to know if there is any high-level description of such systems (e.g. a lecture, etc.). For example, both of them essentially use a public reference parameter with certain trapdoor built in (to issuer credentials)..... And so on. Thanks! – OnTarget May 5 '14 at 17:31

Guillou and Quisquater (link) present a zero-knowledge proof of an RSA signature. Basically, the scheme is as follows:

Public knowledge: RSA modulus $n$, public RSA exponent $v$, preimage $X$.

Secret knowledge for prover: $A$, such that $A^v = X \mod n$.

$$\begin{matrix} \mathcal{P} & & \mathcal{V} \\ r \xleftarrow{\} \mathbb{Z}_n^* \phantom{\mod n} & & \\ T \leftarrow r^v \mod n & & \\ & \xrightarrow{\quad{}T\quad{}} & \\ & & d \xleftarrow{\} \{0,1,\ldots,v-1\} \\ & \xleftarrow{d} & \\ t \leftarrow A^dr \mod n & & \\ & \xrightarrow{\quad{}t\quad} & \\ & & t^v \stackrel{?}{=} X^{d}T \mod n \end{matrix}$$

In this diagram, $\leftarrow$ denotes assignment of a value to a variable and $\xleftarrow{\$}$denotes uniformly random selection from a finite set. • Nice, but here you require that signer and verifier are distinct entities and do not communicate, because any verifier must not know the factorization of$n$(and in a previous comment the OP wrote "Verifier and Issuer are parts of one system in my case, so they do communicate with each other."). But this could be solved by requiring the issuer issue a blind signature (anyways, one would then still not achieve unlinkability of showings when conducting several proofs - the OP wants multi-show unlinkability - under the assumption that issuer and verifier collude). – DrLecter May 6 '14 at 11:33 • Thanks, @Alan, for an interesting link. The only problem in this case is that even if verifiers and the issuer do not collude, the verification sessions are traceable, since for each verification the prover has to deliver his "identity" which is used to check the proof (in my previous terms, to "bootstrap" verification). I guess that was one of the motivations to resort to more complex CL-like signatures. Any ideas on how to make Guillou and Quisquater method "multi-show" in a privacy-preserving sense (let's assume at first that verifiers and the issuer do no collude)? – OnTarget May 6 '14 at 13:49 • You can use Ferguson's randomized blind signature protocol (oai.cwi.nl/oai/asset/5290/05290D.pdf) for issuing the credentials. (You want the protocol from figure 1, in which the bank signs a jointly generated and perfectly blinded random value.) – Alan May 6 '14 at 14:17 • How about a "small patch": simply randomizing the reference parameter$X$on each session? Then, on each verification, additionally generate$s \in_{R} Z_{n}^{*}$and deliver$X_{r}=X^{s}$(instead of$X$) along with T as well as$K=s^{v}$. Then compute$t$as$t \leftarrow A^{ds}rs$. To verify, compare$t^{v} \overset{?}{=} X_{r}^{d} TK$. What do you think, guys? – OnTarget May 6 '14 at 14:25 • Generating the credential:$z \xleftarrow{\$} \{0,1,\ldots,2^{|n|}-1\}; y \leftarrow zv; X \leftarrow g^y \mod n; A \leftarrow g^z \mod n$. Since $y$ is necessarily kept secret, the verifier cannot tell it is a multiple of $v$. – Alan May 8 '14 at 11:15

One-Way Aggregate Signatures (OWAS) (also called composite signatures) can be used to do this. They are based on BLS signatures. I will skip the notation except mention that they are based on bilinear pairings. The above links will give the details.

Let $H$ be a hash function and $x_1$ be the private key. The public key is $y_1=g^{x_1}$. For any message $m_1$, the signature is $\sigma_1={h_1}^{x_1}$, where $h_1 = H(m_1)$. To verify the signature, test that: $\hat{e}(\sigma_1, g) \stackrel{?}{=} \hat{e}(h_1, y_1)$ holds.

Let $x_2$ be another private key. The public key is $y_2=g^{x_2}$. As before, for any message $m_2$, the signature is $\sigma_2={h_2}^{x_2}$, where $h_2 = H(m_2)$. To verify the signature, test that: $\hat{e}(\sigma_2, g) \stackrel{?}{=} \hat{e}(h_2, y_2)$ holds.

We can also combine $\sigma_1, \sigma_2$ into an aggregate signature $\sigma$ as follows: $\sigma=\sigma_{1}\cdot \sigma_{2}$. To verify, we check that: $$\hat{e}(\sigma, g) \stackrel{?}{=} \hat{e}(h_1, y_1)\cdot\hat{e}(h_2, y_2)$$

The signatures satisfy the standard security as shown in the Aggregate Signatures Paper. That is, assuming that the Diffie-Hellman problem is hard, presentation of $\sigma$ proves that $y_1$ signed $m_1$ and $y_2$ signed $m_2$ (even if the original signatures are not provided).

The security of OWAS relies on the fact that given just $\sigma$, it is hard to compute either $\sigma_1$ or $\sigma_2$ (as hard as solving Diffle-Hellman problem). In fact, for two combined signatures, the resulting signature is a zero-knowledge proof of knowledge of each individual signature. This can be shown as follows:

Suppose I can control the output of the hash function (i.e., we are using the "random oracle model"), then instead of doing it the correct way as described above, given $(g, h_1, y_1)$, I can compute a fake tuple $(\sigma, h_2, y_2)$ such that the last verification equation above holds. First generate random $a, b$. The compute:

$$y_2=g^a y_1$$ $$h_2=\frac{g^b}{h_1}$$ $$\sigma=\frac{{y_1}^b\cdot g^{ab}}{{h_1}^a}$$

It can be checked that the above values satisfy the aggregate signature verification equation. Yet, I did this without knowing $\sigma_1$. Hence this is zero-knowledge.