Thanks for your answers, Joost! Sent from my phone. Please excuse brevity and typos.
> On Jun 8, 2017, at 03:31, Joost Renes <j.re...@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
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves