Schneier on Security

Clive Robinson • August 8, 2023 11:28 AM

Lets be honest up front and say,

“We are fighting an enemy that does not practically exist, and may not exist at some point if at all.”

NIST in the background to the call for standard candidates said,

“If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems currently in use. This would seriously compromise the confidentiality and integrity of digital communications on the Internet and elsewhere.”

However they decided to take the cautious approach,

“While in the past it was less clear that large quantum computers are a physical possibility, many scientists now believe it to be merely a significant engineering challenge. Some engineers even predict that within the next twenty or so years sufficiently large quantum computers will be built to break essentially all public key schemes currently in use.”

And start in even though there was no likelyhood of a “Quantum Computer”(QC) within the foreseable future if at all.

People have to remember that QC like “Artificial Inteligence”(AI) is one of those seeming eternal dreams that are always “a decade in the future” (though based on NISTs own time lines they had put it out to more than thirty years).

But we also need to ask what has happened with QC in the past half decade?

Honest answer the results are slowing down and progress on getting the number of Q-Bits up is not looking at all good[1].

But also we need to also be realistic about how long it will take to replace our existing “Public Key”(PK) algorithms.

And I think NIST was well off base with,

“Historically, it has taken almost two decades to deploy our modern public key cryptography infrastructure.”

Because that is a “New view” not a “Replace view”. Look at it this way,

1, Is DES still out there?
2, Is defective AES still out there?

The answer to both is “Yes” and is unlikely to change anytime soon.

As I’ve mentioned in the past we have to consider “Expected Product Life Time” some of which are upto half a century for utility meters, industrial control systems, medical implants and similar where replacment has high cost.

The fact some people get jittery is a fact of life and there is also the “Chicken Little” syndrome.

My main concern is actually not “when” these things might happen but

“What will happen with ‘Collect it All’ records”

People had an expectation of privacy not just at the time, but forvever.

It’s been pointed out that the Founding Fathers could get both simply by walking into the middle of a field and talk quietly. That is nolonger true technology has made “eavesdropping easy” thus “Privacy hard very hard” and some lunatics wabt to use this to destroy society as we used to know it.

But the question I don’t hear being asked or addrrssed is a fairly obvious one,

“Do we want to replace PK with the same?”

The answer is actually “probably not” PK was a cludge in many ways and it is reliant on assumptions. The PQC equivalents have key sizes that are large, some so large they are bigger than works of literature. You should be suspicious and ask “What hides within?”.

Remember the basis is “One Way Functions with trap doors”, we don’t actually know that One Way Functions”(OWFs) actually exist, as for the “Trap doors” that is an interesting philosophical question along the lines of,

“None, One, Some, Endless, Unknown?”

We need “One” to make a PK replacment work, anything else is not going to be what we want.

It’s interesting that the Chinese are looking at other ways than PK to do secure key exchange, but in the West we give the impression of being so manic about PQC we’ve failed to look at alternatives…

I’m keeping my eye rather more on “Quantum Communications Systems” the version you will hear most about is “Quantum Key Distribution”(QKD). It’s already a practical technology in terms of functionality, the question is,

“Can we make QKD scale in terms of distance and number of users?”

If we can then PQC to replace PK may well be seen historically as a quaint cul de sac.

[1] It’s dificult to measure QC performance, which is why came up with “Quantum Volume” which has subsequebtly been redefined by IBM,

The “latest and greatest” figures,

https://www.quantinuum.com/news/quantinuum-h-series-quantum-computer-accelerates-through-3-more-performance-records-for-quantum-volume-217-218-and-219#

But note the number of Q-Bits is 20. Some years ago the estimate on the number of Q-Bits needed to be equivalent of a high end personal computer was 1000… Each extra Q-Bit improvment is almost like doing what has been done again due to noise, decoherance, and circuit depth.

Clive Robinson • August 8, 2023 10:03 PM

@ anon, ALL,

“By that time it will be too late for any data that has aleady been transmitted anywhere at any time, over any network”

Not quite true.

Whilst PK used for asymmetric algorithms are very susceptible to American mathematician Peter Shor’s 1994 algorithm, it generally does not apply to symetric algorithms.

However many but not all symetric block algorithms are susceptible to Indian-American computer scientist Lov Grover’s 1996 Algorithm. It does not produce an exponential speed up but in effect is the equivalent of taking the square root of the non quantum search. This is the equivalent of “halving the bit width” of the block algorithm so the under Grover’s algorithm 256 bit width AES would be the same strength as 128 bit AES under current attacks.

Then there are other cipher systems that quantum computers will have no effect on. These are ones where the unicity distance is the length of the message.

The most well known is the One Time Pad, which though it is fragile to operator errors is an easy to use pencil and paper “hand cipher” that should have the property that all messages of a given length are equiprobable or as is more commonly said have “Perfect Secrecy”.

@ ALL,

As I’ve mentioned above Post Quantum Crypto Algorithms may not be a worthwhile investment in effort, for key exchange protocols. And that the Chinese are looking at extending both the range and capacity of Quantum Key Distribution”(QKD) systems.

Others are looking in other areas. One such is to extend the notion of “perfect secrecy”. Earlier this year a paper poped up on ARXIV,

https://arxiv.org/abs/2302.07671

Shannon Perfect Secrecy in a Discrete Hilbert Space

15 Feb 2023

Randy Kuang[1], Nicolas Bettenburg

“The One-time-pad (OTP) was mathematically proven to be perfectly secure by Shannon in 1949. We propose to extend the classical OTP from an n-bit finite field to the entire symmetric group over the finite field. Within this context the symmetric group can be represented by a discrete Hilbert sphere (DHS) over an n-bit computational basis. Unlike the continuous Hilbert space defined over a complex field in quantum computing, a DHS is defined over the finite field GF(2). Within this DHS, the entire symmetric group can be completely described by the complete set of n-bit binary permutation matrices. Encoding of a plaintext can be done by randomly selecting a permutation matrix from the symmetric group to multiply with the computational basis vector associated with the state corresponding to the data to be encoded. Then, the resulting vector is converted to an output state as the ciphertext. The decoding is the same procedure but with the transpose of the pre-shared permutation matrix. We demonstrate that under this extension, the 1-to-1 mapping in the classical OTP is equally likely decoupled in Discrete Hilbert Space. The uncertainty relationship between permutation matrices protects the selected pad, consisting of M permutation matrices (also called Quantum permutation pad, or QPP). QPP not only maintains the perfect secrecy feature of the classical formulation but is also reusable without invalidating the perfect secrecy property. The extended Shannon perfect secrecy is then stated such that the ciphertext C gives absolutely no information about the plaintext P and the pad.”

And before anyone asks, no I’ve not looked at it in any depth, so I’ve no idea if it is secure or not.

[1] https://www.researchgate.net/lab/Lab-of-Quantum-Encryption-Randy-Kuang

Clive Robinson • August 9, 2023 7:52 AM

@ Winter, ALL,

Re : Sweet spots exist.

“We all tend to look the other way but efficiency and robustness are mutually exclusive.”

Efficiency and robustness are not mutually exclusive any more than efficiency and fragility are mutually inclusive.

I’ve a mantra about,

“Security -v- Efficiency”

Being the norm, but it does not have to be. All real world engineering has trade offs, and thus “sweet spots” exist.

Back in the 1950’s US cars were death traps because the way they were designed was on a production costs basis that had entered a downward spiral, and no single manufacturer could “jump the grove”.

A change in legislation forced all manufacturers to change their behaviour. The grove got closed and engineers got freed up from the limitations. The result was not only did safety go up, but manufacturing costs dropped and as a consequence of lighter vehicles fuel usage went down[1].

Most ICT designers don’t even go for “efficiency” but what marketing sees as “performance” via rather dubious “specmanship”. It’s why we have the “Xmas Gift that Keeps Giving” that came into view with “meltdown” and as we’ve just seen with AMD opens up “side channels” through which information can be extracted.

