Hacker News new | ask | show | jobs
by JanisErdmanis 1001 days ago
It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required.

It's similar to how FM radio works: there's a main frequency and several sidebands. When you adjust the tuner to pick up a station, you're essentially "interacting" with the corresponding station. But if there are too many stations, you may no longer be able to hear the music, and as a result, there would be only a static noise present.

This leads me to a somewhat cynical conspiracy. Imagine the moment when a curios government agency realises that building a quantum computer for this purpose is a futile endeavor. Instead of admitting this, they could perpetuate the idea that its construction is just around the corner. Then, act as a wolf in sheep’s skin and introduce everyone to quantum-resistant solutions, which are unfortunate to have secret hidden backdoors by having done more advanced research on them. Has anyone thought about this?

15 comments

Doesn't your argument apply to classical bits too? The more interconnected a classical bit is, the more parasitic coupling it will experience. That used to be an argument used against the feasibility of classical computers in the 40s (until von Neumann published work on fault tolerant classical computing).

Both classical and quantum computers (1) can not "scale" without error correction because of analog noise (although it is less crucial on the classical side), but (2) can be build with error correction codes integrated in them to overcome that noise.

Also, you do not need all-to-all connectivity between your qubits (or bits) to build a scalable quantum (or classical) computer.

Edit: To add to your FM radio metaphor: you can have way more FM radio channels if each channel is on a separate coax cable (or in physics speak, if you multiplex not only by frequency but by spacial mode). No need to have all your qubits be controlled by the same optical or microwave mode, you can have physically separate control lines for each qubit and then eliminating cross-talk is as simple as inverting an n-by-n matrix.

To add to the sibling comment, the reason our classical computers work is because the individual transistor errors in your CPU are basically zero.

We do use “error correction” on storage (and do see bit errors creep into data stored on disk and in RAM over time) but not “fault tolerance” on the compute. In fact there is no such thing as fault-tolerant classical compute - the CPU only works if it “perfect” or “near perfect” (or if you had an ancillary computer that was perfect to implement the correction). Note that occasionally computers do crash due to a bit error in your CPU, or you get a “unstable” CPU that you need to replace.

(We do create fault-tolerant distributed systems, where such faults can generally be modelled and remedied as network errors, not compute errors.)

Quantum fault tolerance relies on the fact that you can do “perfect” classical computation - which I find kind of amusing!

There have actually been a surprising number of computing platforms that implement fault-tolerant processing. It's often called "lock-step" execution.

https://www.vmware.com/content/dam/digitalmarketing/vmware/e... (throughout)

https://en.wikipedia.org/wiki/Tandem_Computers

https://www.intel.sg/content/dam/doc/product-brief/high-perf... (page 5)

With the benefit of hindsight, it is easy to agree with what you say. But from the point of view of the scientists creating the first classical computers, classical fault-tolerance seemed just as difficult to them as quantum fault-tolerant computation seems to us. See von Neumann's "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components" from 1952 https://static.ias.edu/pitp/archive/2012files/Probabilistic_...

Not that it is impossible for OP to be right, but the argument he is using used to be applied to classical computation and ultimately turned out to be wrong in that context.

This idea that multiple redundant voting computing units would be magic to Johnny VN seems unlikely. This is because that exact scheme was used with manual "computers" (people with desk calculators) for example in code breaking and nuclear weapon simulation. You'll find descriptions of these techniques for example in Feynman talks.
> Team member Raphael Some of JPL explains: "One way to use faster, consumer CPUs in space is simply to have three times as many CPUs as you need: The three CPUs perform the same calculation and vote on the result. If one of the CPUs makes a radiation-induced error, the other two will still agree, thus winning the vote and giving the correct result."

https://science.nasa.gov/science-news/science-at-nasa/2005/1...

Yes. In practice it can be worthwhile doing this in distributed compute. These methods (and those from sibling comments) do rely on the error rate being low, and the data compared being much smaller than the amount of compute (eg bytes in final answer << number of CPU instructions used). AFAICT such faults can be treated much like network and storage errors.

