<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 20, 2017, at 3:17 PM, Fan Jiang <<a href="mailto:fan.torchz@gmail.com" class="">fan.torchz@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="auto" class="">Hi Mike,<div dir="auto" class="">Thanks alot for the suggestion.</div><div dir="auto" class=""><br class=""></div><div dir="auto" class=""><span style="font-family:sans-serif;font-size:16.512px" class="">that should be true for any output of Point::from_hash</span><br class=""></div><div dir="auto" class="">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.</div></div></div></blockquote><div><br class=""></div><div>Hi Fan,</div><div><br class=""></div><div>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.</div><div><br class=""></div><div>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.</div><div><br class=""></div><div>— Mike</div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><div class="gmail_quote">2017年1月20日 17:42，"Mike Hamburg" <<a href="mailto:mike@shiftleft.org" target="_blank" class="">mike@shiftleft.org</a>>写道：<br type="attribution" class=""><blockquote class="m_5231372927889131948quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Fan,<br class="">
<br class="">
Decaf’s cofactor is 1, so all non-identity points are generators.<br class="">
<br class="">
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.<br class="">
<br class="">
Overall, the computation would then be elligator(hash(base_point, seed)). In C++, that’s something like:<br class="">
<br class="">
std::string seed = [a fixed 512-bit constant which you chose at random];<br class="">
Point::from_hash(SHAKE<256>::H<wbr class="">ash(std::string(Point::base()) + seed, Point::HASH_BYTES*2))<br class="">
<br class="">
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.<br class="">
<br class="">
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.<br class="">
<br class="">
Cheers,<br class="">
— Mike<br class="">
<div class="m_5231372927889131948elided-text"><br class="">
> On Jan 20, 2017, at 1:01 PM, Fan Jiang <<a href="mailto:fan.torchz@gmail.com" target="_blank" class="">fan.torchz@gmail.com</a>> wrote:<br class="">
><br class="">
> Hi,<br class="">
> I'm currently working on a CramerShoup implementation using decaf_448,<br class="">
> Whereas decaf is to eliminate the cofactor by compression,<br class="">
> Should I still use the equation "orderQ*cofactor*P == identity" to check the candidate generator P?<br class="">
> Or, What should be a "valid" generator mean in this use case?<br class="">
><br class="">
> Thanks,<br class="">
> Fan<br class="">
><br class="">
</div>> ______________________________<wbr class="">_________________<br class="">
> Curves mailing list<br class="">
> <a href="mailto:Curves@moderncrypto.org" target="_blank" class="">Curves@moderncrypto.org</a><br class="">
> <a href="https://moderncrypto.org/mailman/listinfo/curves" rel="noreferrer" target="_blank" class="">https://moderncrypto.org/mailm<wbr class="">an/listinfo/curves</a><br class="">
<br class="">
</blockquote></div><br class=""></div>
</div></blockquote></div><br class=""></body></html>