4
$\begingroup$

In the answer to the question “What exactly is a negligible (and non-negligible) function?”

There is a part in the explanation that – as far as my knowledge goes – is conflicting:

But instead of brute force, the adversary can guess (a polynomial number of) random values and hope to chance upon the right one.

From what I understand, a “brute force attack” attempts to guess (to exhaustion)… or am I missing something here? Can someone please explain the distinction in this context?

Improve this question
$\endgroup$
1
  • $\begingroup$ I'm thinking that it has to do with being polynomially bounded which means many keys are not valid in the first place. Of course, an adversary is not going to choose invalid keys. So you need some other method to define security - the notion of a brute force attack doesn't hold anymore. Think of brute force as infinitely dumb, just iterating through every possible (bit) value. Even a dictionary attack is not brute force. $\endgroup$
    – Maarten Bodewes ♦
    Jul 13, 2014 at 14:00

1 Answer 1

Reset to default
2
$\begingroup$

The difference in that answer is that brute force refers to an exhaustive guessing attack (having guaranteed success but requiring exponential time) whereas guessing (a polynomial number of) random values refers to exactly what it says (requiring polynomial time but having only a certain chance of success).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ok, so would it be correct to say that the part I missed was the assumption that the "brute force attack" in this explanation is above the bounds of polynomial complexity and considered exponential? $\endgroup$
    – Ben B
    Jul 14, 2014 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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