At 03:50 PM 08/06/2003 -0700, Major Variola (ret) wrote:
Yes, but the cryptanalysis of symmetric ciphers involves
exponentially-expanding "back trees".
That is the whole point of "avalanche". If, somehow, "for any NP
algorithm there were an equivalent P algorithm",
then the block-cipher backtracking would be solvable in poly time.
You could find the plaintext ASCII needle in the haystack
of possibilities in poly time, no?
No. NP is the set of problems which can be solved in
poly time on a non-deterministic Turing machine,
i.e. which can be solved in poly time if the
magic oracle correctly tells them a poly number of answer bits.
Not all exponential problems fit this model.