What we can’t do is have a set of CPUs where roughly every 1000th instruction fails and hope that plugging together a bunch of computers together to check each other’s progress will work. The specific issue is that the checking is wrong so frequently that you can’t “win” to solve a problem involving trillions of instructions by adding more computers. The overhead of “checking the checkers” just blows up.

What’s interesting about quantum computation is this is exactly what is proposed - have qubit error rates of (I think) around 0.1% and lots of measurement, classical compute, and feedback control to keep the computation “on track”. The whole scheme relies on the error rate for all of that classical compute step to be negligible.

This isn't really accurate. Fault-tolerant classical computing absolutely does exist as a field, and plenty of work has been done there. Some of the early work was done by von Neumann [1] because early computing hardware was extremely error-prone. Over time it turned out that these techniques were not really needed due to the fact that modern solid-state hardware is extremely reliable. The field of quantum computing actually resurrected a handful of ideas that were originally developed for classical computers.

More generally, nobody needs "perfect" classical computing either to make quantum computing work. Given a (quantum or classical) processor with some degree of error, the idea behind these techniques is to "boost" that into a processor with arbitrarily small error. It just turns out that with modern classical processors the error is so small that we suffer it rather than pay the cost of using these techniques.

[1] https://www.cs.ucf.edu/~dcm/Teaching/COP5611-Spring2013/Pape...

It does not apply to classical bits in the same way. Quantum computers derive their computational power from the qubits being in a single quantum state across the qubits (an entangled one, to use physics jargon.)

This is distinct from classical computers, where you can describe a bit without needing to describe the other bits in the computer. You cannot describe a qubit (in a way that's computationally useful, at least) without describing all of them.

But the exponential cost (the need to describe the "whole") is there in the classical case too.

To describe a set of classical bits completely, you need a probability distribution over the whole system (including possible classical correlations induced by the crosstalk that OP spoke about). That probability distribution is a stochastic vector that has 2^n real positive components if we have n bits.

To describe a set of qubits completely, you need at least a "quantum probability distribution", i.e. a ket that has 2^n complex components (I am skipping the discussion of density matrices).

Both the classical and quantum description of the bits requires exponentially many real numbers. This exponential behavior on its own is not enough to the explain "quantum computational advantage". The exponential behavior is well known in plenty of classical contexts (e.g. under the name "curse of dimensionality") and classically solved with Monte Carlo modeling.

Scott Aaronson's lecture notes cover that quite well.

At the end, the issue of crosstalk is modeled in a very similar way in the quantum and classical case, and if it forbids the existence of a quantum computer, it should forbid the existence of classical ones as well. In both cases it is the use of linear binary (or stabilizer) codes that solves that issue.

I may be misunderstanding your argument, but it seems like you are saying that modeling faults in a classical computer also needs to take into account the states of all bits in relation to one another, and that this somehow proves that the problem of crosstalk is similar to interference in quantum computers.

If I have understood your argument correctly I don’t think the conclusion follows from the premise because crosstalk is not fundamental to classical computing. By that I mean that for a given logical cpu design, crosstalk can be (and is) minimized through physical design characteristics (eg grounding, wire spacing etc) without reducing the size of computation. The same cannot afaik be said of quantum computers, where the interaction between qbits is essential to computation

I do not think I follow your last two sentences. Both for bits and for qubits, two-bit gates are required (e.g. NAND for classical and CNOT for quantum). The bits/qubits need to interact for such a gate to happen and should be isolated from one another before/after the gate. And same as with bits and grounding and wire spacing, we use various decoupling techniques for qubits.

Of course, qubits are drastically more difficult, but the principle is the same.

Good point, I said computation, but I was thinking more of the storage and routing pieces of that rather than the gates, likely because I don’t understand quantum gates very well. Most of the quantum ecc I have read about was in the storage lifetime and retrieval process.

Basically what I mean is that classical computing can split things up during storage or routing to reduce coupling, but quantum can’t do this because the qbits must stay entangled to be useful

Not the parent (and gotten my PhD more then 25 years ago), but the answer is no.

Quantum mechanics is a fickly thing. Schrödingers cat has not been observed ;-) because scaling kills the quantum mechanical properties.

