Practical machines for quantum-level computing are on the horizon. The immediacy of this technology raises a slew of questions when factored into a threat model. Some of these cannot be resolved without actual machines present; others are more general. For example, how can data at rest be protected when quantum machines can easily decode the cryptography?

The Post-Quantum Future is Near

To many organizations and professionals, post-quantum computing represents a chance to rebuild their systems from scratch. The causes for the restart may be specific to an enterprise’s reaction to quantum computing, but they are already showing up. The post-quantum cryptography (PQC) landscape is where we are all heading, whether we want to or not.

Highlighting these landscape changes, the U.S. government officially warned its agencies not to rely on standard encryption to be foolproof when analyzed in the future by a quantum-level computer. This is forcing government agencies to rethink how they secure their records.

PQC is sure to bring about many new challenges in the near future. Security professionals will be expected to deal with these challenges effectively in years to come, and the ripples from these changes will greatly affect all of enterprise computing.

Dawn of Quantum Computing

The Diffie–Hellman cryptography commonly used today is based on the mathematical difficulty of solving the discrete logarithm problem. With classical computing, it would take an enormous amount of time to calculate the solution to the problem.

In 1995, however, Peter W. Shor of MIT devised a way to factor the answers to the discrete log problem simply, greatly reducing the assumed computational difficulty. However, Shor’s method depended on the eventual construction of a then-unbuilt quantum computer. It took MIT another 20 years to come up with the requisite hardware, but they eventually got it.

Soon it will be possible to break Diffie–Hellman crypto, and cryptographers are already fighting back. Many efforts are underway to develop a quantum-resistant cryptosystem. This is a major challenge, however, given the speculative nature of quantum computing.

Quantum-Resistant Cryptography Coming Soon

An effective cryptosystem must be able to evolve as the PQC field advances. It’s too early in the development cycle to focus solely on one method of solving the problem. Instead, there are several potential options that could revamp the cryptography landscape.

SIDH Library

Microsoft is all-in on its new quantum-resistant crypto project. The SIDH Library solves many of the most pressing problems, including interoperability with legacy systems. It provides 128 bits of security against quantum cyberattacks and 192 bits of security against traditional attacks. In addition, SIDH Library features a “hybrid key exchange that combines supersingular isogeny Diffie–Hellman (SIDH) with a high-security classical elliptic curve Diffie–Hellman key exchange at a small overhead,” according to the official blog.

SIDH Library is “protected against timing and cache-timing attacks through regular, constant-time implementation of all operations on secret key material,” Microsoft continued. It also validates public keys in static key exchange when private keys are used multiple times. The system is supported on Windows and Linux and compatible with x86, x64 and ARM platforms.

Supersingular elliptic curves and the isogeny maps that exist between them make up the math providing the security for key exchange operations. Security is derived from the hardness of computing large-degree isogenies between two given elliptic curves. This is widely considered unfeasible at the moment, even for a quantum computer, but that may change over time.

While some crypto boffins have been known to kick the tires of this project, there is no consensus from the field on its operational characteristics. One such person described SIDH Library as “at least 300 times slower than curve25519” and advised not to use the library for anything serious yet.

BCNS Builds on SIDH

Researchers introduced another method, BCNS — named for its founders, Joppe W. Bos, Craig Costello, Michael Naehrig and Douglas Stebila — at the IEEE Security and Privacy 2015 conference. BCNS is notable for providing a seemingly quantum-resistant TLS security mechanism for OpenSSL. This method produces an ephemeral, secret key to encode the covered message traffic.

In the 2015 paper, “Post-Quantum Key Exchange — A New Hope,” the team of researchers proposed how to improve some performance parameters and extend the key exchange function of BCNS. The New Hope key-exchange protocol is based on the Ring Learning with Errors (RLWE) problem. The paper offers two different software implementations: a C reference implementation and an optimized software implementation targeting Intel Haswell processors.

According to the paper, the protocol more than doubles the security parameter for the same lattice dimension and halves the overhead communication. This speeds up computation by a factor of eight in portable C implementation and a factor of 27 in an optimized implementation targeting current Intel CPUs. These increases are achieved, the paper said, with comprehensive protection against timing attacks.

New Hope builds upon the lattice-based approach. “Even for the simplest tasks in asymmetric cryptography, namely public-key encryption, signatures and key exchange, lattice-based cryptography offers an important feature: resistance to all known quantum algorithms,” the paper said.

It’s important to remember that New Hope is a key-exchange, not authentication. The designers deliberately opted for an unauthenticated key-exchange protocol to address the most immediate of quantum problems. In their view, the protection of stored transcripts against future quantum decryption is more urgent than post-quantum authentication.

The researchers contend that it will soon be possible to achieve authentication using proven, pre-quantum signatures and hashes. They further posit that attacks on the signature will not compromise previous communications.

The designers intended to reduce the complexity of the protocol and simplify the choice of parameters. They see this as an advantage because it will decouple key exchange and authentication. There will be a choice available for the optimal algorithm for both tasks, such as an ideal lattice-based key exchange and a hash-based signature.

TESLA

Some of the same researchers were also involved in developing TESLA, a signature authentication protocol based on the lattice method. Other PQ signature methods have been developed, including BLISS and SPHINCS. SPHINCS is the only signature scheme that has been instantiated with quantum-hard parameters so far.

According to the paper, the public and secret keys of TESLA-768 are much larger than SPHINCS keys. However, TESLA-768 is significantly faster for signing and verification, and signatures are more than an order of magnitude smaller.

PQ signature methods are still undergoing rapid development. Right now, the bit security of TESLA depends on both the bit hardness of LWE and the security of the used hash function. There is much work yet to be done.

Challenges and Opportunities

As of now, New Hope seems to be the most reliable method for in-transit document protection, if only because it uses well-examined, longstanding concepts.

A long-term problem remains, however: Methods will have to change and evolve. Picking one way to do things now without the ability to modify it at a later date can only be problematic. Underlying assumptions will vary as practical quantum computers arrive and quantum-flavored zero-day exploits emerge.

The PQC world isn’t going to be easy. Security professionals will have their work cut out for them. At the same time, quantum computing will present enormous groundbreaking opportunities: It may well cause the greatest software refresh cycle in the history of enterprise computing.