For years I’ve pointed out that information leakage depends on the energy in and leaking out as well as the bandwidth of the side channel. Reduce any of them and information leakage goes down.

Thus the trick is to make those reductions without overly effecting performance. One way is by the use of parallel path systems and segregation.

[1] What many would see as things moving in the right direction got halted by the SUV “carve out”. If the US wants to decrease it’s frankly horrifying road death numbers they have two basic ways.

1.1 Cut speed limit on all roads, with it down to 20mph in city suburban and urban roads.
1.2 Get the weight and size of vehicles down and change body shapes

They can also make all bodywork “impact absorbing” that is effectively energy absorbing crumple zones. Such bodywork is actually less costly to make than what is currently made.

Clive Robinson • August 14, 2023 4:37 AM

@ Winter,

“Robustness requires excess capacity. Efficiency required no excess capacity.”

Err neither statment is true, all you’ve defined is “a point on a line”.

Robustness requires “only sufficient” capacity to function continuously at maximum load.

Likewise,

Efficiency requires “only sufficient” capacity to function continuously at maximum load.

Thus the “capacity” will be the same, that is provide the robustness required to meet maximum efficiency.

You see this in power electronics design where you “Design to the load line”. Where you select “a load” based on the device manufacturers maximum power ratings curve supplied in their data sheet.

However I’ve often designed significantly beyond the load line in the “storage quadrants” using both the maximum voltage and current ratings combined. The trick is to use them in such a way that maximum current occures at minimum voltage and the reverse. That is you use the device as a “true switch” in a digital not analog Class, like Class E. What you have to ensure is that the device disipation over time stays inside the manufacturers maximum power curve.

Clive Robinson • September 13, 2023 8:18 AM

@ Winter, Paul Koning,

Re : QC ECC

I’m not sure you to guys are talking about,the same issue.

The thing about the plants is each part is independent of each other.

In the QC however all the parts are interdependent.

Clive Robinson • September 13, 2023 12:24 PM

@ Winter,

“But the light harvesting complex is one big multi-part quantum machine…”

Each cell where light harvesting goes on, it’s function is independent of all the other cells.

The commonality is nutrients in and what are effectively sugars out, both of which are very much non quantum systems of chemistry and basic physics, that you can build and demostrate at home as a school science project.

The potentially 10^6 quantum logic gates / Qbits in a usefull QC have to work together and in synchronisation without loosing coherence for a significant period of time. So the quantum gates / Qbits are not independent of each other.

Further with a QC is the question of coherence distance, that is d=tC/e where “C” is the speed of light “e” is the constants of the system non freespace effects and “t” the time coherence can be usefully maintained for the Qbits in question. Depending on the Qbit t ranges from just a few pico seconds to just a few micro seconds in systems people have considered. The Qbit traps are generally many thousands of times in size bigger than the Qbit, which is quite a lot of effective realestate even for 1/1000th of the number of Qbits required.

So pardon me, if based on the information we have, I’ve my doubts on the viability on the sort of QC needed to gain benifit to apply to modetn RSA key sizes, or the larger AES “extended” key sizes.

But as I’ve also indicated other conventional logic is catching up fast. Logic gates clocking at 10GHz is an accepted thing but not generally usefull in the design of “general purpose CPUs” which is where the use of “hardware algorithms” using FPGAs and “chain algorithms” without feedback comes into play. It’s not hard to envisage a 10,000 times speed improvement for some algorithms over that which can be achieved with a general purpose CPU.

So with the QC achievement curve being both shallow and slow, and the hardware algorithms being far from shallow or slow… The point at which QC is “going to pay the rent” is moving away faster than QC achievements are being established.

Hence my original comment that @Paul Koning refrenced above.

I’ll tell you what, there are atleast a couple of people that read and post to this blog, who’s work dependency is way closer to QC than mine, I’ll leave it to them to express their viewpoints.