[Cryptography] Quantum computers and the Government

[Henry Baker]

Re: "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."

Or,

It's sort of like the Germans and Japanese asking in 1941 when
electromechanical encryption machines were just becoming
available whether a secret govt lab had an *electronic* code-
breaking computer. Not likely.  ;-)

---
The US got a pretty good 'wakeup call' with Sputnik, but that
was 64 years ago. We've developed quite a lot of flab and
arrogance in the interim. Haven't you noticed the relatively
small % of papers from the U.S. at Crypto conferences?

It will now take the better part of a decade before cutting edge
chips are made on U.S. soil again.

We're finally reaching the feature size where quantum effects
like 'quantum dots' can become ubiquitous.

Change is often discontinuous -- some bright student asks
Nature a 'stupid' question, and gets an unexpected "Yessiree!"

-----Original Message-----
From: John Levine <johnl at iecc.com>
Sent: Sep 1, 2021 12:12 PM
To: <cryptography at metzdowd.com>
Cc: <leichter at lrw.com>
Subject: Re: [Cryptography] Quantum computers and the Government

It appears that Jerry Leichter 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.