NIST has organized a competition for public-key algorithms secure against a quantum computer. It recently published all of its Round 1 submissions. (Details of the NIST efforts are here. A timeline for the new algorithms is here.)
echo • December 27, 2017 9:06 AM
I have been wondering if quantum entanglement and the new paper showing how tracking unoberved quantum particles can be used to transmit information? (I read wiki on position-based quantum cryptography and they mention tagging too.) I am fairly sure I have misunderstood something very obvious making this impossible.
@Lisa
This article on Sciencealert mentions decoherence
https://www.sciencealert.com/10-qubits-chip-new-quantum-computing-superposition-record
The only problem – entangled qubits are also prone to the decoherence we mentioned earlier.
To stop this from happening, the superconducting circuits were cooled to incredibly low temperatures to keep the qubits coherent for longer. In this case the central bus was able to create entanglement between two qubits, between multiple pairs, or between all 10 qubits on the board with a single interaction. All without collapsing.
Petre Peter • December 27, 2017 10:11 AM
It seems that the agreement to compete no longer makes this a movie plot scenario.
Lawrence D’Oliveiro • December 27, 2017 12:27 PM
As I understand it, nobody has successfully used these “quantum”* computers to solve a number-theoretic problem (e.g. cryptography and cryptanalysis); they have only been demonstrated working on ones which involve numerical analysis (physical problems etc).
This points to their true nature: they are an updated version of the old “analog computer” concept. In the earlier part of the 20th century, analog computers could solve such numerical problems much faster than the digital machines, but at the cost of much lower precision. These “quantum” machines are exhibiting exactly the same characteristic.
*In quotation marks because no existing computer would work without “quantum” effects.
Rhys • December 27, 2017 12:37 PM
Anyone hear of or aware of the distinction between effective superselection rules vs classical determinism (or strict superselection rules)?
The robustness of the preferred states is related to the fact that information about them is stored in a redundant way in the environment (e.g. …because Schrödinger’s cat has interacted with so many stray particles: photons, air molecules, dust).
Grauhut • December 27, 2017 2:28 PM
@Lisa: Just follow the IBM Q Group Blog
https://www.ibm.com/blogs/research/2017/10/quantum-computing-barrier/
Let a selflearning ai play with a quantum computer and cypher text and things become funny. Fast. 🙂
justina colmena • December 27, 2017 4:23 PM
Post-quantum? The general consensus is that that’s pretty far out there.
What about Post-P=NP cryptography? Why is it so universally assumed without proof that P!=NP?
Jack • December 27, 2017 6:05 PM
What about post-cryptography? You know, burned out users who give up on privacy entirely?
Ken Thompson says hi.
MrC • December 27, 2017 6:56 PM
@ Lisa:
If a “practical” quantum computer is ever built, it can be applied to pretty much all stored encrypted communications. Not even the much-ballyhooed “perfect forward secrecy” does any good when the ephemeral keys can be recovered.
We know that the NSA is collecting and storing all encrypted communications and shoving them in the hole in the ground in Utah. Possibly other entities too. So, it’s a safe assumption that every encrypted communication from now till forever is going to be a stored communication vulnerable to some hypothetical future quantum computer.
Secrets have lifetimes. Today’s secret may be tomorrow’s old news, or next week’s, or someday’s. Eventually everyone who cares or would be affected by a secret coming out will die of old age. The goal of encryption is not so much to keep secrets safe forever, but to keep them safe beyond the end of their lifetimes.
Now, let’s assume that at least some secrets have a 50-year lifetime — that, in some cases, what you say today could still get you shot if it came out 50 years later. Working backwards, that means that we’d want to have post-quantum encryption up and working and in general use 50 years before the advent of a “practical” quantum computer.
If we wait until a solution for quantum decoherence seems imminent, it will already be too late. In order to act timely, we must act on predictions about how quantum computing might develop several decades from now. Error is inevitable, but Pascal’s logic can help us see which error to prefer: Which is worse: to deploy algorithms that are otherwise unnecessarily slow and bandwidth-hungry to defend against a threat that never materialized, or to watch the encryption protecting decades of stored communications crumble to dust because we moved too slowly?
Gweihir • December 27, 2017 10:47 PM
@Lisa:
I agree very much. This seems about as premature as 25 years ago, when I first heard of Quantum Computing. It seems, besides some capability to inspire fantasy, Quantum Computing has delivered basically nothing to this day. And there is the little problem that whenever Physics went into extreme regions before, new effects were discovered that were too tiny to notice before. That could easily kill the supposed computing power of Quantum computers, in particular as the precision levels needed to break crypto far outstrip anything else the human race has ever done or measured in the analog space.
hmm • December 28, 2017 12:18 AM
“everyone who cares or would be affected by a secret coming out will die of old age”
What about secrets that are bigger than any one person’s life?
echo • December 28, 2017 12:25 AM
Nobody has answered my question about entanglement and measuring unobserved particles. They solved decoherence for one problem. There is also another recent paper which discusses control of the movement of quantum particles. I’m not sure how useful this is or whether it can cross over and be used in combination with entanglement as well to transfer information.
Speaking which after doig more diggging and discovering the “Zeno effect” I also learned about “counterfactual communication”. I just discovered another article which explains that my theory is possibly correct.
https://phys.org/news/2017-12-secret-movement-quantum-particles.html
“To measure this phenomenon of counterfactual communication, we need a way to pin down where the particles between Alice and Bob are when we’re not looking,” said Arvidsson-Shukur. “Our ‘tagging’ method can do just that. Additionally, we can verify old predictions of quantum mechanics, for example that particles can exist in different locations at the same time.”
Wulf • December 28, 2017 2:33 AM
More than 15 years ago people already started researching quantum-computer-cryptosystems on a theoretical basis. It was just a matter of time until NIST started a competition for this.
Ziggy • December 28, 2017 4:19 AM
Gweihir
i remember you. You’re that guy with the compunction to disagree with Clive Robinson.
Drone • December 28, 2017 6:33 AM
So 5-7 years before the first post-quantum algorithms are ready. Maybe in that period quantum computers will be developed so they can help shorten that time. But if-so, the global economic system will collapse due to quantum computing. Sigh 🙁
BitFlip • December 28, 2017 6:58 AM
Quantum-secure public/private key encryption is necessary to allow cryptocurrencies to survive quantum supremacy. Currently, only QRL is (allegedly) quantum secure. But I don’t understand what makes their approach secure. If we can’t find a quantum secure public private key system, then bitcoin and all the other cryptos will collapse. Current market cap is 557 billion dollars.
MrC • December 28, 2017 7:59 AM
@ hmm:
Same deal: Eventually everyone who cares will die. If the secret pertains to something with multigenerational appeal, it could take awhile. So, if you’re planning to use encrypted communications for your rebellion/religion/secret society, best move to post-quantum algorithms now.
Wael • December 28, 2017 8:32 AM
Oh, don’t be so self-centered, PQ is not for you and me. It’s for the Big Boys.
Ask not what you can hide from your country — ask what your country can hide from you 😉
hmm • December 28, 2017 2:36 PM
“Eventually everyone who cares will die.”
Secrecy through fatality? Everyone dies, but not all secrets become obsolete in a generation or 2.
Ross Snider • December 28, 2017 3:41 PM
I was not able to do a full review of all of the submitted documents. However in broad strokes it seems to be true that most of the codes are:
There seem to be multiple proposals running at the same time, as many authors broke their submissions into signature proposals separate from encryption proposals. There were a large number of proposed key encryption mechanisms (for obvious reasons).
I did not see any post quantim elliptic curve proposals.
(Limitations: only checked the submissions with websites).
Love seeing this kind of work. Let’s get some standards with nothing-up-my-sleeve properties.
Even if we don’t come up with a proposal that works for everything (key/signature sizes), this will move us toward schemes that increasingly provide better properties.
MrC • December 28, 2017 8:36 PM
@ hmm:
I think we’re quibbling over a minor point.
My main point is that, in a world where all encrypted communications are stored (i.e., the one we live in), algorithms need to be rotated out of service one full secret lifetime before a cryptoanalytic break. This is in response to Lisa’s head-in-the-sand-ism that we don’t need to worry about moving to post-quantum encryption until the quantum decoherence problem is solved.
This point holds regardless of how long a secret lifetime happens to be. You seem to take issue with what I consider a very minor point — that all secrets eventually become irrelevant, for a sufficiently longsighted definition of “eventually.” I agree with you that some secrets may have very, very long lifetime. Which reinforces the conclusion that we are likely already running late with replacing RSA and ECC with something post-quantum.
David • December 29, 2017 1:15 AM
A good post-quantum cryptographic system is another name for Vernam Cipher.
We don’t know whether quantum computers already exist. Nor do we know whether the whole concept is merely fanciful. We don’t know whether public-key algorithms in all of their forms are already being broken like candy cane.
If Bob and Alice know they are up against INGSOC’s quantum computer, burying Vernam Cipher from an air-gapped device into completely innocent-looking traffic starts to look doubleplus good.
JG4 • December 29, 2017 8:05 AM
@David – your skepticism is a virtue, but I think that there is enough scientific literature on quantum bits and quantum commputing to make it perfectly clear that the machines already exist. whether they are useful to empire for human rights abuse remains to be seen. I agree completely with your comments on double-plus good. the hardest message to decrypt is the one that you and your quantum computers don’t even know is there. the hardest metadata to collect is the metadata that your algorithms can’t see.
an0 • December 29, 2017 5:45 PM
Does this competition involve creating new standards for symmetric encryption as well? I know that in the opinion of many, symmetric ciphers just need to “double their key size” but that currently isn’t done for any of their implementations, because there isn’t a standard telling anyone to do so. Also, I’ve read some skepticism as to whether simply doubling key sizes of existing symmetric ciphers is enough to be truly quantum-resistant. So, it seems as though it should be part of the discussion along with asymmetric crypto.
Hweihir • December 29, 2017 8:34 PM
@Ziggy:
You remember wrongly. I only disagree with Clive when he is talking out of his backside and I read what he wrote. The second has gotten rarer, much of what he writes is a waste of time to read. I may still disagree with him on occasion, without actually knowing it.
David • December 29, 2017 10:33 PM
@JG4 I completely agree.
From the viewpoint of denying access and defeating cryptanalysis in quantum world, a good way forward will be to hide Vernam Cipher in the big haystack.
As you said, there is no metacontent if there is no message. And notice that the cost of mass collection will have become astronomical because surreptitious entry is expensive.
The technical challenges of (1) generating large quantities of high-quality truly random numbers
(2) in systems that are very difficult to subvert (3) and are easy to use for everyone (4) breaking the trail of electrons to and from the collection platform in a genuinely air gapped system–and then burying it, ready to be exhumed–this is exciting.
The INGSOCs of the world have advantages, especially as the technology gets sexier. But the logic of the bureaucracy is against them–spend, spend, me, me–in fetishizing technology and only wanting to grow. Low-cost, highly effective solutions do exist which can change the game.
In my mind, protecting the privacy of Americans is consonant with supporting and defending the Constitution of the United States.
Rachel • December 30, 2017 4:07 AM
Gweihir
self revelation noted by the collective.
your existence on this forum continues in your own mind only. you are a ghost. your name and words are ignored. good luck skulking the desolate outlands. oh and good luck treating the pox
Gweihir • December 31, 2017 6:39 PM
@Rachel:
You probably should seek medical help. You seem to be living in a delusion.
Forest Bailie • December 31, 2017 9:55 PM
@Clive Hater without a name
i suspect what she is saying is, by your stance you are entirely ostracised and excluded here you have forfeited all identity and must wander in exile. which sounds like something you are familiar with. the pox is figurative for being the subject of ill wishes at least in the fiction i used to read. but i think you know all that
Itching sock companion • December 31, 2017 11:40 PM
@Gweihir:
You probably should seek medical help.
Speaking of medical help, has the PR specialist eased your problems? Or is the low residue diet making you extra grumpy prior to the manual extraction?
PKCs • February 2, 2019 2:59 AM
Verisign Labs Distinguished Speaker Series:
Ralph Merkle: Quantum computers and public-key cryptosystems – September 19, 2013
Merkle and many others expert in the field are telling a cautionary tale (despite many of those actually implementing crypto in the open source and commercial world today, even those implementing security-oriented systems, disregarding this) of quantum computing’s critical threat to PKCs’ widespread and systemic use for encryption and authentication and the fact that PQC with the same properties may never be available…there seem to be no copies on YouTube of this talk or any other on this topic by Merkle, and this Verisign video is referenced on his site http://www.merkle.com.
Since Verisign decided to break all early-mid 2010s Verisign Labs speaker series sites, try using archive.org (hopefully they’ll be there)
Luckily ooyala/telstra still retain a copy of the video content. To be sure that video content doesn’t disappear, the direct web archive video link is also below. (hey you get to avoid executing ooyala’s javascript).
Archived Talk URL:
Direct Ooyala Video (Web Archive) URL:
If there are other talks that are worth something from Verisign labs series, I encourage others to share them…to read more on this, read the full pastebin that contains the above text and a bit more
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
Lisa • December 27, 2017 8:44 AM
Sorry, am I missing something here? Has the quantum decoherence problem been sufficiently solved?
I last heard that physicists do not know yet how conherenent qubits in a general purpose quantum computer capable of running Shor’s algorithm and other similiar public key busting routines, will scale with the increasing number of qubits. The current record for quantum factoring uses at most 4-6 qubits, and took 2 years to set up.
Many still think that this may scale exponentially, such that it may require more energy than in our galaxy, or more time than trillions of years, to set up a sufficiently powerful quantum computer and operate in such a manner capable of breaking a single large public key.
Until we know that public key busting quantum computing is even physical possible/practical, this seems like a science fiction threat that we should not concerns ourselves with any more than we do with other sci-fi threats to crypto such as time travelling, parallel universes, or hyper-intelligent AI.
Actually the last threat seems to be much more of a practical concern than quantum computing or the other sci-fi threats are, since advance intelligence (be it AI or a lucky and brilliant humans) are much more likely to find exploits against trapdoor functions which are at the heart of all public key cryptography.
Personally until there is some physical experimental evidence regarding qubit scaling for a general purpose quantum computer, I think that more research effort should be spent on understanding and validating existing public key crypto and also developing new and better trap door functions, than just focus solely on quantum resistance alhorithms.