I expected to find answers along the lines of quantum-computing insight into attacking AES; however, answers on this question aren't applicable because "Quantum computers give a quadratic speedup on a (sic) general search problems".
Let us suppose the very worst case: P=NP by constructive proof. Therefore, 3-SAT and direct polynomial attacks on AES and all other standard-model symmetric ciphers.
How do we construct something that takes a serious attack to break besides using ECB and sending one block per key? Do quantum-proof symmetric ciphers with properties other than those of the one-time pad actually exist?
I think I can prove that if you use any kind of MAC other than polynomial evaluation MAC (or something else with its characteristic deniability) your cipher must fail.
I can prove that ciphered random data is possible because you can't break ECB over random data, but that proof is useless.
I am aware of the implausibility of ending up in this world of P=NP. I am also aware of this old post describing very good reasons why P=?NP is a poor model for breakability. I am interested in this problem because I am reasonably certain that any solution must use an encryption method that is, of itself, deniable.
The one-time pad has this property; however, I'd rather have an answer that offers something less unwieldy, if possible.