My (entirely theoretical) PhD project dealt with a 2 dimensional electromagnetic cavity, with one 'perfect' mirror (100% reflecting) and one 'imperfect', say 99.999999999% reflecting.

My results were that if you started with a 'squeezed' vacuum, in just a few roundtrips, the 'squeeziness' disappears, due to the bath/loss of the non-perfect mirror. My 'gut feeling' tells me that if we have enough qbits to actually factor something more then 2x2, the loss/bath effect will delete any useful use of the quantum computer.

So I am in the 'will not happen' category. (Not in 1, not in 5, not in 30 years, not in 500 years).

This is different from classical error correction: as far as I understand Schors algorithm, there is no 'get N approximate answers, combine them, and get a better answer' part in there. While classically you could do 100 measurements and get a better approximation then with just one.

It doesn't change the overall point you're making but your "gut feeling" was already wrong 20 years ago. A group working for IBM factored 15 = 3x5 with a quantum computer in 2001.

You are also somewhat wrong about the combining N approximate answers and combining them. It is correct that that the "repetition code" approach (repeat the same calculation a bunch of time and average the results) does not work for quantum computers. However there are quantum error correcting codes which do appear to work, although they require sufficiently small initial error rates (so-called thresholds) in order to help.

Yes. In fact the proofs that quantum error correction works as long as you're below a certain error rate (so-called "threshold theorems" are very, very similar to the same proofs that error correction works in classical computers.
Yes, the same as classical error correction but distinct from classical fault tolerance. It’s fascinating (to me) how these are different!
CRYSTALS-Kyber was designed by an academic team, not a government (though a government standards body refereed the competition that selected it; that competition, in turn, was driven by technical feedback that came predominantly from academic cryptography teams around the world). In general, with some exceptions (like curve isogenies), the "math" behind PQ crypto is pretty well established; it was just less attractive than curves were for performance reasons, but is now more attractive if you presume curves will be broken in 20 years by QC.
Yet if you followed the money those programs are funded by government adjacent entities that usually have 3 letters.
None of those researchers have been subverted by academic grants.
But those grants specifically influence that which is researched
People have already said here most of what I want to say in this comment, but just to make it as explicit as possible:

Essentially the only reason anyone thinks that useful quantum computation is possible is because of things called threshold theorems, which state that as long as the noise in each qubit is less than some small but non-zero error rate you can add more qubits and use quantum error correction to make your computation arbitrarily precise. In other words as long as you're below the threshold rate quantum computers scale well.

Of course those threshold rates are very very small, and creating significiant numbers of qubits which are below the threshold rates is incredibly difficult, but theoretically it works.

>...as long as you're below the threshold rate quantum computers scale well.

Last I heard, getting below that threshold was going to take one or two orders of magnitude of noise improvement. That seems unlikely.

Say you were at a VC presentation and the company said that they had this really great system and the only thing stopping their immense success was the requirement to reduce the noise by an order or two of magnitude. Oh, and by the way, we already have the system very close to absolute zero. So you ask them what they are planning to do and they tell you that they don't have the faintest idea. Noise is always the ultimate limit on the information that can be obtained from a system. The most reasonable interpretation of the situation is that a technology doesn't exist and that there is no reason to think it would ever exist.

But when it comes to quantum computers the optimism is boundless. I am not sure why.

I agree with you that the general optimism towards quantum computing needs some tempering. It is certainly possible it doesn't work out and we never get a universal fault-tolerant quantum computer.

I think part of the reason for optimism is that there are a lot of different ways to make a quantum computer. Ion traps, linear optics, resonant superconducting circuits, topological quantum computing (if anyone ever actually discovers an anyon) and many more.

Different groups are working on wildly different directions right now, i.e. Google and IBM are doing superconducting stuff, microsoft loves topological stuff, researchers at various places are doing trapped ions and at least one company (psi-quantum) is working on linear optics.

It certainly wouldn't be surprising if several of these approaches fail to work, but the hope is that they don't all fail.

