On Sat, 7 May 2016 19:41:59 +0000 (UTC) lukep <lukep@xxxxxxxxxxxx> wrote: > Thanks isis for this, it looks really good, I look forward to seeing a > similar protocol for SIDH! (and X25519+NEWHOPE+SIDH !) When there is a sufficiently fast SIDH implementation, it might be worth considering (MS Research's is less slow than prior attempts at this, but misses the mark). On Sat, 07 May 2016 22:51:27 +0200 Jeff Burdges <burdges@xxxxxxxxxx> wrote: > On Sat, 2016-05-07 at 19:41 +0000, lukep wrote: > > It's hard to guarantee that any fixed, finite amount of SHAKE > > output will be sufficient for any rejection sampling method > > like gen_a. I think that being in the position to gather the timing information required on the client side means the adversary has won already, so I'm not seeing the issue here apart from an abstract theoretical sense. > Isn't some small multiple usually enough? I think 1024 is large > enough to tend towards the expected 42%ish failures. > > Also, can't one simply start the sampling over from the beginning if > one runs out? For clarity regarding what the code does now: The reference code generates excess output from the initial SHAKE call, and samples from that, and incrementally squeezes out an additional block one at a time as required (Enough for 1344 elements, with each additional squeeze providing 21 elements). (The rejection sampling algorithm is somewhat wasteful since it discards 2 bits of input per sample as well, but what's done now is easier to implement.) > I've no idea if an maybe an arithmetic coding scheme would be more > efficient. > > > Or let a be a system-wide parameter changing say on a daily basis? > > I mentioned using the Tor collaborative random number generator for a > in my other message, but only as feint to get to the meat of my > argument that Isis and Peter's proposal sounds optimal. I think > rotating a network wide a would get messy and dangerous in practice. > > If bandwidth is an issue, then a could be derived from the ECDH > handshake, thereby making it zero cost. Err. I'm not sure how that will work without rejection sampling that exposes timing information, maybe I'm missing something. I had a brief discussion with Dr. Schwabe regarding using deterministic `a` generation for unrelated reasons, with something time based being tossed around, but requiring a global clock isn't that great, and leaks clock skew information (Though I would use something like H(tweak | unixTime / 3600), which is rather coarse...), and as a peace of mind thing, I do prefer randomizing `a` on a per-connection basis. But anyway like I said, I don't think this is an issue. Regards, -- Yawning Angel
Attachment:
pgpbARWY_ueXs.pgp
Description: OpenPGP digital signature
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev