Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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. – Maarten Bodewes Jul 13 '14 at 14:00
up vote 2 down vote accepted

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).

share|improve this answer
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? – Ben B Jul 14 '14 at 8:50

Your Answer


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.