Fujisaki & Suzuki's Traceable Ring Signature paper, which allows for a signature by one private key out of a ring of public keys to sign, and for anyone to verify that one member of the ring signed, without disclosing which member of the ring signed, unless the same member of the ring signs two different messages under the same tag ('double spends'), in which case it is possible to identify the double spender.
For a ring of $n$ signers, both the signing protocol and the verification protocol depends on $\sigma_j$ for $i \in [1..n]$. Where $i$ is the position of the true signer in the ring, $\sigma_i$ is determined based on the private key, ring members, and issue. The traceability is then based on the idea that with only one message for a private key / ring / issue triple, it should be intractable to determine which $\sigma_j$ is the constrained one without the private key. However, if the same signer signs two messages for the same ring/issue, then $\sigma_i$ will be the same across the two messages, identifying both messages came from signer $i$. The paper points out, however, that if the protocol were to give signer a free hand to choose $\sigma_j$ for $j \neq i$, a signer could frame another signer as having double signed.
To overcome this, the paper instead describes a scheme for expressing all the $\sigma_j$ as a line with an intercept fixed by the algorithm based on a hash of the inputs, and a slope (determined by the signer based on $i$, the intercept, and $\sigma_i$).
The paper expresses the $\sigma_j$ values as being a member of a "multiplicative group G of prime order q" with no further information about what they had in mind for that group. I would therefore like to pick $G$ as the elliptic curve Curve25519, which seems to fit within the assumptions of the authors.
However, this brings up a challenge with this scheme of putting the $\sigma_j$ values on a line. The paper says:
Set $A_0 = H'(L, m)$ and $A_1 = ({\sigma_i \over A_0})^{1/i}$
There are a several possible interpretations for how to compute $A_1$ from this. Apparently the codomain of $H'$ is also $G$. Interpreting this as an expression in $G$ (which someone else asked about previously: How to compute $x^{1/y}$?), however, would mean solving the Elliptic-Curve Discrete Logarithm Problem. The security of the entire scheme in the paper depends on that being intractable over whatever $G$ is chosen, so I think the interpretation of doing it using the field operations probably doesn't make sense - and I think that the authors must have intended that the operation be performed on the raw number that identifies a point in the group is an option.
My question therefore is: Since Curve25519 uses compressed elliptic points that can be identified by a single integer $x$, would a safe and correct implementation be to calculate $A_1 = ({\sigma_i \over A_0})^{1/i}$ on the $x$ coordinate of the point?
One problem I can see with this is that only $1/8$ of all values are points on the curve for Curve25519, and if the signing algorithm ensures that $\sigma_i$ comes out as on the curve but not $\sigma_j$ for $i \neq j$, then that could rule out 7/8th of the possible ring participants as the source of a signature (which would be an unacceptable information leak).
Would a reasonable fix for this be to make the verification protocol calculate $\sigma_j^{'}$ from $A_0$ and $A_1$, and then increment the x coordinate repeatedly until a point on the curve ($\sigma_j$) is obtained? And then the signer could decrement the $x$ coordinate of $\sigma_i$ repeatedly to obtain the largest $X < \sigma_i$ that is not on the curve, and then randomly sample equiprobably an x coordinate $x \leftarrow [X+1..\sigma_i]$, and use that to compute $A_1$. That way, an adversary wouldn't be able to tell whether a given $j$ value is $i$, but the $\sigma_i$ values would be constrained to prevent the attack in the paper. Are there any obvious problems with this implementation that I am missing?
