Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In many articles and papers I find the phrase

...discrete logarithm problem in many groups of cryptographic interest...

commonly used. I would like what groups are they exactly referring to when they mention "groups of cryptographic interest" when it comes to the discrete logarithm problem.

Thanks!

share|improve this question
9  
The groups that are normally used in actual applications of cryptography that relate to the discrete log problem: groups of points of elliptic curves, multiplicative groups of finite fields (and particularly of finite fields of characteristic 2), etc. The point is that there are many groups which are never used in cryptography (e.g., additive group of integers modulo $n$), for which solutions to the discrete log problem are irrelevant for cryptography (usually because they are trivial there, or because the group is too hard to implement effectively). –  Arturo Magidin Feb 28 '11 at 4:42
2  
@Arturo: that would make a fine answer, I think. It might be worth mentioning that "cryptographic interest" is not invariant under isomorphism. –  Qiaochu Yuan Feb 28 '11 at 13:02

1 Answer 1

up vote 4 down vote accepted

Not all cyclic groups are created equal; some groups are used (currently) for cryptographic applications, while others are not.

"Groups of cryptographic interest" refers to groups that are normally used in actual applications of cryptography that relate to the discrete log problem; these are Diffie-Hellman key exchange, ElGamal, and the like.

Usually, the groups that are used for these problems are the multiplicative group of integers modulo a very large prime $p$; the multiplicative group of a finite field (particularly of finite fields of characteristic $2$, because they tend to be easy to implement); or points of curves of elliptic curves (over finite or global fields).

Some groups have very easy discrete logarithm problem (the additive group of integers modulo $n$, for example) so they are not used in actual applications of cryptography; other groups are too hard to implement, so they are not used either. The discrete logarithm problem for these groups is irrelevant for cryptography, since they are not used for cryptography. So these groups are not of "cryptographic interest".

Note that being of "cryptographic interest" is both time-dependent (it depends on what is being used now), and more importantly as noted by Qioachu, it is not invariant under isomorphism. The multiplicative group of a finite field of order $p^k$ is (abstractly) isomorphic to the additive group of integers modulo $n=p^k-1$; but while the discrete logarithm problem for the former is considered "hard", the discrete logarithm problem for the latter is "easy". The problem here is that finding an isomorphism is essentially equivalent to constructing a full logarithm table for the multiplicative group of the finite field, so having an isomorphism is pretty much the same as solving the discrete logarithm problem.

share|improve this answer
    
The last paragraph on "isomorphism" is vital information! Interesting.. –  bala maverick Mar 1 '11 at 4:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.