If by brute force you mean checking the entire key space, fuzzing can be made to sound quite similar to encryption.
There is a specific program path, or "key", that leads to a crash. Fuzzers attempt to search all paths in a somewhat intelligent manner to find the "key" path that leads to a crash.
We can inhibit the fuzzers ability to find the key by increasing the search space by adding more paths. The way in which this paper adds paths takes advantages of the way intelligent fuzzers explore the path space to make it even more difficult to search the entire path space.
The problem is that there isn't a single key in this case, there are many. If there was just a single key to begin with, fuzzing would not be very fruitful for any moderately+ complex program since finding that single path would already be very hard (and therefore has a high cost/benefit).
What fuzzification actually enables is to hide more keys (crashes) from a constant amount of (current) effort. Those crashes are still there and now there are more of them, waiting for someone to find them with an alternative method or simply by buying more fuzzing equipment to scale horizontally.
There is a specific program path, or "key", that leads to a crash. Fuzzers attempt to search all paths in a somewhat intelligent manner to find the "key" path that leads to a crash.
We can inhibit the fuzzers ability to find the key by increasing the search space by adding more paths. The way in which this paper adds paths takes advantages of the way intelligent fuzzers explore the path space to make it even more difficult to search the entire path space.