[curves] Prime order curves vs Decaf

[Henry de Valence]

On Thu, Jun 1, 2017 at 3:27 AM, Tony Arcieri <bascule at gmail.com> wrote:
> I also believe I've heard Decaf decompression of Ed25519
> points can actually be faster than the regular Edwards decompression.

I think I might have said the thing you're referring to; what I said
was that, after changing our (mine and Isis') prototype of a Decaf
encoding for Curve25519 to use Mike Hamburg's trick for doing the
computation with only one inverse square root, I measured the cost of
Decaf decompression as slightly less than the cost of
Edwards-Y-plus-sign decompression plus multiplication by 8 to "clear"
the cofactor [1].  This wasn't a scientific benchmark or anything,
just a `cargo bench` run inside a VM to get a ballpark estimate.

[1]: "clear" seems like a bad word here, because (at least to me) it
sounds like the 8-torsion component of the input point is removed
while the l-torsion component is unaffected. Maybe "mangle" might be a
better word?

> Seems like a complicated topic. Curious about people's thoughts.

Just my opinions:

Decaf for an existing cofactor-4 curve seems like a very elegant and
non-invasive solution.

Decaf for an existing cofactor-8 curve (in particular, Decaf for
Curve25519) seems like a somewhat messier solution that could be added
to existing Ed25519 implementations relatively easily.

I don't understand the benefit of specifying a new prime-order curve
versus specifying a cofactor-4 curve with Decaf.

Henry