> the only thing stopping their immense success was the requirement to reduce the noise by an order or two of magnitude

I mean, i know its different context, but in general, a 1-2 magnitude improvement in hardware capability does not sound crazy on its face for most of the computer industry. Most computer hardware has improved by that much over very short time periods historically.

I don't necessarily disagree with what you're saying but multiple research teams do already have error rates below the threshold. It's still early days for the most promising QC platforms, so it's too early to tell if making a QC is possible or not.
I've heard physicists raise opinions like yours (i.e. QC will never be built for practical reasons), but I also hear ones that say the opposite. I'd err on the side of caution.

As for your conspiracy: The conclusion of that would be to continue using hybrid constructions.

Though, and I know crypto more than physics, I'd consider it as highly unlikely. Creating backdoors that others won't find is next to impossible. Why do I say that? Because we have some historic evidence how "NSA wants to plant a backdoor into an algorithm" works. Usually they've been discovered quickly. They can still be successful, because as we have seen with dual ec drbg, it was discovered quickly, yet nobody really cared and industry still used the algorithm.

But something like that won't happen in a transparent process. You can be sure that every expert in the field had a look at crystals-kyber. If anything about it was suspicious, we would know.

It's perhaps telling that NSA has been rather aggressively against the use of hybrid systems, even though they have almost no marginal cost (an extra 56 bytes on top of 1.2kb of PQ exchange) and are the obvious move esp while the PQ systems are very new.
The transparency of the process in an essential way depends on a number of people who can understand what is being proposed. It seems from the outside that the lattice-based cryptography is significantly more complex. The question is, would anyone notice and how far-reaching are the proofs made on their security? On what basis can one prove that a computer with a novel algorithm could not break it?

> As for your conspiracy: The conclusion of that would be to continue using hybrid constructions.

As long as ordinary crypto does not get deprecated.

Anyway, the number of responses made me curious about this new novel crystals-kyber. Do you have any recommendations on the best introductory text that explains it from the bird's view?

> As long as ordinary crypto does not get deprecated.

On that note, just this month Tutanota emailed customers that their Secure Connect product is being turned off at the end of next month in order to focus developers on quantum-secure encryption solutions.

This occurs in a time when there appear to be a stark few hosted E2EE webform-submission options that don't involve either a) bigtech or b) fly-by-night operations. Tutanota was a happy medium, and is getting out of that market, apparently.

It can make one wonder what kind of pressure might exist to turn off a quite good, working solution to an actual problem. If one didn't know better, it could seem that blaming the need for quantum is just a distraction.

The GP is not the first to make the observation in a natural line of inquiry. HN guidelines ask to assume good faith, and surely we know to try to.

Honestly, that sounds more like an excuse to get out of the market. Probably facing a lot of competition from securedrop for the paranoid, and the non paranoid dont care about security at all.
Why create backdoors if you can convince everyone to use less effective cryptography?
> I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required.

Seems weird to be assuming what's possible based on current technical obstruction. If you trace CPUs development, or many other technologies, many people with deep technical knowledge were certain about some thresholds which we have long passed. This bias even had some name which I forgot.

I tend to take "it's impossible" statements from scientists seriously only when the reasoning can be firmly tied to an extremely well established physical law with no "wiggle room."

For example I accept that faster than light travel and inertialess propulsion are both impossible. If either of these things were shown to be possible, it would mean that there are huge errors or oversights in the most well established areas of physics.

I also accept the conditional impossibility of things that are just provably beyond our current ability for fundamental reasons, like a Dyson sphere. I don't know of any physics that says you could not build one, but for us it'd be like dust mites building the international space station.

For everything else I leave the door open. People have historically underestimated creativity.

For the first types of things, taking preparatory steps would be irrational. We don't need to plan for the arrival of FTL travel because we have no reason to think it will ever arrive.

For the latter types of things, preparing does make some sense as long as it's not unreasonably expensive. We do have reason to believe that a large quantum computer might be possible, so mucking around with a bit of code to defend our security against a surprise seems rational.

To a first approximation, the US government uses the same cryptography that US consumers do -- AES, SHA-2, the NIST P curves, ECDSA, etc. are all categorized for various levels of data integrity and confidentiality within the government.

