[Cryptography] Quantum computers and the Government

[Jerry Leichter]

> What are the odds that governments already have quantum computers capable of breaking encryption (or will soon) and not tell anyone? RSA encryption, after all, was discovered and kept secret by the British government several years before it was "discovered" by the public; Especially with how weak certain common encryption schemes may be to quantum computers, it would be plausible that governments are rushing to develop and exploit this technology before the public has access to it.
Those who know can't say; those who say, don't know.

However, it seems unlikely.  Some of the largest companies in the world are pouring huge amounts of money into research on quantum computation.  There are hundreds of publications in the open literature.  This is a highly active, well-funded area of open research, with participants all over the world.  That's very different from the 1970's, when cryptography wasn't really seen as of much academic interest and there was essentially no open research in the field.

As an illustration of attitudesm in the field, in the early 1980's, I was a graduate student in computer science at Yale.  In one of those "current topics in research" seminars, I presented a couple of talks about cryptography - the very first such talks ever given at the department.  I don't recall exactly what I covered, but it probably started off with Shannon's work, then Feistel networks and DES, then DH and RSA.  I remember some initial dismissive remarks by a theory faculty member, basically saying "what's the point, you can always get a faster computer."  I think people came to see, by the time we talked about DH and RSA, that there was more going on.  Within a few years, the same dismissive faculty member had published at least one paper related to cryptography, and one of his advisees had gotten a PhD on the subject of cryptographic mechanisms for fair elections.  (That same advisee and I also published a paper - on generalized secret sharing systems.)

> Wouldn't it make sense to start making the switch to quantum-resistant algorithms before such computers are publicly or commercially available to stop something like this from happening?
Even the NSA is pushing for that to happen!  It's not clear (to me, anyway - haven't followed the literature) how high our confidence is that the new mechanisms really are secure against quantum attacks.  At the moment, we know which ones are *in*secure in the same way that we know that certain classic techniques are insecure:  Because we have attacks against them.  But do we understand enough yet about what quantum attacks might possibly accomplish?  It's a difficult field.  Changing cryptosystems is a very complex and expensive business; it would be really problematic to have to go through it twice.

Keep in mind that the NSA's motives in calling for a transition to quantum-resistant algorithms (some of which, as I recall, they've published) might not be as simple as they seem:  They have a long history of pushing public cryptography toward NOBUS - Nobody But Us - areas, where they know about weaknesses that they can exploit (in the algorithms themselves, in the complexity of getting the implementations right, or in other ways) but that they don't believe anyone else can exploit.  And if all else fails, they just go for delay.

It's a difficult, very complex area and rushing in is a bad idea.  On the other hand, so is waiting too long....
                                                        -- Jerry