the timeline on which encryption may be broken just got moved up

[Jon "Poprox" Paprocki]

https://www.microsoft.com/en-us/research/blog/full-stack-ahead-pioneering-quantum-hardware-allows-for-controlling-up-to-thousands-of-qubits-at-cryogenic-temperatures/

Another potentially huge W for topological quantum computing. One of the biggest challenges facing quantum computers of any sort are their control electronics - how do you manage many thousands of heat-producing components that manipulate qubits, which generally need to stay very close to 0K?

Microsoft, the only company attempting to build topological quantum computers, now claim they have sufficiently sophisticated control electronics to control thousands of topological qubits.
This is a _big_ deal. Topological qubits are roughly equivalent to several thousand qubits of other architectures in terms of error correction. This is why you may have heard that while breaking RSA with Shor's algorithm ought to only take a few thousand logical qubits, in reality it would require millions of physical qubits - if they were superconducting, or ion trap, etc. Topological qubits correct for errors by virtue of their physics, and so thousands of topological qubits will be sufficient to start breaking cryptography.

Now, it is very important to note that nobody has built a topological qubit yet (though Microsoft has claimed that they are very close for several years running now). On the other hand, because of how they work, once it's possible to make one it should be possible to make many. This is because topological qubits ought to be able to be "spawned" simply by creating the correct electromagnetic conditions, rather than by building and connecting innumerable nanoscale physical devices. So the largest difficulty is in creating those conditions, but once they have them, it's a much smaller challenge to repeat it.

So the timeline for when cryptography may be broken may have taken a big step forward. If Microsoft manages to build a topological qubit this year, it might only be a few more years until they can start breaking cryptography, since they apparently have the control electronics figured out.

The generally accepted timeline for quantum crypto doomsday has been something like - 2025, incredibly unlikely, 2030, decent chance, 2040, almost certainly. The wildcard has always been topological quantum computers, and this development just made 2025 move up from "incredibly unlikely" to "within the realm of possibility". Given the other major unexpected leaps in experimental quantum topology last year, such as the discovery of Majorana fermions in gold [0] and unambiguous confirmation of the presence of abelian anyons in fractional quantum hall liquids, I am becoming much more confident that topological quantum computation is a real possibility and could take the crown for dominant architecture sometime in the 2020's.

--

[0] https://news.mit.edu/2020/first-majorana-fermion-metal-quantum-computing-0410

[1] https://www.purdue.edu/newsroom/releases/2020/Q3/new-evidence-that-the-quantum-world-is-even-stranger-than-we-thought.html

—

~datnut-pollen

https://urbit.org

[Christopher King]

I must admit, Nadella’s done a lot to turn around a company Ballmer almost drove into the ground. Good to see Microsoft taking the lead on something again instead of playing catch up with Amazon and Google.

--
To unsubscribe from this group and stop receiving emails from it, send an email to dev+uns...@urbit.org.

--

Best,

Chris

[Jon "Poprox" Paprocki]

Yeah, as someone who spent most of the 2010's studying this architecture, I am very pleased to see Microsoft's gambit coming close to paying off. For most of the last 20 years, topological quantum computing has been seen as unrealistic at worst, and fascinating mathematics at best. It's only in the past 2 years or so, with long-standing experimental challenges finally being surmounted, that more people in the quantum computing community are starting to take it seriously. Now MS is in an extremely strong position, because they have practically have a monopoly on topological quantum computing talent outside of academia, since they've been working on this approach since 2005.

I shared this with the urbit-dev list mostly to get people in the mindset that Urbit needs to start preparing for this future soon with post-quantum cryptography measures. Remember, anything that is not currently encrypted with post-quantum methods can just be stored and cracked once crypto doomsday arrives. Probably the most important thing to track in this is the competition that NIST (National Institute for Standards and Technologies) has been running since 2016 to form standards for post-quantum encryption. They expect to release recommendations in 2022. What you can do right now is learn about what algorithms are still in the race.

