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$ Commented 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$ Commented Jul 14, 2014 at 8:50

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.