[curves] Second day NIST workshop notes

[Trevor Perrin]

On Sun, Jun 14, 2015 at 1:59 PM, D. J. Bernstein <djb at cr.yp.to> 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