[curves] How to find another generator on decaf_448？

[Mike Hamburg]

> On Jan 20, 2017, at 3:17 PM, Fan Jiang <fan.torchz at gmail.com> wrote:
> 
> 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.

Hi Fan,

This isn’t a special property of Elligator.  In a prime-order group, every element is a generator except for the identity.  In extremely rare cases, Elligator can output the identity, but the probability that this happens on a random input is negligible.

Also, in any group, multiplying a point by the group order gives the identity.  You may be thinking of checking if something is in a q-torsion subgroup, which you might check by multiplying by the subgroup order.

— Mike

> 2017年1月20日 17:42，"Mike Hamburg" <mike at shiftleft.org <mailto: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 <mailto: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 <mailto:Curves at moderncrypto.org>
> > https://moderncrypto.org/mailman/listinfo/curves <https://moderncrypto.org/mailman/listinfo/curves>
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170120/0baae35e/attachment.html>