Re: [openpgp] Proposal for a separable ring signature scheme compatible with RSA, DSA, and ECDSA keys

[Vincent Yu <[e-mail]>]

On 03/14/2014 05:50 AM, Werner Koch wrote:
> Why do we need a new registry?  I can't see a problem in using the
> existing public algorithms ids and declare that only certain algorithms
> may be used for ring signatures

This is a good point. I was worried that some people might object to 
having DSA keys being used as Schnorr keys, which is what's being done 
in the current proposal. The registry provides a way for a signer to 
state explicitly that this is intended, and provides some 
future-proofing in case a future extension to ring signatures uses DSA 
keys differently.

I anticipated potential objections because it is possible to modify or 
augment the proposal to use DSA keys in ways that more closely resemble 
DSA. The main alternative I considered is to use something like what Ren 
and Harn published in 2008 [RH08]. Their scheme provides a way to use 
ElGamal keys in a ring signature, and I think it can possibly be 
modified and integrated with Abe et al's scheme to use DSA keys directly 
as DSA keys. I didn't do so for the following reasons:

1. This alternative scheme produces signatures that are up to double the 
size of those from the current scheme.

2. Abe et al's scheme is much more widely read and cited (their paper 
has been cited more than 250 times, whereas Ren and Harn's paper has 
been cited less than 20 times). I'd prefer to stick to well-known schemes.

3. I had trouble parsing Ren and Harn's security proofs (but this could 
just be me being stupid).

But this is all beside the point since no one has actually objected so 
far. Looking back at my proposal, it does seem rather silly to have a 
registry that is currently redundant.

I agree with you that it is mostly useless. Unless someone has a better 
idea, I will remove the registry and modify the new signature subpacket 
to hold only the fingerprints of possible signers. This will nicely 
simplify things.

> (i.e. exclude the algo for a ring signature).
>
> I would also suggest to settle for ECC algorithms and not bother with
> RSA or DSA anymore.

A major consideration in the proposed scheme is to make sure that it is 
separable; i.e., that different types of existing keys can be used 
together without a dedicated setup. In the current scheme, signers are 
able to produce a ring signature without any cooperation or setup from 
the other possible signers (as long as they each have an RSA, DSA, or 
ECDSA signing key). I think this is an essential feature; otherwise, it 
would be a pain to make sure that all possible signers have the correct 
type of key.

Thus, I think it is important to have a new algorithm ID for ring 
signatures so that signers are free to mix together different types of 
keys in the ring signature. I would also prefer to leave RSA and DSA 
keys in the scheme for the same reason.

What ECC signing algorithms does the current development version of 
GnuPG support?

> Until a v5 public key packet format has been defined, I would strongly
> suggest to use the full SHA-1 fingerprint instead of a key id.  Creating
> long key id collisions is quite possible and thus would require extra
> code for trial verification.

Okay. dkg and David suggested similarly. I will modify my proposal to 
use full SHA-1 fingerprints.

Thanks!
Vincent

[RH08]
J. Ren and L. Harn (2008).
Generalized ring signatures.
doi:10.1109/TDSC.2008.22
https://v-yu.com/lib/2008_Ren,%20Harn.pdf