Assessing the impact of quantum cryptanalysis
By Jaime Sevilla @ 2020-07-22T11:26 (+39)
[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.
irving @ 2020-07-23T08:37 (+13)
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.
Jsevillamol @ 2020-07-23T11:34 (+4)
Thank you so much for your kind words and juicy feedback!
Google has already deployed post-quantum schemes as a test
I did not know about this, and this actually updates me on how much overhead will be needed for post quantum crypto (the NIST expert I interviewed gave me an impression that it was large and essentially would need specialized hardware to meet performance expectations, but this seems to speak to the contrary (?))
here may be significant economic costs due to public key schemes deployed "at rest"
To make sure I understand your point, let me try to paraphase. You are pointing out that:
1) past communications that are recorded will be rendered insecure by quantum computing
2) there are some transition costs associated with post quantum crypto - which are related to for example the cost of rebuilding PGP certificate networks.
If so, I agree that this is a relevant consideration but does not change the bottom line.
Thank you again for reading my paper!
irving @ 2020-07-23T13:15 (+4)
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.
David_Kristoffersson @ 2020-07-22T14:57 (+5)
Metaculus: Will quantum computing "supremacy” be achieved by 2025? [prediction closed on Jun 1, 2018.]
While I find it plausible that it will happen, I'm not personally convinced that quantum computers will be practically very useful due the difficulties in scaling them up.
Jsevillamol @ 2020-07-22T15:05 (+13)
Note that we believe that quantum supremacy has already been achieved.
As in, the quantum computer Sycamore from Google is capable of solving a (toy) problem that we currently believe unfeasible in a classical computer.
Of course, there is a more interesting question of when will we be able to solve practical problems using quantum computing. Experts believe that the median for a practical attack on modern crypto is ~2035.
I regardless believe that outside (and arguably within) quantum cryptanalysis the applications will be fairly limited.
The paper in my post goes in more detail about this.
PabloAMC @ 2020-07-24T09:12 (+6)
I regardless believe that outside (and arguably within) quantum cryptanalysis the applications will be fairly limited.
I might be confused, but did we agree that the most useful application of quantum computing would be on chemistry and material science? I thought so, but the above sentence seems to say otherwise...
Jsevillamol @ 2020-07-24T10:37 (+7)
I think we broadly agree.
I believe that chemistry and material science are two applications where quantum computing might be a useful tool, since simulating very simple physical systems is something where a quantum computer excels at but arguably significantly slower to do in a classical computer.
On the other hand, people more versed on material science and chemistry I talked to seemed to believe that (1) classical approximations will be good enough to approach problems in these areas and (2) in silico design is not a huge bottleneck anyway.
So I am open to a quantum computing revolution in chemistry and material science, but moderately skeptical.
Summarizing my current beliefs about how important quantum computing will be for future applications:
- Cryptoanalysis => very important for solving a handful of problems relevant for modern security, with no plausible alternative
- Chemistry and material science => Plausibly useful, not revolutionary.
- AI and optimization => unlikely to be useful, huge constraints to overcome
- Biology and medicine => not useful, systems too complex to model
Linch @ 2020-07-23T09:05 (+4)
Yeah one strong reason to believe in your own judgement over that of prediction markets/prediction engine medians is if you think you have additional important additional information that the community was not able to update on. In this case, the question was closed in mid-2018 and the paper came out in 2019.
David_Kristoffersson @ 2020-07-23T09:51 (+1)
Thanks Linch; I actually missed that the prediction had closed!
Linch @ 2020-07-23T10:49 (+3)
Yeah the Metaculus UI is not the most intuitive, I should flag this at some point.