Jeff Burdges transcribed 2.6K bytes:
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.
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?
Yes, you can safely start the sampling over from the beginning without giving anything away, other than "the seed was bad".
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.
Peter and I also discussed generating `a` from the Tor shared randomness, but ultimately I feel squeamish about the potential anonymity-set segregations.
If bandwidth is an issue, then a could be derived from the ECDH handshake, thereby making it zero cost.
That would add an extra RT to the handshake, since the handshakes could no longer happen in parallel (in my construction, they're actually literally side-by-side, in the same CREATE2V cell). Separating the handshake would also mean we'd need some new cell types to handle the fact that the handshake would take 2 RTs, since Tor's design now assumes ---CREATE*--> then <---CREATED*---.
Also, deriving `a` "somehow" from the shared X25519 secret is a bit scary (c.f. the §3 "Backdoors" part of the NewHope paper, or Yawning's PoC of a backdoored NewHope handshake [0]).
[0]: https://git.schwanenlied.me/yawning/newhope/src/nobus/newhope_nobus.go
Best,