[curves] qDSA signatures

[Joost Renes]

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.

> 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.

> 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.

> 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