Suppose $\mathrm{P}=\mathrm{NP}$ were proven and a practical low-degree (2 or 3) polynomial algorithm was found before widespread quantum key distribution was available. How would internet security work? Presumably, there would be eventually fewer bugs because of formal verification, but everyone would need to use one-time pads. Major platforms could mail USBs or hard drives with keys to everyone and people could be taught to use one-time pads to talk securely with friends and family or could an alternative system work?

Would the internet would be down for several months while major security bugs were found and fixed and the one-time pad distribution system was set up? Wouldn't internet security would be a hassle for years afterward?

Edit: I am specifically asking about practical policy implications. If we knew that all the major cryptographic primitives would be unsalvageably tomorrow (other than one-time pads), what would we need to do to get the internet working and what would be the future limitations we would have to live with.

  • $\begingroup$ Your hassles might be mitigated when QKDNs appear with star topologies. $\endgroup$
    – Paul Uszak
    Commented Mar 4, 2021 at 0:32
  • $\begingroup$ As an additional reason to close this question, it's more opinion-based than the one that motivates closing as duplicate. In particular, that proof of $\mathrm{P}=\mathrm{NP}$ (which itself would come as a huge surprise) would imply that "the one-time pad distribution system (would be) set up" is speculative opinion. $\endgroup$
    – fgrieu
    Commented Mar 4, 2021 at 9:22


Browse other questions tagged or ask your own question.