The traceable ring signature used in cryptonote
https://cryptonote.org/whitepaper.pdf looks like:
KEYGEN: P_i=x_i*G, I_i=x_i*H(P_i)
SIGN: as signer j; random s_i, w_i
(I relabeled q_i as s_i to be more standard, and relabeled the signer s as signer j)
IF i=j THEN L_i=s_i*G ELSE L_i=s_i*G+w_i*P_i
IF i=j THEN R_i=s_i*H(P_i) ELSE R_i=s_i*H(P_i)+w_i*I_j
c=h(m,L_1,...,L_n,R_1,...,R_n)
IF i=j THEN c_i=c-sum_{i!=j}(c_i) ELSE c_i=w_i
IF i=j THEN r_i=w_i-c_i*x_i ELSE r_i=w_i
\sigma = (m,I_j,c_1,...,c_n,r_1,...,r_n)
VERIFY:
L_i'=r_i*G+c_i*P_i
R_i'=r_i*H(P_i)+c_i*I_j
sum_{1..n}( c_j ) =? h(m,L_1',...,L_n',R_1',...,R_n')
LINK: reject duplicate I_j values.
where H(.) is a hash2curve function (taking a value in Zn and deterministically mapping it to a curve point), and h(.) is a hash function with a hash output size very close to n the order of the curve, ie h(.)=SHA256(.) mod n.
Towards finding a more compact ring signature I'd been trying to find a way to make c_i into a CPRNG generated sequence as they are basically arbitrary, though they must be bound to the rest of the signature (non-malleable) so that you can compute at most n-1 existential signature forgeries without knowing any private keys.
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.
This alternate linkable ring signature tends to 1/2 the size of the crypto note ring signature as the signature is 3+n values vs 2+2n values.
Adam
