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

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 Sz 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 Sz May 8 '14 at 11:15