[linkpost to Assessing the impact of quantum cryptanalysis]
I wrote this paper a few months back - it received a journal rejection because of lack of topic fit. I do not think this paper is important enough to spend more time chasing a publication, but others might benefit from it being public and I would still benefit from feedback for learning purposes; hence this post. Let me know in a comment or through a private message if you know of a publication venue which would be a better fit.
I reproduce the conclusion as a short summary of the paper. The rest of the paper is available here.
Conclusion
Quantum computing will render modern public key cryptography standards insecure. This risk is well-known, and as a result many reputable, well-connected and well-funded organizations are working on developing quantum secure standards for the future, eg the National Institute of Standards and Technology.
Several credible proposals for post-quantum classical cryptography already exist and are being actively researched. Another considered avenue is quantum cryptography, but as an alternative it has many shortcomings.
Should the efforts to develop post quantum public key cryptography fail, there are some theoretical arguments that indicate that we would be able to substitute its functionality by symmetric-key based standards and a network of private certificates. This alternative would incur in some efficiency overhead and security trade-offs.
Even if this more speculative approach does not work out, a more rudimentary system where people exchange keys physically would be, albeit inconvenient, potentially feasible to maintain some key applications such as secure online transactions.
All in all, given the existing attention and limited downside I would recommend against prioritizing research on mitigating the effects of quantum cryptanalysis as a focus area for public officials and philanthropists, beyond supporting the existing organizations working on post quantum cryptography and supporting existing cryptanalyst experts so they can conduce further security analysis of current post quantum cryptography candidates.
This is a great document! I agree with the conclusions, though there are a couple factors not mentioned which seem important:
On the positive side, Google has already deployed post-quantum schemes as a test, and I believe the test was successful (https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html). This was explicitly just a test and not intended as a standardization proposal, but it's good to see that it's practical to layer a post-quantum scheme on top of an existing scheme in a deployed system. I do think if we needed to do this quickly it would happen; the example of Google and Apple working together to get contact tracing working seems relevant.
On the negative side, there may be significant economic costs due to public key schemes deployed "at rest" which are impossible to change after the fact. This includes any encrypted communication that has been stored by an adversary across the time when we switch from pre-quantum to post-quantum, and also includes slow-to-build up applications like PGP webs of trust which are hard to quickly swap out. I don't think this changes the overall conclusions, since I'd expect the going-forwards cost to be larger, but it's worth mentioning.
Yep, that’s the right interpretation.
In terms of hardware, I don’t know how Chrome did it, but at least on fully capable hardware (mobile CPUs and above) you can often bitslice to make almost any circuit efficient if it has to be evaluated in parallel. So my prior is that quite general things don’t need new hardware if one is sufficiently motivated, and would want to see the detailed reasoning before believing you can’t do it with existing machines.