On Sun, Jun 14, 2015 at 1:59 PM, D. J. Bernstein <[email protected]> wrote: > > Example: A standard way to hide bits of n in computing nP is to instead > compute (n+rl)P, where l is the order of P and r is chosen randomly. How > long does r have to be for rl to actually randomize all the bits of n? > > If the prime is very close to 2^k then l will also be within roughly > 2^(k/2) of 2^k by Hasse's theorem (for cofactor 1; similar statements > apply to other standard cofactors), so if r is below k/2 bits then the > top bits of n won't be randomized. This is obviously unacceptable--- > ample reason to recommend r above k/2 bits, whereas for "random" primes > people typically recommend 32 bits or 64 bits. > > People listening to Lochter's talk, or reading the slides, would have > acquired the impression that this was a new recommendation based on a > new attack:
Certainly this has been raised this before [1,2,3]. I don't think the talk was misleading, but I'm not sure what new info it adds, and I'm not sure how it makes a strong argument for random vs "special" primes. Random field primes are ~2x faster than special primes like Curve25519 and Goldilocks, given a special implementation. But a certain technique (scalar blinding) for power sidechannel resistance is slower for special primes. It would be great to have a clearer idea what the apples-to-apples blinding factors are between, say, Curve25519 vs a random 256-bit prime. I've seen suggestions for a 32 or 64 bit blinding factor for the random prime, and a 128-256 bit blinding factor for Curve25519. So that puts the slowdown in the range: (256+128) / (256+64) = 1.2 (256+256) / (256+32) ~= 1.8 Anyways, I think the concern is hardware that (a) needs power sidechannel protection, (b) chooses scalar blinding as a protection, and (c) doesn't have a special field multiplier. If you had to choose one curve for a given security level I think the "greatest-good-for-greatest-number" is on the side of special primes: the 2x speedup can be widely achieved, whereas the <2x slowdown will have more narrow impact. Perhaps advocates of random primes are worried that many different parties will demand their own curves? If all ECC is Weierstrass / random-prime / ECDSA etc, then everyone can randomize their parameters and get a different curve, and HW can support everything by just changing a few numbers? Trevor [1] http://www.ietf.org/mail-archive/web/cfrg/current/msg05198.html [2] http://eprint.iacr.org/2014/832.pdf [3] http://www.ietf.org/mail-archive/web/cfrg/current/msg05892.html _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