The same will be true of PQ signing schemes, meaning that a backdoor would be predicated on the USG believing that they have some truly remarkable NOBUS breakthrough in PQC. That feels unlikely to me; NSA interventions in cryptographic design have historically gone in the opposite direction[1].

(This is separate from the actual design question. I don't know as much about stateless PQ signing schemes, but the stateful ones are mostly "boring" hash-based cryptography that's well understood to be strong in both settings.)

[1]: https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA's...

> NSA interventions in cryptographic design have historically gone in the opposite direction[1].

I'm not sure I'd say that given that there are some other designs and things that have gone on[1][2]. Particularly the Dual EC debacle. They have a history of helping make suspect or down right compromised crypto if they think they can get away with it. That said it does look like they avoid doing it to anything that gets USA GOV approval for use internally but it's difficult to say to what level they would actually go to for getting a backdoor out into the world that would let them look at other secrets.

[1] https://en.wikipedia.org/wiki/Export_of_cryptography_from_th... [2] https://en.wikipedia.org/wiki/Dual_EC_DRBG

That’s fair. Maybe this is too fine of a hair to split, but I would categorize the Dual_EC fracas as less an intervention and more of a ham-fisted attempt to standardize something that mainstream cryptography was immediately suspicious of. But I suppose you could argue that there was similar suspicion around DES from the very beginning.
The main twist is that we don't know the future but we know how theorical QCs are able to break currently used cryptography, with QCs algorithm like the Shor algorithm: https://en.wikipedia.org/wiki/Shor%27s_algorithm

"As such, as quantum technology advances, there is the potential for future quantum computers to have a significant impact on current cryptographic systems. Forecasting the future is difficult, but the general consensus is that such computers might arrive some time in the 2030s, or might not arrive until 2050 or later." quoted from:

https://datatracker.ietf.org/doc/draft-ietf-pquip-pqc-engine...

> The main twist is that we don't know the future but we know how theorical QCs are able to break currently used cryptography

Under the constraints of us correctly modelling the math of QC. Isn't it possible that we have gaps between our models of QC and how it works in reality that could make it such that these algorithms can't actually offer any speedup over classical approaches in the real world? Or similarly, even if they do work, maybe it's just impossible to build a computer with sufficiently many qubits to outperform classical approaches. Anyway, massive gap between theory and practice with no indication we're bridging it in meaningful ways.

> Under the constraints of us correctly modelling the math of QC.

You're right.

Those questioning are legit, and we don't know.

It could even turn that the post quantum procedures we chose in our times produces messages quickly breakable by classical computers. And that eventually one day, someone discovers it while trying to solve another problem and decides to warn everyone the right way (yay).

