Enzo Michelangeli wrote:
> Sure, I did not intend to belittle the theoretic significance of those
> papers, which are surely very interesting. I just meant that:
>
> 1. Converting a generic codebreaking problem into an NP-complete one with a
> transformation of polynomial complexity, while probably possible, is not
> trivial at all. For example, the factoring problem MIGHT be NP-complete, as
> the best known algorithms are of exponential complexity, and the
> verification is polynomial: but, so far, nobody has either disproved the
> hypothesis, or proved it by transforming it into an NP-complete problem. And
> we can't say that nobody tried! The transformation NP->NP-Complete may well
> run in polynomial time, but FINDING it in the general case is probably
> intractable, and finding it in particular cases is very difficult
> (especially with complicated encryption algorithms involving arbitrary
> s-boxes and such).
Any block cipher I can think of can be straightforwardly represented as
equations in Boolean vectors:
c = e(k,p)
p = d(k,c)
Where plaintext, ciphertext, key, encryption and decryption are each
represented by their 1st letter. These will of course be messy eqn's,
quite hard to solve for any reasonably good cipher. In principle, though,
they can certainly be solved for k if we have enough known c,p pairs.
This reduces breaking the cipher to a SAT instance whose size is a function
of three things: key size, block size, and the number of blocks described
as "enough" above. If those three are related in any straightforward way,
this reduces to a SAT instance with a single size parameter.
If this is the best possible attack on the cipher, then the problem of
attacking it requires exponential time on a deterministic computer.
Or, if brute force search through the keyspace is the best attack, that
is exponential in keylength.
Verifying a solution involves performing a few encryptions or decryptions.
This appears polynomial for any reasonable cipher.
So, if either of those attacks is the best available, the cipher is
equivalent to SAT, hence NP-complete.
