Quote from: adam3us on March 01, 2015, 12:19:30 PM

I found this paper "1-out-of-n Signatures from a Variety of Keys" by Abe, Ohkubo and Suzuki http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.363.3431&rep=rep1&type=pdf section 5.1 shows a way to do it. I show here how to add traceability to it in a way that makes it compatible with crypto note:

KEYGEN: P_i=x_i*G, I_i=x_i*H(P_i)

SIGN: as signer j; \alpha = random, \forall_{i!=j} s_i = random

c_{j+1} = h(P_1,...,P_n,\alpha*G,\alpha*H(P_j))
c_{j+2} = h(P_1,...,P_n,s_{j+1}*G+c_{j+1}*P_{j+1},s_{j+1}*H(P_{j+1})+c_{j+1}*I_j)
...
c_j = h(P_1,...,P_n,s_{j-1}*G+c_{j-1}*P_{j-1},s_{j-1}*H(P_{j-1})+c_{j-1}*I_j)

so that defines c_1,...,c_n with j values taken mod l some number of signers. Next find the s_j value:

Now \alpha*G = s_j*G+c_j*P_j so \alpha = s_j+c_j*x_j so s_j = \alpha - c_j*x_j mod n.

Similarly \alpha*H(P_j) = s_j*H(P_j)+c_j*I_j so \alpha works there too.

\sigma = (m,I_j,c_1,s_1,...,s_n)

VERIFY:

\forall_{i=1..n} compute e_i=s_i*G+c_i*P_i and E_i=s_i*H(P_i)+c_i*I_j and c_{i+1}=h(P_1,...,P_n,e_i,E_i)

check c_{n+1}=c_1

LINK: reject duplicate I_j values.

It looks like Joseph Liu, Victor Wei and Duncan Wong made the same observation in "Linkable Spontaneous Anonymous Group
Signature for Ad Hoc Groups" 2004 https://eprint.iacr.org/2004/027.pdf

The proposed scheme is basically the same as what I propose above, and the Liu, Wei & Wong 2004 publication seems to predate the 2007 Fujisaki & Suzuki "Traceable ring signature" https://eprint.iacr.org/2006/389.pdf cited by cryptonote.

Adam