In such unpropitious (but, we still don't know) scenario, how cute we'll be if all that attempt for protecting us from the future were sincere.

> Isn't it possible that we have gaps between our models of QC and how it works in reality that could make it such that these algorithms can't actually offer any speedup over classical approaches in the real world?

If BQP=BPP or if BQP did not accurately model a quantum computer, i think that would be a much more interesting result than an actual working quantum computer. It would be world shattering.

Or BQP is a purely theoretical construct with no real-world counterpart. No world shattering result necessarily.

There’s plenty of math that exists purely in the virtual real with no connection to physical reality. Math is a language to describe any possible universe. That doesn’t mean anything we say in it necessarily applies to our universe.

> Or BQP is a purely theoretical construct with no real-world counterpart.

I would consider that world shattering. It would suggest significant flaws in our understanding of the universe which would be very exciting.

Honestly i can't think of a more earth shattering discovery. It would be on par with aliens landing and saying we come in peace.

> There’s plenty of math that exists purely in the virtual real with no connection to physical reality.

Obviously.

The earth shattering part is if quantum physics goes from an accurate description of most of the universe to one that isn't.

What you are basically saying is any theory could be wrong. Well duh, but that describes literally all earth shattering scientific discoveries.

The good news is that if you're willing to take a 2x slowdown for asymmetric encryption (which basically everyone is) you can get the best of both worlds by wrapping your quantum resistant crypto in regular crypto.
So you are claiming the protocol that Signal has adopted is already backdoored by the government. Extraordinary claims require extraordinary evidence. You need to provide some kind of evidence of this. We are talking 20+ years of open and public research on post-quantum cryptography.
I think it's pretty clear that they are theorizing rather than claiming anything?
AFAIK no one is transitioning to PQC algorithms by abandoning classical ones. They concatenate classical and PQC - so-called hybrid.
I agree with this. My concern only applies if the classical crypt gets deprecated or new solutions use PQC exclusively using widespread hybrid use as an argument for trust.
It seems that your primary concern is that the government (or some bad actor) will be able to install a backdoor into PQC algorithms. Is that right? Why would PQC be more exposed to this type of subversion than existing public-key cryptography?

To your point about PQC being used exclusively, post-quantum encryption methods are designed to be resistant to both quantum and classical attacks. That is one of the key stated goals of the NIST post-quantum cryptography program.

it's less about a backdoor and more about just being a lot less robust in general. classical crypto is based on ~100 years of math on finite fields and ~50 years of heavy scrutiny by cryptographers. the post quantum algorithms are much newer and built on much less well studied math. (and empirically, a large number of them have been found to be completely broken). we're at least 20 years from PQC that can be widely trusted. there really just isn't an alternative to having a generation of grad students studying an algorithm that's as old as they are
For signatures, hash based signatures are quantum computer resistant and are also more secure than any other signature scheme. No reliance on a math problem if you don't count the cryptographic permutation to be one, but then everything relies on it regardless of what scheme is used.

The McEliece cryptosystem[1] is one of finalists in the PQC competition and it's also quite old - developed in 1978. It didn't face as much scrutiny as RSA or ECC due to its large key sizes which resulted in nonexistent adoption.

My understanding is that all the other PQC candidates including Kyber are much newer and far less studied.

[1] https://en.wikipedia.org/wiki/McEliece_cryptosystem

Doubly more that the recommended best practices have actually reduced the key length.
If I was NSA, that's exactly the kind of fud (fear, uncertainty and doubt) I'd try to propagate.

While I appreciate and respect the useful criticism, I would be careful with this kind of content:

Regardless wether you read this before or authored it, if you're right then go ahead and show to the world how we're wrong, if you're wrong you're helping quantum attackers.

FM radio has frequency capture, interference there is not additive as in AM. You're very likely to capture the strongest station unless there's a lot of interference.

As for QC, we don't seem to be running into any limits yet. It may well be that any limits are well above useful amount of qbits.

I assume you’re not proposing some kind of interference limit in principle?

Are you suggesting that limiting interference will be a practical dead end that is prevents advancement?

Either way that would be a pretty significant claim. There are lots of research directions being pursued and plenty of smart people think it’s worth trying.

> Are you suggesting that limiting interference will be a practical dead end that is prevents advancement?

This is a hunch I have. Regarding the "plenty of smart people think it’s worth trying", I can only provide an analogy of the 15-14th puzzle known as the Boss puzzle at that time, for which a substantial prize was promised for the first one who could solve it. A lesser-known proof that it is impossible came to surface decades later. There is a lot of inertia in academia along those lines, where grants depend on your ability to make a convincing argument that your path will solve the problem. This sets up PhDs to know only to advance but not to question as the latter does not give the prize.

That’s a good point.

Of course it happens the other way around also - things are thought not to be possible and later realized through some unexpected result or insight.

But I wouldn’t guess that’s as common or as systemic.

Can you explain how qubits are physically implemented in a real-world computer? I just cannot wrap my mind around what they're made of and how they operate in the physical reality.
Disclaimer: No where close to an expert.

My understanding of the more popular superconducting types is that a bit of superconductor is connected up to a junction that allows quantum tunneling of electron pairs. The number of electron pairs that tunnel through the junction determines the state and the state is read out by an exotic electrometer.

As for how the chip itself is made, as far as I know it's a relative standard lithography process except with added superconducting layers.

I need to find a video illustrating all this aha