Quantum Bayesian Networks

September 1, 2012

RSA Easily Breakable by CIA or Chinese Gov. 5 Years From Now?

Filed under: Uncategorized — rrtucci @ 12:22 pm

The Cleland and Martinis groups at UCSB have struck pay-dirt again (see Refs. below). This time they have used their QC made with superconducting qubits to factor 15=3X5 using Shor’s algorithm. Furthermore, they believe they have a clear road map for scaling up the size of their device so that it can factor larger numbers. And so far they have a very good track record of doing what they’ve promised.

RSA cryptography, which is based on factoring numbers, is the most common kind of cryptography used for commerce on the Internet. RSA is almost impossible to break with classical computers, but could be easily broken by a UCSB type device, if such devices can be scaled up.

There are certain types of classical cryptographies, called post-quantum cryptographies, which cannot be easily broken by QCs, as far as we know. Some are already available, although not yet in a convenient form.

In theory, switching from RSA to post-quantum crypto should be possible long before QCs arrive. But one shouldn’t forget human inertia. World history is full of examples of situations (Maginot Line, Hurricane Katrina, building whole cities on flood zones, fault zones, and next to volcanoes, etc., etc.) in which societies and their governments took too long to react to an approaching danger, or reacted inadequately to it. It’s likely that some mismanaged institutions and some people that are naive or ignorant or careless or prone to procrastination will continue to use legacy RSA code, long after a cheap and convenient post-quantum substitute is available.


  • “Computing prime factors with a Josephson phase qubit quantum processor” by
    Erik Lucero, Rami Barends, Yu Chen, Julian Kelly, Matteo Mariantoni, Anthony Megrant, Peter O’Malley, Daniel Sank, Amit Vainsencher, James Wenner, Ted White, Yi Yin, Andrew N. Cleland, John M. Martinis arXiv:1202.5707, published in Nature Physics (19 August 2012).

    Another source of information about the same experiment is Erik Lucero’s Ph.D. thesis, which can be found at Prof. Martinis’ excellent website. Lucero has been hired as a postdoc by the group led by Matthias Steffen at IBM, a group which is working on a QC architecture based on superconducting qubits, similar to the UCSB one.

  • Previous posts in this blog about the Martinis and Cleland groups at UCSB

  • good news for quantum computing?, post by aram at “Quantum Pontiff” blog



  1. A better use of time would be to ask the question what are Many-World like?

    rrtucci: deleted remainder of comment. Sorry, way off topic. And besides, I’m allergic to MWI. It makes me to get all itchy.

    Comment by Martin Musatov — September 3, 2012 @ 11:43 pm

  2. […] RSA Easily Breakable by CIA or Chinese Gov – Quantum Bayesian … […]

    Pingback by Bayesian networks | Sellukus — September 9, 2012 @ 2:54 am

  3. MWI allergic reactions, I certainly share them. Kingsley recently also blogged a nice diatribe on this.

    Comment by Henning Dekant — September 15, 2012 @ 2:52 am

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: