Quantum Computers, Encryption Wars, and the End of Privacy

From government to business to regular individuals, encryption is important. It’s how we maintain some level of privacy in our lives. It protects our email and our credit cards. For some, it can be a matter of life and death. And it’s a risky business. We never know if our passwords have been compromised, or if the systems that we use provide some kind of backdoor that allows others to spy on us. But in the future, we may face a much bigger issue: quantum computers.

Encryption depends upon creating mathematical equations that take modern computers an extremely long time to solve — longer than the age of the universe. But quantum computers could change all that.

Just how fast would quantum computers be? Exponentially. To solve a 100-bit encryption problem would take a digital computer 2⁵⁰ steps. That’s:

A quantum computer would take only 50 steps to do the same calculation.

So what are these amazing devices? They are computers that harness the power of quantum mechanics. Digital computers store data in bits. They can be 0 or 1. Quantum computers are based on qubits. They are two-state quantum systems — effectively partly 0 and partly 1. This is called quantum superposition. Think: Schrödinger’s cat.

This may not sound like much, but a whole computational system has been built on top of quantum superposition. And the result is an unimaginably faster computer.

Or that would be the result if anyone had been able to build a universal quantum computer. Creating qubits is very hard. And they are unstable. Currently, they only last on the order of nanoseconds. But big institutions like the National Security Agency and Google are working on them. And progress is being made.

So will all our secrets soon be exposed? Will quantum computers bring an end to online privacy?

Get all the details below.

Quantum Computers, Encryption Wars, and the End of Privacy

From law enforcement to criminals, governments to insurgents, and activists to Facebook dabblers, many people have come to rely on encryption to protect their digital information and keep their communications secure. But the current forms of encryption could be obsolete the moment anyone succeeds in building a quantum computer. A what?! Read on about the brave new world awaiting us.

Binary vs Quantum

• Binary
  • Typical computers are binary – they encode information as a series of 1s or 0s
    • This applies even to supercomputers, which operate hundreds of thousands,if not millions, of times more quickly than regular computers
  • These 1s or 0s are called “bits”
    • A bit has two states:
      • On/1
      • Off/0
• Quantum
  • A quantum bit is called a “quibit”
    • Qubits can not only be 1 or 0, they can be both at the same time
      • This is called “superposition”
      • Certain molecules, atoms, and electrons have been used successfully as qubits
• The value of a quantum computer
  • One qubit (or bit) by itself isn’t of much use, but the more quibits a computer has, the more complex calculations it can carry out
  • One of the things quantum computers can do better than regular computers is reach an end goal with an exponentially smaller number of operations
    • Factoring large numbers, for example – the basis of much encryption

Encryption and Factoring Large Numbers

• Many common forms of encryption, such as RSA, Diffie-Hellman, and others rely on the difficulty of factoring large numbers for the security of their encryption (though others, such as EC and AES, do not)
  • Prime numbers are those that can only be divided by 1 and themselves
    • 1, 5, 7, etc.
  • All numbers have one prime factorization
    • This means that every number can be reached by multiplying some primes together
      • 68 = 2×2×17
      • 3,654 = 2×3×3×7×29
  • For a computer, finding a large prime number is relatively simple
    • Factoring large numbers is considerably more difficult in that it takes an exceedingly long time to do so
      • Normal computers have to go through each set of primes until they reach the correct set
      • Even supercomputers – which have many processors working in parallel – have trouble with large enough prime factorizations
  • If we had a computer that could do long division in a millionth of a second, it would take longer than the lifespan of our sun to factor a 100-digit number.
    • Our sun has an expected lifespan of 15 billion years.
  • The length of time it would take to figure out the key is what makes using prime factorization so useful for cryptography.

How Quantum Computers Crack the Code

• Even forms of encryption that don’t use prime factorization rely on the fact that brute-force number crunching requires so many steps that doing so is unfeasible
  • To find the pattern in an EC cipher, for example, with a 100 bit key would take
    • Binary computer: 2⁵⁰ (over 1 quadrillion) steps
    • Quantum computer: 50 steps
  • A normal computer has to work its way through each calculation one at a time
    • A quantum computer’s qubits allow it to avoid unnecessary calculations
      • As a result, it can find the answer faster and with far fewer steps

Where Can I Get My Own Quantum Computer?

• D-Wave Systems, Inc. markets their D-Wave Two as a quantum computer, but other computer science experts disagree that it’s a “proper” quantum computer
  • The issue is that D-Wave’s machine takes advantage of some quantum mechanics, but it isn’t a universal quantum computer, able to do any quantum computation
