Post-Quantum Cryptography: Protecting Today from Tomorrow

The race is on worldwide between data privacy and those criminal and state-sponsored hackers wishing to extirpate the protection of secrets—personal, governmental, and industrial. The threat comes from an ability to crack today's public-key encryption using future quantum computers.

Back in 1994, ACM Fellow Peter Shor published the seminal algorithm showing how to break public-key encryption standards, albeit only for future quantum computers. Since then, nation-states have been archiving encrypted information, awaiting the day when commercial quantum computers will be able to decrypt it.

Fortunately, it is possible to craft more difficult algorithms to protect secrets so they are resilient to future quantum computers, creating, in effect, post-quantum cryptography.

Post-quantum cryptography uses today's conventional computers to run more secure encryption algorithms. In 1996, Miklós Ajtai described a lattice cryptographic algorithm whose security was ensured by the NP-Hardness (non-deterministic polynomial-time hardness) of finding a decryption key.

Since then, many such algorithms whose solutions are resilient to future quantum computers have been created, but almost no one uses them—except deep-pocketed government agencies like the National Security Agency (NSA), which can afford to build custom accelerators. The rest of the world is waiting for post-quantum cryptography to be officially standardized, because without standards, the necessary hardware accelerators are too expensive to mass-produce (so far, post-quantum cryptographic algorithms are economically forbidding without hardware acceleration).

Software-only experiments with post-quantum cryptography have been performed by Google (using a cryptography library called New Hope) and Microsoft (LatticeCrypto), but neither have seen widespread usage.

Now, Germany's Technical University of Munich (TUM) and the Massachusetts Institute of Technology (MIT) have broken the ice by crafting hardware accelerators that work with the post-quantum cryptography algorithms most likely to be standardized. The hope is to pave the way to adoption and commercialization of post-quantum cryptography as early as next year, when the first standards are expected to be announced by the National Institute of Standards and Technology (NIST).

Said Georg Sigl, a professor of Security in Information Technology in the department of Electrical and Computer Engineering at TUM, "There are several groups working on post-quantum crypto accelerators. I know of only one chip which has been developed so far, at MIT, but MIT's contains only a hardware accelerator developed without the integration of hardware/software co-design, as does ours. Therefore, [I believe] TUM's is more flexible."

Mathmatician Dustin Moody, a lead for NIST's post-quantum computer team, said he did not favor one chip over the other, but confirmed that he, too, knows of only the TUM and MIT prototype chips.

NIST fast-tracked a Post-Quantum Cryptography Standardization Process beginning in 2017 with 69 candidate algorithms, which have been narrowed down to seven finalists.

"We are nearing the end of the third round of evaluation and analysis," said Moody. "This involves seven finalists including Kyber [and McEliece, NTRU—Number Theorists R Us , and Saber, plus three digital-signature finalists], as well as eight alternates. We have included schemes for both public-key encryption, key encapsulation, as well as public-key digital signatures. We expect to name the algorithms we will standardize roughly by the end of this year [2021]."

The winning algorithms (one focused on encryption/decryption, the other on digital signatures) will be offered up as the U.S. standards. That will leave four to nine years to complete the typical standardization process—including public reviews—before the dawn of the first crypto-cracking quantum computers predicted by NIST to occur circa 2025-2030.

According to Moody, this effort is at the core of NIST's charter to "promote U.S. innovation and industrial competitiveness by advancing measurement science, standards, and technology in ways that enhance economic security and improve our quality of life."

"From the beginning, the motivation has been the threat that large-scale quantum computers could threaten public-key crypto-systems. NIST has taken the threat seriously and has been responding [with its Post-Quantum Cryptography Standardization Process]," said Moody.

Once standards are in place, all the major chip makers will enter the fray, but they will have the advantage of having the TUM and MIT prototypes from which to start their designs.

TUM's prototype chip is more complicated than MIT's, because TUM also wanted to test whether post-quantum cryptography could find hidden Trojan Horses that would allow either a nation-state in which the chip was manufactured, or criminals selling counterfeits, to bypass its security implementation with embedded malware. The two efforts were headed by TUM's Sigl (for the post-quantum encryption) and TUM chair for security in information technology Johanna Baehr (for hiding four hardware Trojan Horses), and both were implemented on a single application specific integrated circuit (ASIC) chip developed in Sigl's lab.

TUM's prototype chip contains basically two independent parts, one focused on post-quantum cryptography, the other on hardware Trojan Horse detection. A paper presented at this year's ACM International Conference on Computing Frontiers (CF 2021) described the chip's tape-out of hidden Trojan Horses, which has since been successfully fabricated into TUM's prototype chip.

The researchers report that when running post-quantum cryptography from Kyber (one of the top finalists in NIST's standardization effort), their accelerators run code 10 times faster than when using software alone. Likewise, the Super-singular Isogeny Key-Encapsulation (SIKE) algorithm—one of the alternative NIST finalists—helps the software run over 20 times faster than when using software alone.

Both post-quantum cyphers are accelerated by the chip's finite-field accelerator. Implementation of the finite-field accelerator was built by TUM into a RISC-V core (described in an earlier paper at the ACM International Conference on Computer-Aided Design). TUM also supplemented an ARM A-9 core with a finite-field accelerator as a proof of concept. In both cases, the hardware/software co-design used these specialized hardware components and control software to complement one another. The researchers report their co-design approach used just one-eighth the power than if implemented in software alone running on an unaccelerated core.

Baehr reports that four types of hardware Trojan Horses were successfully hidden within TUM's quantum-resistant encryption chip: Denial of Service (causing intermittent stalls), Number Theoretic Transform (manipulates instruction counter), Hardware Leak (which breaks hardware loops), and LEAK (enabling side-channel information leaks). Together with the Sigl team, Baehr plans to reverse-engineer the chip's functions by destructively shaving off the circuit pathways incrementally, photographing each successive layer, and reconstructing the precise functions performed using machine learning, in the hope this will aid future post-quantum accelerator chips in detecting hidden Trojan Horses.

The MIT researchers, supported by Texas Instruments and the Taiwan Semiconductor Manufacturing Company (TSMC), have also developed a low-power Internet of Things (IoT) prototype chip aimed at proving the feasibility of using post-quantum cryptography with battery-powered Internet of Things devices.

According to a paper they presented at ACM/IEEE's International Solid-State Circuits Conference two years ago (ISSCC 2019), 80% of the power consumption of lattice-based post quantum cryptography, such as that used by Kyber, supports the creation of sufficiently random numbers to shield its operation from hackers.

To produce these random numbers within the power budget of Internet of Things devices, MIT designed a two-millimeter-square chip running a Number Theoretic Transform (NTT). NTTs work like a Fourier transform, which decomposes inputs into multiple frequencies allocated over four single-port memory devices that occupy a third less total area than the multi-port memories traditionally used, thus satisfying the requirement for an Internet of Things device of a small die area.

R. Colin Johnson is a Kyoto Prize Fellow who ​​has worked as a technology journalist ​for two decades.