6 Aug
2003
6 Aug
'03
8:49 p.m.
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.