Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This might be a quite stupid question: since a naive brute force algorithm to solve the discrete logarithm problem will only take O(n) time for a group G with order n, why is it assumed to be hard to solve? Doesn't hard mean no polynomial algorithm to solve in the context of cryptography?

share|improve this question
1  
$O(n)$ is polynomial in the order of the group, in general polynomial-time means polynomial in the number of digits thereof, i.e. $O(\log^k(n))$. This is because we can make $n$ rather large easily (a few hundred digits), but making $\log(n)$ large is "much harder". –  Thomas Jan 12 at 11:47
add comment

2 Answers 2

up vote 4 down vote accepted

While $O(n)$ is linear in the order of the group, what matters is actually the computational difference between the exponentiation and the discrete logarithm. The exponentiation is not in $O(n)$ but instead in $O(\log(n)) = O(|n|)$ (e.g. expoentiation with square and multiply has $|n|$ multiplications and at most $|n|$ squaring operations).

Therefore, the basic consideration for $n$ should not be the number of group elements, but its logarithm (which is linear to the length of the numbers. In order to avoid the question: This is valid for any numeral system, regardless of its base). So if we have numbers of a group $\mathbb{G}$, we should set $n=\log_2|\mathbb{G}|$, and brute force algorithms require $O(2^n)$ operations.

Short version with less algebra:

Encrypting or signing something uses exponentiation as operation, and there are algorithms with complexity linear to the length of the numbers (in binary representation), and let's call the length $n$. If you want to test all possible values (aka brute force), there are $\approx2^n$ values to test, and this is exponential in the parameter $n$.

share|improve this answer
    
Would it be possible to "dumb down" this answer a bit for those of us with interest in the topic, but without the mathematical/algorithmic context that seems to assumed in the current answer? –  Stephen Touset Jan 13 at 19:40
1  
done, I hope it is understandable –  tylo Jan 14 at 10:31
add comment

The polynomial vs. exponential complexity notations for algorithms or problems are always expressed in the input size, i.e. the size of a convenient way to express the problem.

For the discrete algorithm problem, you normally would not write the whole group (or even its multiplication table of size $n^2$) as the input, but only some key parameters which allow calculating the group law, as well as the element of which you want to get the logarithm.

Both can be usually expressed in $m = O(\log(n))$ bits for a group of size $n$.

For example, in the "classical" discrete logarithm problem you only need to express the modulus $n+1$ (which has $\log n$ digits), a basis (often one digit, at most $\log n$), and the element (also $\log n$ digits). The result will also be a number with $\log n$ bits.

In an elliptic curve DL problem, you'll note the base field (i.e. its size/modulus – around $\log n$ bits), and the curve equation (i.e. two or three field elements, at most around $\log n$, often smaller), and a base point (two field elements, around $2·\log n$ bits), together with the point of which you need the logarithm. Again, the result will be a number with $\log n$ bits.

And then polynomial means that the problem can be solved in $O(m^k) = O(\log(n)^k)$ time/space/other resources.


PS: Your naive brute force algorithm needs $O(n)$ multiplication (and comparison) steps, but each of them will need at least $O(\log(n))$ time (in average), so your algorithm needs $O(n·\log(n))$ time, not $O(n)$.

And in practical cryptography, you often don't want just some asymptotic high complexity, but want to calculate that it is practically hard, i.e. calculate some lower limits for the actually used parameters.

share|improve this answer
    
I think his algorithm actually needs $\:\: \large O\left(n\cdot \log(n) \cdot \log(\log(n)) \cdot 2^{O(\log^*(n))}\right) \normalsize \:\:$ time. $\hspace{.773 in}$ –  Ricky Demer Jan 14 at 0:20
add comment

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.