Yawning Angel transcribed 4.3K bytes:
On Sat, 7 May 2016 19:41:59 +0000 (UTC) lukep lukep@tutanota.com 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).
When there is also sufficient cryptanalysis of curve-isogeny-based cryptosystems…
Also, I'm not understanding what SIDH would provide in an X25519+NewHope+SIDH construction which is not already provided in the X25519+NewHope construction, unless someday there are SIDH-based signatures.
On Sat, 07 May 2016 22:51:27 +0200 Jeff Burdges burdges@gnunet.org 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.
Your point that an adversary with native-code execution on the client's machine is capable to do worse makes sense. However, given that there are browser-based cache timing attacks (e.g. RowhammerJS) which give cache eviction rates only negligably different to those of native-code exploits, I would argue that Jeff's original concern that the timing attack presents a distinguisher is actually a valid concern.
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.
Nope, it would still not work to fix the timing attack. Although, luckily, we already wrote some constant time code for my sorting-network idea, and then, with some coffee, Peter made it faster. (Give us something stronger to drink, and we'll probably come up with a way to get it even faster.)
Best,