Subject: [Cfrg] Terms for comparing curves and other algorithms, on the basis of security and efficiency

From: Dan Brown <[email-masked]>
Date: Wed, 29 Oct 2014 15:24:54 +0000

Dear CFRG,

I've noticed some discussions on the CFRG list about security-efficiency
tradeoffs and so on.  It seems that every time the topic arises, somebody
has to explain the assumptions and so forth, all from first principles.  In
some cases, I even wonder if people are talking past each other, by
misunderstanding each other's explanations and positions.  In that regards,
perhaps a standardized terminology might help.

As part of a rather rushed research report http://eprint.iacr.org/2014/877,
Appendix B, I made an effort at this, but I'll summarize the ideas here in
an email.

First, we need to establish (non-trivial) and define some things:
- To establish absolute security and efficiency metrics, s and e (usable
across multiple algorithm types).
- To establish _defective_ security and efficiency levels, s_0, and e_0.
- To establish _saturated_ security and efficiency levels, s_1 and e_1
(beyond which no utility is gained).
- To define _tolerable_ security and efficiency levels, as those between
defective and saturated (assuming defective is strictly less than
saturated).
- To define _work ratio_ w = se
- To define _progressive ratio_ p = log(s)e

Next, consider two curve (or algorithm) choices with levels (s,e) and
(s',e') with it being non-trivial to determine these levels, 
- If s<s' and e<e', use the terminology that (s',e') _dominates_ (s,e), and
(s',e') is obviously better.  
- If both s and s' are saturated, that is, s,s'>s_1, then choose the higher
of e and e'.
- If both e and e' are saturated, that is, e,e'>e_1, then choose the higher
of s and s'.
- Otherwise, pick some ordering of e or s or w or p to maximize (i.e. a
lexicographic order).  I recommend maximizing work ratio w first, then
maximizing progressive ratio p, because using s or e first risks having
small gains in one metric for large loss in the other: whereas w and p try
to balance the s and e metrics.

Also, the systems above algorithm-agnostic, so can be used to compare block
ciphers, hash functions, not just elliptic curves.

I felt most of the above is more or less self-evident, albeit simplistic and
abstract, and is a paraphrasing of my understanding of most people's
arguments, but perhaps I am missing something (see below).

When I tried to apply the regimen above to elliptic curve selection, I had
two problems, which make me worry that the analysis is missing something
fundamental.  First, the conventional practice of offering multiple curves
sizes does not fit well into the system above: it defers too much of the
decision process to the user and seems to imply some kind of ambiguity about
the saturated security levels.   Second, optimizing work ratio w seems to
favor large cofactor, which seems very strange to me, and is certainly
unconventional (though I ignored public key size in the efficiency metric).
Maybe these strange discrepancies are not faults in the comparison system
above but merely discrepancies in my bounds for s_1 and e_0. For example,
perhaps my saturated security level is much higher than conventional, and my
defective efficiency is much lower than conventional.

Returning to the issues of debates about curves on the CFRG list, if two
people have different values of, say, s_1, but don't really know it, then
they are likely to disagree on the best curve or algorithm, and perhaps not
understand why.  Perhaps stating one's metrics, one's saturated and
defective levels, will help resolve some disagreements, or at least enable
better understanding of the disagreements.

Best regards,

Daniel Brown
Research In Motion Limited

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 29 Oct 2014 10:53:25 -0700

> to balance the s and e metrics.
I have a couple issues with this strategy overall.

The first is that we don't know when security saturates.  If attacks 
don't improve then Curve25519 might never fall.  Bigger curves are a 
hedge, but it's hard to determine how much of a hedge or what its value 
is.  Likewise e_0 and e_1 vary between users, devices and protocols.  
That's why multiple curves are used in practice.

As for work and progressive ratios, if you aren't careful your metric 
will simply force a curve on one of the bounds of the e_01, s_01 
rectangle, which would be OK except that we don't know e01 or s1.  For 
example, if e ~ field order^3, so that order  s ~ 2^(k/(cbrt(e))) for 
some constant k, then maximizing the work ratio will always lead to a 
curve which is as big as possible.  Likewise maximizing the progressive 
ratio will lead to a curve which is as small as possible.

Trevor and I have been ranking with an "efficiency ratio" of e (log 
s)^k, where the Karatsuba-2 power k = 1 + log_2(3) is roughly the 
trendline of the graph.  This metric has no intuitive meaning in terms 
of security trade-offs; it just captures the practical aspect of what it 
means for a curve implementation to be "efficient for its size".
> unconventional (though I ignored public key size in the efficiency metric).
I don't think this is true.  First of all, in some protocols you need to 
clear the cofactor, so having a huge cofactor doesn't improve efficiency 
at all.  But even if you don't need to clear it, a big cofactor 
generically only helps the user by log h / log n, and hurts security by 
a much larger sqrt(h) factor, so it doesn't improve work ratio.  It 
probably doesn't make a difference to progressive ratio, but a smaller 
field is usually going to have a better progressive ratio.
> Research In Motion Limited
I think you're partly correct about this.  Most people on this list seem 
to have implicitly set s0 ~ 2^128, s1 ~ 2^512, and are optimizing 
metrics which force curves to the edges.

But given the Snowden, NSA and NIST backdrop of this discussion, there's 
also a NUMS component in security.  And NUMS is a vague property which 
is hard to incorporate into a metric.  CFRGers can argue all year about 
whether the NUMS component is maximized by 2^(2*AES security level) - 
(smallest), or a curve over a Mersenne prime found by 3 groups, or VPR; 
and if a prime constrained by high performance even counts as NUMS.

-- Mike

---

From: Dan Brown <[email-masked]>
Date: Thu, 30 Oct 2014 21:12:06 +0000

> -----Original Message-----
> From: Mike Hamburg [mailto:[email-masked]]
> >   Second, optimizing work ratio w seems to
clear the
> cofactor, so having a huge cofactor doesn't improve efficiency at all.
But even
> if you don't need to clear it, a big cofactor generically only helps the
user by log
> h / log n, and hurts security by a much larger sqrt(h) factor, so it
doesn't
> improve work ratio.  It probably doesn't make a difference to progressive
> ratio, but a smaller field is usually going to have a better progressive
ratio.

You're right! Thank you for looking into this and finding my mistake, wow.
I'm relieved that I was just making a silly mistake (mixing up h and log h -
argh, how bad) in applying the system, so perhaps the overall system (of
saturation, defective, work and progressive ratios) is somewhat reasonable
after all, although perhaps too simplistic.