Re: non-NP-completeness of block ciphers?

Paul Rubin wrote:
Mahaney 1982 proved that if P != NP then there are no sparse
NP-complete sets. Sparse means that the number of strings of length n
is bounded by n**k for some k: [..]

I see the confusion. Remember that a language is a subset of
{0,1}^*. A NP-complete problem is a language that is NP-complete.
(The language is the set of Yes-instances to the NP-complete decision
problem.) Mahaney's theorem presumably proves that if a decision
problem is NP-complete, then its corresponding language is sparse.

For instance, the language corresponding to the 3SAT problem is
the set of 3SAT formulas that are satisfiable. Note that by encoding
a 3SAT formula in binary in some standard way, we can consider it as
an element of {0,1}^*, and so a set of 3SAT formulas can be considered
a subset of {0,1}^*.

In the rest of your post, you fail to identify a NP-complete decision
problem whose corresponding language is sparse. One must be careful about
how you go from decision problem to language. I think you made a simple
mistake. You did not identify a decision problem: you identified some
other problem. Likewise, you did not identify a NP-complete language;
you chose some set (the set of keys K such that blah blah blah) but
that set was not a NP-complete language (indeed, for any fixed value of
(P1,C1),..,(Pn,Cn), that set is a language in P). While it may be true
that the set of keys K that are consistent with (P1,C1),..,(Pn,Cn) is
"sparse", this does not contradict Mahaney's theorem.
.

Relevant Pages