On 12/06/2013 03:12 PM, Niels Möller wrote:
I think the main point of the smaller group in DSA is to get small signatures.
And discrete logs in the large group and discrete logs in the small subgroup are of comparable difficulty, because there's more structure in the larger group ("index calculus" is the name of the trick, iirc).
cool, thanks, i'll look into that further.
For DH, I don't think there's any particular reason to prefer to work in a small subgroup. But I may be missing something, of course.
I can think of a few, but i'm not sure how legitimate they are:
one is a minimized-entropy: If you know your small subgroup is of size q, then you need less entropy to choose your secret A in the DH key exchange, since it never needs to exceed q.
Another might be efficiency of modular exponentiation: if you use exponentiation by squaring, then the cost of generating the public DH value A' from A where 1 < A < q should be O(log_2(q)) instead of O(log_2(p)) where 1 < A < p. The cost of the second exponentiation (from B') will still be O(log_2(p)), of course, but it still seems like a non-trivial reduction in computation.
I've heard complaints about both the additional round-trip of the DH
--dkg