3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Other duplicates: crypto.stackexchange.com/q/8891, security.stackexchange.com/q/12802 $\endgroup$
    – Squeamish Ossifrage
    May 20, 2019 at 4:03
  • $\begingroup$ @SqueamishOssifrage: That paper probably contains the answer to my question. Too bad I can't read it because ADA bugs are making PDF useless to me right now. Unfortunately your answer without the paper you site doesn't of itself answer my question. :( $\endgroup$
    – Joshua
    May 20, 2019 at 4:03
  • 3
    $\begingroup$ The main point is that the mere proposition that P = NP has no consequences for cryptography, absent an extremely efficient concrete reduction, because we already choose cryptosystems so that the concrete costs of attacks for fixed parameter sizes are beyond human capacity—not so that the asymptotic growth curves of cryptosystem ensembles belong to some theoretical complexity class. The paper isn't about P = NP in particular; it's just about how to choose RSA parameters to attain certain concrete costs that are beyond even a hypothetical quantum adversary. $\endgroup$
    – Squeamish Ossifrage
    May 20, 2019 at 4:06
  • 1
    $\begingroup$ @SqueamishOssifrage P = NP has no consequence for cryptography under your definition of "cryptography". $\endgroup$
    – fkraiem
    May 20, 2019 at 7:19
  • $\begingroup$ @fkraiem I'm talking about practical cryptography, not about the theoretical cryptography whose sole reason for existence is as a proxy for practical cryptography. A deeper understanding of complexity classes, while interesting, does not imply that the AT cost of a cryptanalytic attack on AES-256 will drop below $2^{128}$. Maybe a proof of P = NP would come with an extremely efficient concrete reduction, or maybe it would come with an $\Omega(n^{10000})$ price tag; we're speculating on speculation at this point, and my point is that concrete costs, not complexity classes, are what matter. $\endgroup$
    – Squeamish Ossifrage
    May 20, 2019 at 14:02

2 Answers 2

Reset to default
6
$\begingroup$

An important thing to note is that $\mathsf{P} = \mathsf{NP}$ would not fundamentally threaten cryptography - even theoretical cryptography. What it would imply, as mentioned by Meir Maor in his answer, is that there is no one-way function, which means essentially no "traditional" cryptography.

However, one-way functions, and most of cryptography, are theoretically defined as requiring a superpolynomial gap between the best attack and the honest use of the algorithms. Still, if tomorrow you prove $\mathsf{P} = \mathsf{NP}$, there can still exist functions which take time $n$ to compute, but time $n^{10}$ to invert. This would not at all contradict $\mathsf{P} = \mathsf{NP}$. It would however suffice for all practical purposes: take $N = 2^{10}$, then evaluating your function takes $2^{10}$ steps, while inverting it takes $2^{100}$ steps. That security margin is good enough for most uses.

Such one-way functions, where the gap between evaluation and inversion is a fixed polynomial instead of superpolynomial, are called fine-grained one-way functions. They are an emerging subject of study in cryptography (see e.g. this recent paper), mainly because they can in theory be built from weaker assumptions than those known to imply standard OWF (even though exhibiting such a fine-grained OWF from a generic, well-studied assumption which is not believed to imply OWF remains, as of today, an open problem). They can be used to construct fine-grained pseudorandom generators and stream ciphers.

It does not seem absurd that, in the event that we prove $\mathsf{P} = \mathsf{NP}$, our best attack on AES would still require $n^{10}$ steps. In this case, after some appropriate key-size adjustments, everyone would just keep on using the good old AES, as if nothing had ever happened, and theoretical cryptographers would replace "assume this OWF takes $\mathsf{superpoly}(n)$ steps to break" by "assume this OWF takes $n^{10}$ steps to break".

Improve this answer
$\endgroup$
4
$\begingroup$

If P=NP there are no one way functions, there are no trap door one way functions and essentially no cryptography.

If P=NP it means verifying a key and finding the key are equally hard(Up to a polynomial reduction). So one time pads still work, they are information theoretically secure and don't rely on computational difficulty. But all encryption, symmetric or not, hashing etc becomes insecure.

Practically, quantum key exchange may save us, it will allow a non cryptographic secure channel for sharing key material and then allow one time pad.

It is worth noting that it is possible we live in cryptography distopia even if P does not equal NP. We do not know the existence of one way functions, they may not exist, even if P!=NP

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ AFAIK, your claim the P=NP implies "essentially no cryptography" is only true if the polynomial-time reduction from NP to P is efficient enough to be practically usable. If the best possible reduction had a very high exponent (say, $O(n^{1000})$) and/or an astronomical constant factor (say, it requires brute force testing $2^{256}$ possible choices), then it might practically speaking just as well not exist. (Of course, finding such a reduction might still be a cause for concern, just because "attacks never get worse." But in principle, practical cryptography may be possible even if P=NP.) $\endgroup$
    – Ilmari Karonen
    May 20, 2019 at 8:47
  • 1
    $\begingroup$ Normally we want the legitimate user to have an exponential advantage. There is a small amount of research with only polynomial advantage for instance multi prime RSA tries to be post quantom secure with only polynomial advantage. Considering exponential speedup of computing, relying on a polynomial advantage seema ill advised. $\endgroup$
    – Meir Maor
    May 20, 2019 at 9:03
  • $\begingroup$ @MeirMaor Quantum key distribution and the one-time pad is not necessarily a sound combination. If one could find out half of the key deduced from the QKD, then one can find out the rest of the key if it is used with one-time pad :( $\endgroup$
    – Marc Ilunga
    May 20, 2019 at 10:22
  • 1
    $\begingroup$ @MarcIlunga Are you sure of this? Given that the key is truly random, and the message unknown, it seems tricky to obtain the missing half of the key. And isn't the entire premise of QKN that the key can't be unknowingly obtained, ie. can't be obtained period if the system is correctly implemented. $\endgroup$
    – Paul Uszak
    May 20, 2019 at 12:08
  • 1
    $\begingroup$ @PaulUszak, That was a result from Renner and Maurer plus following papers. The assumption is that one half of the key is known. Although the result is of a purely theoretical interest, the assumption is not too strong. We can assume that the message being OTPd can be to some extent manipulated by the attacker or has a know "header". Assuming that, the problem is not really on whether the QKD or OTP is done correctly, it's more about the composition that doesn't hold in every context(here the one where half of the key can be found). I would say this is a bit like Encrypt-then-Mac issue. $\endgroup$
    – Marc Ilunga
    May 20, 2019 at 13:09

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