[curves] qDSA signatures

[Mike Hamburg]

Thanks for your answers, Joost!

Sent from my phone.  Please excuse brevity and typos.

> On Jun 8, 2017, at 03:31, Joost Renes <j.renes at cs.ru.nl> wrote:
> 
> Hi Mike,
> 
> Thanks for having a look, and for your questions.
> 
>> This is cool work!  I like that you did hyperelliptic Kummer surfaces too.
> 
> Thanks!
> 
>> Do you run into any problems where x:z = 0:0 in any of the formulas?  That
>> would make Check always return true, but maybe it can’t happen?
> 
> Indeed, if you were to end up with the point (0 : 0) in verification,
> everything will vanish and Check returns true. Assuming honest
> execution, this never happens. The xDBLADD function computes the correct
> result if the difference is not in the 2-torsion, and in all of our
> calls we have as a difference a point of large prime order. Note that
> even if the scalar is a (multiple of) the group order, the ladder
> returns the point at infinity, which is (1 : 0).
> 
> You could potentially run into trouble if P (public generator) or Q
> (public key) are in the 2-torsion. In the first case your system
> parameters are simply not defined well, in which case you lose security
> (of course). In the second someone provides you with an invalidly
> generated public key, which you may want to check for. But this should
> not be any different than scenario's in other Schnorr/EdDSA protocols
> where public keys are invalid, and the same countermeasures should apply.

I see. So you might want to prevent someone from setting PK=2tor so that all signatures are valid, but otherwise you don't need to check.

>> Likewise, do you run into any problems if one of the points is on the twist?
>> It might be that eg Q is on the twist but [c]Q = small torsion point is on both the
>> curve and the twist, and so the verification goes through.  But maybe it’s hard
>> to cause this so the proof works anyway.
> 
> There are no problems here. We make a remark about this at the end of
> section 2.1, but let me elaborate.
> 
> The crucial idea is that verification does not assume rationality. If a
> Kummer point does not lift to J(F_p), it will indeed lift to J'(F_p).
> But, actually, it also lifts to J(F_p^2). That is, the Kummer point will
> always lift to J, but it may or may not be F_p-rational. The
> verification algorithm assumes the Kummer points to be images of points
> of J, but does not care whether those points on J were F_p-rational or not.

Makes sense. 

>> Do you know a good way to make the signature nonmalleable?  I settled for
>> malleable ones in STROBE, but it would be neat if there were a way to make
>> it nonmalleable.
>> 
> 
> We are not sure what you mean exactly. There is a trivial malleability,
> as both (R,s) and (R,-s) will be valid signatures. You could get rid of
> this by only accepting signatures where s is positive, for example. You
> may have to slightly adapt the proof to deal with this. In any case,
> this only allows you to get a valid signature on a message and public
> key for which you already have a valid signature, so the usefulness will
> be limited. As remarked in the original EdDSA paper, this is not all
> that significant for signature security.

Oh right, this is only tricky to do if you want both the standard verify algorithm and the x-only one to work.

>> Finally, are you sure that your trick of setting c <- Z_N+ is necessary?  It
>> seems to me that the probability that c1 = -c2 is negligible anyway, so the
>> proof would work just as well without this modification.  In that case, your
>> proof would probably cover STROBE’s implementation as well, except
>> that STROBE depends on the hash’s collision resistance.
>> 
> 
> We chose to do this because, arguably, it seems quite natural. It allows
> for a nice proof, cf. the original Schnorr signatures, without any error
> probabilities. As you say, allowing c to be in Z_N shouldn't be a
> problem. The soundness will only be true up to some error factor where
> c1 = -c2. Assuming that the probability of this happening is negligible,
> everything should work.
> 
> Joost

Thanks!
-- Mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2368 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170608/e3d920c9/attachment.bin>