[curves] General Curve25519 and Ed25519 Libraries

[Michael Hamburg]

> On Jun 17, 2015, at 3:56 PM, Gregory Maxwell <gmaxwell at gmail.com> wrote:

> Internally it has the same feature set listed above minus constant
> time hash uniformly (methods to do so are known, but I haven't
> bothered implementing it due to a lack of a need) and a efficient steg
> bijection (which I don't know how to do for that curve; though I
> haven't looked into it much).

The steg encoding and hashing can be done with Elligator Squared by Tibouchi:

https://eprint.iacr.org/2014/043.pdf <https://eprint.iacr.org/2014/043.pdf>

This technique is implicit in the earlier work of Tibouchi with Brier, Coron, Icart, Madore and Randriam:

https://eprint.iacr.org/2009/340.pdf <https://eprint.iacr.org/2009/340.pdf>

It shouldn’t be terribly hard to implement for secp256k1, if you decide someday to have a go at it.

This is the technique I used in Decaf, except with Elligator 2 instead of the SWU encoding.  My actual implementation of steg is a bit of a hack though.  In particular, by setting STEG_BYTES = SER_BYTES + 8 it assumes without proof that a 64-bit offset makes a stegged point uniform enough, whereas the proof in BCIMRT only shows that for a full 448-bit offset.  Might be worth changing this at some point.

> It's also fast, which may be
> interesting for research use since it means that performance measures
> against it won't just be toy numbers, Someone showing up doing
> something interesting that needed these things (especially the former,
> since I know its possible) would probably inspire some work there. :)
> 
> On the other hand, the optimization for performance (and production
> use) do mean more complexity to implement protocols on it (as you'll
> have to deal with knowing when you want affine/projective coordinates,
> etc).  For safety reasons we also have no plans to expose basic
> cryptography operations externally (because we know from experience
> that callers will misuse them), only higher level constructed for
> "more complete" cryptosystems that are harder to abuse-- so new
> protocols can't just use the public API.

This is where Decaf, or perhaps Floodyberry’s Donna fork, would be easier.

Decaf is explicitly designed as a library for future protocol development, so its API exposes only safe, complete operations.  There are no affine or _var operations available, and all the operations should support the identity as well as every other point.  The implementation is in C, but every API call is also all wrapped in a C++ header with auto-erasing destructors.

However, Decaf is still very fast: on x86-64 it supports point operations and even signing in about the same time as secp256k1, and verifies in just over twice the time, with a 74% larger curve.

I won’t claim that it’s production-quality though.  Not yet…

> I also recently used this system to make a tech demo for a new zero
> knowledge range proof system, which I've been asked to post about, so
> I'll go do that now.

I’m off to read that next!

— Mike
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150617/f8df2f2b/attachment.html>