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 _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves