[curves] How to find another generator on decaf_448?

Fan Jiang fan.torchz at gmail.com
Fri Jan 20 15:17:35 PST 2017


Hi Mike,
Thanks alot for the suggestion.

that should be true for any output of Point::from_hash
This sentence sounds really impressive to me, does it mean a decaf point
decoded with elligator from a hash string is always valid to be a generator
without any exception? I will read elligator paper asap, but please correct
me if I'm saying something stupid here.

2017年1月20日 17:42,"Mike Hamburg" <mike at shiftleft.org>写道:

Hi Fan,

Decaf’s cofactor is 1, so all non-identity points are generators.

For Cramer-Shoup you will need a random point, such that it’s hard to
figure out its discrete log (base g).  You will need to be able to argue
that the point was really generated in a way that would make it hard to
embed a back door.  A straightforward way to get this property is by
hashing a random seed, and then applying Elligator.  Since Cramer-Shoup is
specified as using a *uniformly* random point (even though it’s probably
secure with something slightly less than uniform), you should use
point_from_hash_uniform.  Since Cramer-Shoup is designed to be secure in
the standard model, you should include a uniformly random seed, perhaps 512
bits long.  To prevent a theoretical backdoor mentioned by Stanislav
Smyshlaev, you should hash the base point as well.

Overall, the computation would then be elligator(hash(base_point, seed)).
In C++, that’s something like:

std::string seed = [a fixed 512-bit constant which you chose at random];
Point::from_hash(SHAKE<256>::Hash(std::string(Point::base()) + seed,
Point::HASH_BYTES*2))

If you’re using two random generators instead of random + base point, then
hashing in Point::base() above isn’t necessary, but the hash itself is
still required.

You might as well check that the resulting point isn’t the identity.  You
can check that orderQ * P == identity if you like, but that should be true
for any output of Point::from_hash.

Cheers,
— Mike

> On Jan 20, 2017, at 1:01 PM, Fan Jiang <fan.torchz at gmail.com> wrote:
>
> Hi,
> I'm currently working on a CramerShoup implementation using decaf_448,
> Whereas decaf is to eliminate the cofactor by compression,
> Should I still use the equation "orderQ*cofactor*P == identity" to check
the candidate generator P?
> Or, What should be a "valid" generator mean in this use case?
>
> Thanks,
> Fan
>
> _______________________________________________
> 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/20170120/175ae98e/attachment.html>


More information about the Curves mailing list