[curves] whitenning optional curve25519 keys

[Michael Hamburg]

You can do this with Elligator, but to actually be indistinguishable you have to run it twice, add the results, and then convert to affine.  This takes 3 inverses or square roots (maybe 2 if you’re really aggressive with the isqrt trick), which means that it’s not much faster than computing xG with a comb algorithm.  On the plus side, it is entirely safe to use this as the basepoint for future DH operations, and those operations are essentially independent of each other and of xG.  That’s what the SPEKE password-authenticated key exchange does.

— Mike

> On Sep 14, 2015, at 8:52 PM, Watson Ladd <watsonbladd at gmail.com> wrote:
> 
> 
> On Sep 14, 2015 2:31 PM, "Jeff Burdges" <burdges at gnunet.org <mailto:burdges at gnunet.org>> wrote:
> >
> >
> > I noticed a minor traffic whitenning issue in the HORNET paper :  HORNET
> > uses Sphinx packets to build circuits through the mixnet, but the actual
> > HORNET packets that travel on those circuits use a different header.
> >
> > This begs the question : How should I quickly generate a random curve
> > 25519 group element such that an observer cannot tell that I'm not
> > actually doing a scalar multiplication?
> >
> > We want a hash function f that yields a curve25519 group element such
> > that :
> > (a) if X,Y have uniform distributions, then the resulting distribution
> > f(X) is (sufficiently?) indistinguishable from g(Y) * G where g is some
> > reasonable hash function that yield curve25519 scalars and G is a base
> > point.
> > (b) f(x) can be computed an order of magnitude faster than g(x) * G.  I
> > hear a curve25519 DH operation takes about 40x longer than a typical
> > sha512 based KDF.
> 
> What about Elligator encoding everything?
> >
> > Also, is it possible to do this is such a way that f(x) is a safe
> > basepoint for future DH operations?
> >
> > Jeff
> >
> >
> >
> > _______________________________________________
> > Curves mailing list
> > Curves at moderncrypto.org <mailto:Curves at moderncrypto.org>
> > https://moderncrypto.org/mailman/listinfo/curves <https://moderncrypto.org/mailman/listinfo/curves>
> >
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150915/19d1d8b7/attachment.html>