Timeline for Logjam on Elliptic Curves?

6 events

when toggle format	what		by	license	comment
May 29, 2015 at 16:15	vote	accept	SEJPM
May 24, 2015 at 7:31	history	edited	Samuel Neves	CC BY-SA 3.0	Fix formula
May 23, 2015 at 14:57	comment	added	Samuel Neves		The first logarithm requires $\sqrt{\pi n / 2} / 2^k$ storage, where $k$ is, as above, the number of bits defining a distinguished point. For a 256-bit curve, your $2^{60}$ storage bound implies $k \ge 68$, since that is the amount of storage needed for a single discrete log. Bernstein and Lange suggested (eprint.iacr.org/2012/318) $k = 86$ and a precomputation of $2^{86}$ distinguished points---at a cost of $2^{172}$---making individual logarithms computable with $2^{86}$ effort. Reducing $k$ greatly increases the amount of work; I doubt $2^{30}$ speedup would be achievable.
May 23, 2015 at 13:17	comment	added	SEJPM		You need $i$ times the storage for solving the $i$th discrete logarithm? So it would be possible to reach a speedup of $2^{30}$ with storing $2^{60}$ samples resulting in a general effort of $2^{98}$ to break something like secp256?
May 23, 2015 at 0:39	history	edited	Samuel Neves	CC BY-SA 3.0	added 83 characters in body
May 23, 2015 at 0:34	history	answered	Samuel Neves	CC BY-SA 3.0