--

—

~datnut-pollen

https://urbit.org

[Yaseen S]

Woah, this looks insane. Two questions come to mind:

1. How much work would a migration process take for Urbit to migrate to new crypto algorithms (e.g. how "pluggable" is the crypto suite)? Any plans so far?

2. How would Azimuth adapt to this? I guess that opens up the discussion more broadly to cryptocurrencies. Since Azimuth is pretty tightly integrated with Ethereum, it seems like it would be probably the most contentious place to be affected by this. It also seems to me the area which would take the biggest hit, because the rest of the Urbit platform is predicated on ownership.

[Jack Fox]

Microsoft has for years claimed to have the fastest QC simulator  https://www.microsoft.com/en-us/research/publication/liqui-a-software-design-architecture-and-domain-specific-language-for-quantum-computing/ which has been good enough to publish some real science in analyzing simple molecules.

They have also developed the Q# language https://en.wikipedia.org/wiki/Q_Sharp (I know the lead architect of Q#) as a QC programming language which they designed to be adaptable to any QC or QC simulator.

[Jon "Poprox" Paprocki]

1. How much work would a migration process take for Urbit to migrate to new crypto algorithms (e.g. how "pluggable" is the crypto suite)? Any plans so far?

I haven't done a serious study on this yet so I don't want to make any predictions on timeline or how much work it will be, and for that reason I also don't make any guarantees on the correctness of anything that follows.

I think there are three main things that need to be secured though: Ames, the runtime, and the PKI.

Ames messages are what could be collected and decrypted someday, so that needs to come first. Post-quantum encryption algorithms typically either have very large keys and smaller messages, or smaller keys and very large messages. Depending on the use case, we might want more than one algorithm available. Just making algorithms available shouldn't be hard, but properly implementing them into various use cases might be - at least according to generic advice I've read from researchers in this area that may or may not apply to Urbit.

For the runtime, I don't know enough to say anything concrete. When we had a security audit on Ames last year, the auditors pointed out a few potential security issues with the runtime. It might be possible that quantum computers could introduce additional attack surfaces in the runtime. It might also be the case that there is nothing to worry about. Either way, off the top of my head I can't think of how the risk would be analogous at all to the one with Ames, meaning that it's not a real issue until quantum computers are big enough to pull off the attack. But I don't know how big that might be, or what the attacks might be, etc.

2. How would Azimuth adapt to this? I guess that opens up the discussion more broadly to cryptocurrencies. Since Azimuth is pretty tightly integrated with Ethereum, it seems like it would be probably the most contentious place to be affected by this. It also seems to me the area which would take the biggest hit, because the rest of the Urbit platform is predicated on ownership.

 

For the PKI, this is tangled up with a lot of other factors. On one hand, hash functions are not really affected too much by quantum computers. But they do break things like what is currently used to generate public/private key pairs for wallets. What needs to be done here just depends on what solution we end up using for the current PKI issue, and whether we introduce additional changes for the PKI later, like an Urbit-hosted PKI. Last I checked, Ethereum has plans to introduce Lamport signatures to get quantum secure wallets. But incorporating such wallets into layer 2 solutions might have its own complications, same if we end up with social recovery wallets someday (which are actually smart contracts rather than ordinary wallets), etc. But like with the runtime, this shouldn't be a real issue until quantum computers actually get big enough to perform attacks.

I'll be starting to think about this more seriously sometime later this year. Once I have a better idea on the scope of things, I'll write about it.

--

—

~datnut-pollen

https://urbit.org

[Jon "Poprox" Paprocki]

tl;dr The original reason I wrote the initial email is no longer relevant due to a retraction. But the timeline might still be moved up for a completely different reason.

Some more recent developments.

There are two main experimental approaches to topological quantum computing: one based on Majorana zero modes on nanowires, and the other based on non-abelian anyons in fractional quantum Hall liquids.