• Here are some of the people working to build the quantum computers and qubits of tomorrow:
  • Google
    • Google has been working with D-Wave Systems since 2009
    • In April 2014, John Martinis and a group of UC Santa Barbara physicists successfully operated five qubits together with a low rate of error
    • Google hired Martinis and his team to work at their quantum hardware lab in September 2014
    • The D-Wave machine that Google uses contains a chip with 512 qubits wired into a quantum annealer
      • A quantum annealer solves optimization problems, like “What is the most efficient route for a package to take across town?”
    • Currently, Google’s D-Wave machine can only keep qubits in superposition for a few nanoseconds
      • According to Martinis, he has built qubits that can last for 30 microseconds (30,000 nanoseconds)
  • National Security Agency (NSA)
    • According to documents leaked by Edward Snowden:
      • The NSA is building a quantum computer capable of performing cryptography
      • It is part of the NSA’s $79.7 million research program called “Penetrating Hard Targets”
  • University of New South Wales in Australia
    • In October 2014, two separate teams of researchers at USW successfully created qubits that are more than 99.99 percent accurate
    • Both teams used Silicon-28, an isotope, in the creation of their qubits as it is perfectly non-magnetic
      • One team embedded a phosphorus atom into the silicon
      • The other team created and then embedded an artificial atom – essentially a transistor with one electron trapped inside
    • The phosphorus atom team set a world record for the length of time quantum information could be preserved in a silicon system before it decoheres: 35 seconds

Quantum Encryption

• Although quantum computers would allow users to crack many forms of encryption already out there, they would also foster the creation of new forms of encryption, especially ultra-secure keys
  • ID Quantique
    • About ID Quantique
      • Based in Geneva, Switzerland
      • Founded: 2001
      • Offers consumers quantum key distribution (QKD)
        • Starting in 2004
    • QKD involves generating and transmitting an encryption key simultaneously
    • Use fiber optic cabling
    • Because measuring the quantum state of information affects it, this makes “eavesdropping” on a transmission practically impossible.
      • If someone tried to measure the photons traveling through the line, the customer would receive an error message, and no key would be created
    • The system is limited in terms of range
      • It only offers ranges of up to 62 miles
      • The company has achieved 155 miles in the lab
      • 248 miles is the theoretical limit for this method
    • An emitter-receiver pair costs $97,000
  • The Institute for Quantum Computing (IQC)
    • About IQC
      • Affiliated with University of Waterloo in Ontario, Canada
      • Founded: 2002
      • One of the few places in the world with a quantum key distributor (QKD)
    • About QKD
      • The pieces of the QKD are called “Alice” and “Bob”
        • Alice is a machine located at ICQ headquarters
        • Bob is a machine located at the nearby Perimeter Institute
    • Like IQ Quantique, the IDC’s QKD depends on the nature of entangled particles to ensure that no one can “listen in” on the sharing of an encryption key
    • First, a laser at the University of Waterloo creates entangled photons
      • Alice receives half of these photons
      • Bob receives the other half
    • Photons have a measurable quality called “polarization”
      • The polarization of any given photon will be random
    • If both sets of the device measure their photons, they will have the same polarization
    • By assigning 1 or 0 to a certain polarization, Bob and Alice can continue until their randomly generated key is long enough for their encryption
    • This method is highly secure because:
      • Any attempt to “listen in” on the signal will make itself known
      • There is no way to know what polarization the photons will have ahead of time
        • Thus, there is no way to “work backwards” and figure out the keys

Live by the quantum computer, die by the quantum computer? It certainly looks as though eventually, quantum computers will make traditional binary encryption obsolete. But this will happen at the same time that quantum computers create a whole new level of data security. And the encryption arms race will continue.

Sources: arstechnica.com, cacr.uwaterloo.ca, computer.howstuffworks.com, computerworld.com, dwavesys.com, idquantique.com, learncryptography.com, mathworld.wolfram.com, motherboard.vice.com, nature.com, news.ucsb.edu, pumpkinprogrammer.com, quora.com, sciencealert.com, scienceblogs.com, searchsecurity.com, technologyreview.com, tested.com, universetoday.com, uwaterloo.ca, washingtonpost.com, web.stanford.com, webopedia.com, whatis.techtarget.com, wired.com, youtube.com.

Sources

• Your Encryption Will Be Useless Against Hackers With Quantum Computers
• What Are Supercomputers Used For?
• What Makes a Supercomputer?
• Quantum Computing
• Qubit
• A Tale of Two Qubits How Quantum Computers Work
• Bits and Bytes
• Intro to Binary Numbers
• How Does a Quantum Computer Work?
• The Phosphorous Atom Quantum Computing Machine
• Quantum Computing 101
• Prime Factorization
• RSA Algorithm
• Diffie-Hellman Protocol
• Public Key Cryptography
• Why Is Factoring Numbers Into Primes a Difficult Problem
• What Is the Life Cycle of the Sun
• NSA Seeks to Build Quantum Computer That Could Crack Most Types of Encryption
• The Clock Is Ticking for Encryption
• Confused About the NSA’s Quantum Computing Project? This MIT Computer Scientist Can Explain
• D-Wave
• Your Encryption Will Be Useless Against Hackers With Quantum Computers
• Superconducting Qubit Array Points Way Quantum Computers
• The Man Who Will Build Google’s Elusive Quantum Computer
• Evidence for Quantum Annealing With More Than One Hundred Qubits
• Google Launches Effort to Build Its Own Quantum Computer
• Australian Researchers Have Created the Most Accurate Quantum Computing Technology
• ID Quantique
• The Case for Quantum Key Distribution (PDF)