Fortanix Post-Quantum Cryptography Solution

Quantum Computers and Cryptography

The most common cryptographic primitives used today are AES, RSA, DSA, ECDSA, DH, ECDH, and SHA-2. These primitives are standardized by various entities like NIST, IETF, BSI, and ISO and are considered secure against attacks from the most powerful computers.

Modern cryptographic systems are designed so that attacking them is out of reach even assuming future exponential increases in computing power continue far into the future. Using a simple thermodynamic argument it is possible to show that even if the entire energy output of the sun was utilized to power a brute force attack on a single 256-bit AES key, such an attack would most likely take billions of years to complete. Widely used public key cryptography systems such as RSA and ECDSA rely on the hardness of the integer-factorization and discrete-logarithm problems. The best algorithms for these problems can break only small instances, and only when run on massive supercomputers.

Quantum computers fundamentally change the computing landscape for these problems. The infinitely large space of superposition states during computation and the entanglement of qubits solve these integer-factorization and discrete-logarithm problems much faster. A quantum computer running Shor’s algorithm is capable of solving both of these problems exponentially faster than on conventional computers. In response cryptographers have studied new problems on which public key cryptography can be based.

Ciphers such as AES can also be attacked using a quantum computer, but the speedups are only quadratic and not exponential; Shor’s algorithm cannot be used. As a result, 128-bit AES key might theoretically be attackable using a quantum computer, but a 256-bit AES key should remain secure indefinitely.

Post-Quantum Algorithms

To prepare for the eventual advent of quantum computers, security professionals are discussing multiple families of post-quantum cryptography schemes. The National Institute of Standards and Technology (NIST) is leading a Post Quantum Cryptography Standardization project to identify the best cryptography schemes. Currently, there are multiple candidate families, including Code-based, Lattice-based, and Hash-based schemes. Each of these schemes are based on mathematical problems that are very hard to solve, not only for traditional computers, but also for quantum computers.

CODE-BASED: Based on public-key encryption and the use of error-correcting codes to hide the contents of a message during transmission. Decoding this random linear code is computationally hard, depending on the code parameters. Code-based cryptography was originally invented in 1978 and has been intensively studied especially in recent years as the post-quantum secure properties of the algorithm became appreciated. Leda is a candidate algorithm in the 2nd round of the NIST Post Quantum Cryptography Standardization project.

LATTICE-BASED: Based on public-key encryption, the computationally hard problem for this cryptography is trying to find the shortest vector in a high-dimensional lattice. Round5 is a candidate algorithm in the 2nd round of the NIST Post Quantum Cryptography Standardization project.

HASH-BASED: Hash functions are one-way functions that map bit strings of an arbitrary length to short, fixed-length strings called hash values. LMS (RFC 8554) is a hash-based signature scheme which is in the process of getting approved by NIST (SP 800-208). LMS’s hardness is based on the difficulty of creating a collision for SHA-256, which is estimated to provide 128-bit security. With the parameters chosen by Fortanix, it offers very short public keys (under 64 bytes) and signatures of approximately 3 KB. One limitation of LMS is that it is stateful, which means a given public key can only be used to produce a specific number of signatures. With the parameters in use, around 33.5 million (specifically 2**25) signatures can be generated, after which the key is not able to generate further signatures. In addition, key generation is very slow (on the order of several minutes). For these reasons it is ill-suited for high volume transactions like TLS server authentication. However, its fast, simple verification algorithm and high security make it ideal for applications such as signing firmware updates.

"Crypto Agility is a must in the post-Quantum world of tomorrow."

Quantum computers are actively being researched. However, given that most product life cycles are 7-10+ years, companies are looking to ensure that the security solutions used today support post-quantum cryptography algorithms currently being reviewed by NIST. Given the length of time for an algorithm to be fully NIST certified, it’s much better to be flexible, to quickly support any algorithm NIST finally approves, when the time comes.

And now the dilemma. How can a security professional choose the right post-quantum solution today, to thwart an attack that may take place a decade from now?

The two-part answer is:

1. Choose a solution that incorporates one or more of the post-quantum algorithm schemes listed herein
2. Make sure the solution you choose is flexible enough to incorporate future post-quantum algorithms when/if they become available.

At Fortanix, we support all the post-quantum algorithms discussed herein and with our flexible architecture can easily accommodate any future post-quantum algorithms as well. Our subscription-based pricing means your products are always refreshed with the latest software.

Recommendation

Consider Post-Quantum Cryptography for specific projects:

• Organizations with super sensitive data and products that need protection from Quantum Computers capabilities that may be available but not publicly announced should using PQC.
• Products that have longer life-cycle and are not typically updated in the field should consider using PQC during the time of manufacturing itself. For example, IOT (both consumer and industrial) devices, personal medical devices, and smart utility devices should be equipped with PQC today.
• Products that have long design and manufacturing cycle should adopt PQC today so that when they are productized, they can withstand the state of the art crypto-attacks.
• Research labs and innovation groups looking to understand deeper implication of using PQC in various toolchains and products.

You can contact us at info@fortanix.com or ask your sales representative for access to our online POC environment.

A Brief Primer on Quantum Computing

What’s all the hype?

Quantum Computers allow us to do useful computation on particles at quantum level. Just like we write programs for traditional computers Quantum Computers also work with programs. For traditional computers, the programs are compiled into binaries that eventually result into currents flowing and voltages flipping at the inputs of silicon transistors. The outputs of the transistors are sampled and finally interpreted as the output of the program. On Quantum Computers, there are qubits (short for quantum bits) that hold some information, and ways to influence their behaviors. This influence is provided in the form of quantum inference and is equivalent to us running the compiled programs on traditional computers.

Qubits

Think of qubit as a spinning sphere with half of it pained black and the other half white. When you stop it and see the face near you, the color you see depends on the time at which the sphere was stopped and its speed. Similarly, a qubit can hold two states – 1 and 0 – but the value at the time of sampling is determined by its wave function. To be a useful, a quantum computer needs qubits that can keep spinning for long time, meaning the qubits have non-zero probability of getting sampled either way.

Quantum Supremacy

Since we know how qubits behave and all the equations for quantum interference, why cannot we simply simulate them on traditional computers and get all the benefits? It actually works well for small number of qubits but at some point computations become too hard to do on traditional computers. Quantum supremacy refers to this inflection point – where there exists at least one program which will run faster on a real quantum computer than the equivalent program on a simulated quantum computer on a traditional computer. Google was the first company to claim quantum supremacy in 2019, with 53 qubits.

Quantum Computing Is Now a Reality

While we are in the early days of quantum computing, the improvement continues at incredible pace, with companies exploring everything from super-conductors to light-based approach. The power of quantum computers increases exponentially with the number of qubits and additionally, new quantum algorithms are making drastic improvements, even with the limited number of qubits.

Shor’s Algorithm: Encryption’s nemesis

We are still developing a theory to understand quantum computing and there are open questions on what types of problems would be best suited for quantum computers. However, specific algorithms have been developed that perform much better on quantum computers than on traditional computers. Shor’s Algorithm is one such example. Unfortunately, most of public key cryptography relies on number factorization or discrete logarithm problem being hard, both seriously impacted by Shor’s Algorithm running on a Quantum Computer. So, given enough qubits, public key cryptography would be broken, prompting the National Institute of Standards and Technology (NIST) to start a process for building new types of public key cryptography that would be secure in the world of quantum computers.