note:xaypn9ni

The 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 that is 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.