Google, one of the front runners in the race for quantum computing, announced their first experiments with post-quantum cryptography.
Why does it matter? If Google is starting to worry about post-quantum cryptography, maybe they had a breakthrough in large scale universal quantum computing?
See the original blog post here: https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html
Google’s Post-quantum cryptography experiment
It’s time to explore options for quantum safe algorithms beyond theoretical implementations. Google has launched “CECPQ1” - a post-quantum key exchange algorithm on top of the standard ECC algorithm - live on Google Canary!
Research began with the “New Hope” algorithm developed by Alkim, Ducas, Pöppelmann, and Schwabe, building upon’s Microsoft’s work by Bos, Costello, Naehrig, and Stebila. Bos et al implemented the lattice-based "Ring-Learning-With-Errors"(R-LWE) into the TLS protocol. The thorough paper covers implementation and integration into TLS, as well as performance tests. The later “New Hope” paper focuses on optimizing and building upon the previous work, speeding up computation by 10x or more. All this demonstrates that post-quantum cryptography is practical at this time.
Google’s experiment focuses on a LWE-based key exchange (LWE being a less specialized problem than R-LWE) in their implementation. While LWE uses much larger key sizes, Google chose it based on potential security concerns of the R-LWE structure. Though this algorithm is slower than ECDH, and nearly an order of magnitude slower than R-LWE (New Hope), it’s now officially in use!
Post-quantum cryptography standards
Google does not intend for this particular algorithm to be the end-all standard for post-quantum cryptography. Retiring RSA and ECC is necessary; however, these are not the only options for post-quantum cryptography. While there are conferences focused on the new cryptography standards and algorithm exploration, quantum computers and even the quantum “mindset” hasn’t been around long enough to have thoroughly exhausted all potential attacks or algorithms.
Transitioning to new standards will be its own headache. With query complexity breakthroughs even in key quantum algorithms, these recommendations are just initial experiments. The key is to have easily upgrade-able systems, without painful transition costs.
Here's additional results as of Sept 9, 2016 from the Google experiments: PDF