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
signature.asc
Description: OpenPGP digital signature
_______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
