Post-Quantum Encryption

Recently I’ve been digging into the future of quantum computers and the computer scientists who are already fighting (and denying) them.

A quantum computer uses the concept made famous by Schrödinger’s Cat, superposition, to simultaneously store a one and a zero in each of its bits. In a true quantum computer, each of these so-called qubits would be entangled, so three qubits simultaneously represent the eight binary numbers from 000 to 111. As you add more qubits, this becomes more powerful but also more difficult to maintain. If you do get it working, though, it’s been proven that a true quantum computer would solve certain problems (BQP) which are difficult for us today, but are more easily solvable by quantum algorithms. This is when security and privacy people start getting involved — according to Shor’s Algorithm, the most popular encryption algorithms today will be especially vulnerable.

Current experiments take place in labs near absolute zero, and their qubits are only readable for short periods of time, so some credible researchers believe that a practical quantum computer will never exist. But if you use sensitive communication today, you can’t risk having people intercept the data today and decrypt it in the future. Google recently started experimenting with including a post-quantum algorithm in SSL/TLS (encryption between web browser and servers). The NSA (which is working on its own quantum computer) has advised NIST to start preparing for new standards in encryption algorithms. So it’s a good time to take a deep dive into cryptography.

‘Post-quantum encryption’ covers a variety of algorithms which are believed to be secure both to classical and quantum computers. Almost everything that I know about this is from the Wikipedia page, pqcrypto.org, and the book Post-Quantum Cryptography (2009), which divide the field into four broad categories:

  • hash-based (encrypting messages with a digital signature and including the key for the next message)
  • code-based (adding errors to the message which the receiver will know how to remove using binary Goppa code)
  • lattice-based (based on a vector field)
  • multivariate quadratic equations

Each option relies on the programmer including certain parameters, and over time cryptographers are discovering new vulnerabilities and making recommendations. For example, a paper in 2008 recommended quadrupling the length of a key in the McEliece cryptosystem (code-based cryptography). With RSA and other integer-factorization algorithms dominating the market today, one fear is that researchers and programmers haven’t spent enough time to develop new tools and test their security. To compete in today’s market, programmers might simplify their tools and inadvertently weaken their protection from quantum computers.

The leading option today appears to be lattice-based cryptography, especially ring learning with errors. This is the system which Google is experimenting with in their ‘A New Hope’ test. Lattice-based crypto is receiving new interest and ring learning has just come about in the past few years, so Google is hedging their bets by combining it with a classical algorithm in their test.

Practically speaking, it might be better for Google to rearrange existing encryption ciphers in Chrome. AES-128 and AES-256 are two common algorithms today which use integer factorization. On a quantum computer, AES-256 would drop down to be as secure as AES-128 is today, and AES-128 would be unacceptably insecure. If you visit howsmyssl.com and scroll down, you’ll see that Chrome supports both but prefers AES-128. A smaller key size saves time for the server and browser, but my iPad prefers AES-256, and I don’t have any difficulty browsing the web that way. (update: I’ve been informed that AES-256 is good, but it still relies on an initial key exchange which is vulnerable, so ‘A New Hope’ would help out a lot).

One exciting benefit of lattice-based cryptography is that it can be used for fully homomorphic encryption. The concept is that a number or message can be encrypted by Alice, sent to Bob for some arithmetic operations, and returned to Alice without Bob seeing the unencrypted value. A simple example given was a currency exchange where Alice doesn’t want Bob to know how much money she’s converting. A more complex example would be a secure voting system which has reproducible vote totals.
Coming from the mapping industry, I wondered if this would be useful for geo-fencing and other situations where your location is important, but you don’t want to share your precise coordinates. I used a partially-homomorphic Paillier cryptosystem (not lattice actually) to write a Python server and simple webpage to create a ‘crypto geofence’.