[Cfrg] Standard rant on bit security (related to the pairings draft)

[Watson Ladd <[e-mail]>]

Dear all,

If you have already heard this rant, skip reading the email.

Claims made that an algorithm A provides B bits of security are claims
that ignore substantial real differences in the complexity of attacks.
Pairing based curves present an excellent example of this. Suppose one
wants to break AES-128, that is recover k from E_k(0). The obvious
algorithm is to treat this as a search for a preimage: One grinds
away, and multiple targets can be found quite simply. Each guess is
simply a guess and the success probability is linear.

Now let's break P256. Here the algorithm is the distinguished point
algorithm, which does a random walk that varies by target. The
complexity of attacking multiple keys is not amortized in the same
way. The success probability is also quadratic in the runtime, vs.
linear.

For NFS the amortization is even stronger. The NFS algorithm works by
computing relations among the discrete logarithms of a factor base.
This work does not need to be repeated per target, while the work of
relating the unknown element to a factor base does depend on the
target, but an attacker can enlarge the factor base to reduce it. At
the same time NFS has a communication intensive linear algebra step,
and for discrete logarithms this step is more expensive then for
factoring. This cannot be equated to either of the ones above.

The complexity of the NFS also depends on estimates of the smoothness
probability. In this setting it is the finite field, so I think
smoothness probability is easily estimated (Riemann hypothesis is
known) but for some fields the constants are only know heuristically
with errors after the first few digits.

Simple descriptions of the time complexity as bit lengths ignore the
impact of communication and multitarget effects, and completely
ignores success probability. It omits often constant factors that can
have significant implications for actual security and the heuristics
that need to go into the runtime of many algorithms in number theory.
It sacrifices big differences in multiuser security on the alter of
simplicity.

Lastly P384 is a dog: a different prime shape might have lead to more
usage. I don't think one can draw broader conclusions from it's lack
of usage.

Sincerely,
Watson Ladd