Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

Is breaking AES NP-hard? Can the security of AES be reduced to a NP-complete problem?

If it is reducible, what does the reduction look like? If it is not reducible, why do we assume it is secure?

share|improve this question
5  
We know no such reductions for any cryptosystem we use in practice. Not AES, nor RSA. Such reduction isn't too useful in the first place, since complexity classes talk about asymptotic cost, whereas we want to know if a certain concrete key-size is secure. – CodesInChaos Feb 10 at 19:34
How does it "seems clear"? It is clear that some problems relating to some attacks lie in NP (assuming some kind of generalization which allows growing key sizes, simply guessing the right key and then verifying them solves it – the same goes for secret-key crypto), I don't see how you get that they are NP-hard. – Paŭlo Ebermann♦ Feb 10 at 20:20
2  
"Being broken when $P = NP$" doesn't mean "being unbroken when $P \neq NP$". RSA is broken when factoring is easy, but neither is factoring known to be NP-complete nor is it known that RSA can only be broken by factoring the modulus (this is just the best known way nowadays). It is similar for most other public-key algorithms. (And even less for symmetric "bit-shuffling" crypto.) – Paŭlo Ebermann♦ Feb 10 at 22:18
3  
Actually, it's not at all true that someone showing $P=NP$ implies that all cryptography is broken. For one, an existence proof (that is, a proof that $P=NP$ that does not give an explicit reduction) doesn't affect the practical security at all. In addition, an explicit reduction of an NP-hard problem of size $n$ that takes either $2^{1000} n$ or $n^{1000}$ operations would suffice to show $P=NP$, but would be of no practical concern. To be of concern, we would have to show that large NP-hard problems can be practically solved. – poncho Feb 11 at 18:06
1  
@CodesInChaos why not make that first remark an answer? – owlstead Feb 12 at 0:44
show 4 more comments

1 Answer

up vote 2 down vote

There are some complexity-theoretic reasons to believe that cryptography can't be based on NP-completeness. For one example, see this paper by Akavia et al. Basically it all boils down to the mismatch between average-case hardness required for cryptography, and worst-case hardness required for NP-hardness. Moreover, many (most? all?) hard algebraic problems which serve as the basis for cryptography are in NP $\cap$ co-NP (for one such example, consider factoring). Such problems cannot be NP-complete unless NP = co-NP. You can see more discussion in this stackoverflow thread.

Finally, AES is a finite-domain function. It is invertible / distinguishable from a random permutation in (large but) constant time. The definitions of P, NP, etc., refer to asymptotic behavior -- that is, as the input size grows to infinity. Because of the algebraic structure of AES, it is probably possible to define a "generalized AES" for infinitely many key lengths (though there are many semi-arbitrary choices to be made). We could then ask about the asymptotic behavior of such a generalized AES. I'm not sure if anyone has done so.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.