The Majorana approach has long been the more promising one. Kouwenhoven's group (which works closely with Microsoft) at Delft has published a lot of the biggest progress in this direction over the last decade, but it has been very slow, as the nanowire growth technique is extremely difficult, and detecting Majoranas unambiguously is also very challenging. In 2018, his group claimed to finally have unambiguous evidence of Majoranas, but a couple weeks ago they retracted the paper:

https://www.wired.com/story/microsoft-win-quantum-computing-error/?utm_brand=wired&utm_medium=social&mbid=social_facebook&utm_social-type=owned&utm_source=facebook
https://arxiv.org/abs/2101.11456

This is a big setback. IIRC, Kouwenhoven's group thought they had evidence of Majoranas as early as 2013 (maybe even before then), so it's difficult to say how long this could take to work out. At the very least, there is now less of a reason to believe that this approach will be fruitful in the near future. The original announcement about the Gooseberry control chip is still a big deal for other non-topological architectures, but the reason I felt it important to write the original email was specifically because of its potential application to this Majorana approach, and that only a few thousand Majorana qubits would be necessary to put many ordinary cryptography methods in danger.

The other main approach, with fractional quantum Hall liquids, hit a major milestone last year. Namely, the first unambiguous evidence of (abelian) anyons was discovered: https://arxiv.org/abs/2006.14115 This is not exactly what is needed for this case - something even more exotic - non-abelian anyons - are needed. But the technique utilized in this paper was designed to work for those too - they just started with the easiest case.

Like Majoranas, these are also extremely difficult to detect. Unlike the Majorana zero mode case (where the difficulty in their detection is closely related to the fact that they have zero energy, so many effects can obscure them), the signature here is unmistakable - there is nothing else known that could create the data. However, the Gooseberry chip is not the right kind of device to control these sorts of exotic quasiparticles. For both Majoranas and anyons, the idea is to "braid" their worldlines in spacetime to perform quantum computation. For Majoranas, the simplest way this is done is by creating T-junctures with the nanowires, and moving Majoranas past one another at the T-junctures. But for anyons in fractional quantum Hall liquids, the substrate in which they appear is necessarily disordered, and so anyons are essentially trapped wherever they are spawned (due to a phenomenon called Anderson localization).

The proposed method to get around this is a technique called measure-based topological quantum computation, which (now this starts sounds like science fiction) works by using quantum teleportation on the anyons in the fractional quantum Hall liquid to do something like braiding them. This requires a totally different sort of electronics than the Gooseberry chip. I don't actually know whether anybody has even started on this part of the problem yet. In any case, I'd be surprised if there is a topological qubit of this sort before 2025, or even 2030.

----

Despite this - there was recently an article published by Bloomberg, saying that a quantum computing company Terra Quantum AG claimed to have discovered that quantum annealers (much simpler machines than universal quantum computers that only perform one algorithm, primarily build by D-Wave) are able to break encryption methods they previously were thought to be unable to. https://www.bloomberg.com/news/articles/2021-02-07/a-swiss-company-says-it-found-weakness-that-imperils-encryption?srnd=technology-vp

At this moment, as far as I have been able to tell, they have not published a paper saying how this can be. It's rather unusual to go to a media outlet about this before a paper is available. So I am quite skeptical. On the other hand - it is only strongly suspected by experts that modern cryptography methods are not broken by quantum annealers, but there has never been a proof of that. So it's not impossible. It's worth paying attention once they actually have a paper - and if it holds up to scrutiny, it's basically Red Alert, because quantum annealers are much easier to build than universal quantum computers. But the circumstances are very odd, so I would still bet against it if I were a gambler. For now, there's nothing to go off of.

--

—

~datnut-pollen

https://urbit.org

[Jon "Poprox" Paprocki]

One minor (but important) typo: I meant to write measurement-based topological quantum computing, not measure-based.

--

—

~datnut-pollen

https://urbit.org