Discussion:
How to find another generator on decaf_448？
Fan Jiang
2017-01-20 21:01:56 UTC
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
Mike Hamburg
2017-01-20 22:42:55 UTC
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
Post by Fan Jiang
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
https://moderncrypto.org/mailman/listinfo/curves
Fan Jiang
2017-01-20 23:17:35 UTC
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" <***@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
Post by Fan Jiang
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?
Post by Fan Jiang
Or, What should be a "valid" generator mean in this use case?
Thanks,
Fan
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Mike Hamburg
2017-01-21 02:05:17 UTC
Post by Fan Jiang
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
Post by Fan Jiang
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.
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
Post by Fan Jiang
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
https://moderncrypto.org/mailman/listinfo/curves <https://moderncrypto.org/mailman/listinfo/curves>