[Cryptography] Quantum computers and the Government

[John Levine]

It appears that Jerry Leichter <leichter at lrw.com> said:
>> What are the odds that governments already have quantum computers capable of breaking encryption (or will soon) and not tell anyone?

>However, it seems unlikely.

Agreed. Quantum computing is a hardware problem, RSA encryption is
software. Once you have the insight to use a hard-to-reverse
calculation to build a crypto system, you can write the code on any
ordinary computer. We have Shor's algorithm, but what we don't have is
hardware with enough stable qubits to run it. Barring some very
unexpected breakthrough, we will see incremental improvements in
quantum computers as people slowly get better at the engineering
problems. It's sort of like asking in 1962 when commercial vendors
were just figuring out how to manufacture reliable individual
transistors whether a secret government lab had a 10,000 element
microprocessor chip. Not likely.

>> 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.

Pretty confident.  Some calculations are amenable to quantum methods, some aren't.
Only what one might call "reversible" computations are, but those happen to include
multiplcation/factoring and exponentiation/logarithm.  Hashing, on the other hand,
is not reversible because multiple inputs hash to the same output and you can't
tell which input you started with.  So it's relatively straightforward to tell
whether a quantum computer could run an algorithm.

As to the urgency, it's urgent to get get new algorithms even if we don't expect
working quantum computers for a decade or more.  There is plenty of encrypted material
and digital signatures that have to remain secure for many years.  It is not rare
to collect encrypted material in the hope it might be broken later.  Some of the Venona
intercepts were decoded decades after they were sent and were still interesting.

R's,
John

PS:

>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, ...

I was probably there and I don't remember the talk at all.