Antoine MissoutAntoine MissoutLa partie tendre du chat.
Regarding symmetric encryption: if you have no idea what the plaintext looks like, then any key you try could be valid. In general, you do have some idea about the plaintext file. Assume for a second you know the file is a JPEG encrypted using AES256, then it is trivial to validate more than 256 bits of the plaintext (plenty of markers in a valid JPEG), meaning the whole problem now has a singular solution. If my conjecture is correct, then it is possible to solve using a faster than brute-force algorithm.
In short, beware symmetric encryption where the private key is smaller than the number of bits you can validate on the plaintext. That's the whole point of yadacha.
An interesting tidbit about SHA256: all the intermediate values of the rounds (s1, ch, s0, etc) can be calculated from the round output, meaning the whole round can be reversed, except for w[i]. Only the key expansion matters, and that's a very well structured problem.
Let's take RSA numbers as an example. You have a known number, let's call it c, which is the product of two prime numbers, which we'll call a and b. The goal is to find a and b such that a * b = c. This is the usual statement of the problem.
However, looking closely, you'll notice that, as stated, there is 4 valid solutions. Let's take 21 as c, you have 1 * 21, 21 * 1, 3 * 7, and 7 * 3. If you include the fact that a and b are prime (which is non-trivial to encode into the problem statement), you can remove the first two solutions.
To ensure a single valid solution, you need to specify a < b. And instead of encoding that a and b are prime numbers into the statement (rather difficult), you can instead simply specify that a > 1 or b < c, which is much easier to implement.
To exploit the fact a given problem has a single solution, you must be very careful how you state it, otherwise the approach will fail: if you encode the problem statement into a graph of logical gates, random large subgraphs will behave differently if there's a single global solution or many.
Julia Robinson and Hilbert's Tenth Problem is a movie by George Paul Csicsery covering the MRDP theorem, which provides a negative answer to the stated problem.
A slightly different problem caught my interest, due to its applications. Instead of asking about whether any discrete problem has a solution (without providing it), what happens if we know in advance the problem has a single solution: can it be provided?
My conjecture is as follows: provided a discrete problem with a single valid solution, there exist an efficient algorithm to extract it.
It's the very fact that the problem has a single solution that makes it efficiently solvable. There is a great deal of interesting problems that can be formally stated under that condition.
Hint: Value computing codes, that is, the truth tables of logical gates that any discrete problem can be broken into, are just error correcting codes that are very bad at correcting errors. My thanks to Irit Dinur for the inspiration.