PIs: Bo-Yin Yang, Kai-Min Chung, Bow-Yaw Wang, and Ruben Niederhagen
Quantum computing is a promising upcoming technology that has the potential for disruptive changes to our modern society in many fields. One of the negative changes of quantum computing that we need to be prepared for however is its devastating impact on today's cryptography: An attacker equipped with a large and powerful quantum computer will be able to break crucial cryptography that is in use today all around the world.
Therefore, since 2017, the National Institute of Standards and Technology (NIST) in the USA has been in a public process of standardizing a new generation of cryptographic algorithms that protect against future attacks aided by large quantum computers. This new generation of cryptography is called Post-Quantum Cryptography (PQC). Our team has been involved in this process by contributing to the four submissions Classic McEliece, Gui, NTRU Prime, Rainbow, and SPHINCS+. At the end of the third round of the standardization process in 2022, NIST selected one key-establishment algorithm (CRYSTALS-Kyber) and three signature algorithms (CRYSTALS-Dilithium, Falcon, and our submission SPHINCS+) for standardization and promoted four alternative key-establishment algorithms into a fourth round. Three of these algorithms, among which is our submission Classic McEliece, are still under consideration.
To further diversify the field of signature algorithms, NIST provided an on-ramp of new signature algorithm proposals in June 2023. We are participating in this on-ramp by contributing to the three schemes MEDS, UOV, and WAVE. The signature scheme UOV is based on the hardness of the MP problem (the solving of multivariate polynomial systems) and is a very promising candidate with a long cryptographic tradition and well-understood security features. The schemes WAVE and MEDS broadly belong to the family of code-based schemes and are much younger. However, they provide attractive features like small public key sizes and efficient signing operations. We are the main implementer of MEDS and UOV and contribute to the implementation of WAVE.
We are planning to continue our contributions to the NIST PQC standardization processes with our contributions to these three schemes. Furthermore, we are planning to work on efficient, secure, and verified implementations in software and hardware as well as software-hardware co-designs of other schemes considered by NIST and in the PQC community. Our work spans the entire ecosystem of cryptography, starting with the design, cryptanalysis, and verification of schemes over the implementation and optimization to the security analysis and hardening of implementations and their integration into protocols and IT systems.
This project has several papers published in IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES). For example, alone in 2022, we contributed five articles to TCHES. IACR TCHES is widely considered the best publication venue for cryptographic implementation and applied cryptography, and our publications include verifiable fast implementations in cooperation with the world-leading IIS formal methods group.
Post-Quantum Algorithm Implementation
The lattice-based family of PQC systems has the reputation of being particularly efficient both in computational cost as well as in key and cipher text respective signature sizes. The main operation structure of lattice-based schemes is a polynomial ring and the most time-consuming operations on polynomial rings are multiplication and division. We have significantly contributed to the development of fast implementations of these operations and we were the pioneers to use the Number Theoretic Transformation (NTT, related to the Fast Fourier Transformation - FFT) to compute multiplications on polynomial rings not designed for NTT on various embedded ARM CPUs. The main implementation techniques cover complete and incomplete FTTs (or NTTs, with Cooley-Tukey and Gentleman-Sande butterflies), Good-Thomas FFT, Rader's FFT, Schönhage-Strassen FFT, and Nussbaumer FFT.
The code-based family of PQC schemes is in general more expensive regarding computational cost or key and data sizes. However, while more recent proposals exist, the field itself goes back to the late 70s, and therefore early, well-vetted code-based schemes are regarded as very secure and reliable. We have been contributing to the efficient implementation of code-based schemes in hardware and software and we have been looking into the side-channel security of these schemes: For the use of cryptography, efficiency and theoretical strength are not sufficient – schemes also need to be implemented securely such that an attacker cannot derive secret information from side channels such as timing behavior, power consumption, and electromagnetic radiation.
The family of multivariate PQC schemes such as UOV provides remarkably short signatures and efficient verification time – but often public keys are considerably large. While many schemes of this family have suffered severe cryptanalysis in the past, UOV is considered very reliable and durable and this scheme is widely considered the front-runner of the NIST PQC signature scheme on-ramp. With the submission of the UOV scheme, we are providing optimized implementations for various platforms, including x86 CPUs, embedded ARM implementations, and an FPGA hardware design. Besides this design and implementation work on the UOV submission, we have been contributing to the assessment of the underlying hard problem of solving multivariate polynomial systems for many years and we are holding several public records of solving such systems on computer- and FPGA-cluster architectures.
The family of hash-based PQC schemes does not provide encryption schemes but only signature schemes. Our submission SPHINCS+ culminates the best-known practices of a long period of research. While having very small public keys, hash-based signature schemes have large signature sizes. They come in two variants – stateful schemes such as XMSS and LMS that have been in broader use already for a while and their stateless counterparts such as SPHINCS+. Due to the relatively high cost of key generation and signing, we have conducted research on how to implement these schemes efficiently in memory-restricted embedded devices and how to improve their performance using hardware accelerators.
NIST PQC On-Ramp Contributions
UOV: Most of the work for the implementation of the Unbalanced Oil and Vinegar (UOV) signature scheme has been performed in Taiwan. For the ARM Cortex-M4 and Intel/AMD x86-64 implementations, we generalized and reused our earlier work on the related PQC scheme Rainbow. We provided new implementations for ARM Neon and an FPGA platform.
MEDS: The Matrix Equivalence Digital Signature (MEDS) signature scheme is based on a Fiat-Shamir construction and only requires relatively simple operations on matrices such as multiplication, inversion, and Gaussian elimination. For the reference implementation of the scheme, we implemented all operations in a straightforward, timing-secure manner. The next steps now are to provide an optimized implementation for SIMD CPUs and a hardware implementation of the scheme.
WAVE: The WAVE submission is a code-based hash-and-sign signature scheme. The signer needs to perform the hard task of solving the decoding problem with the aid of some secret knowledge. WAVE has very short signatures – but very large public keys. Currently, there is only a reference implementation of WAVE and we are going to contribute to optimized implementations on various platforms.
Verified Post-Quantum Cryptography
Our research group is the first to investigate the formal verification of the NTT components of post-quantum cryptography in collaboration with the Program Center for Formal Verification. We are promoting and enhancing the CryptoLine tool chain, which is a set of tools and mechanisms for handling arithmetic and logic verification problems using SAT and algebraic solvers as well as CAS (computer algebra system) respectively.
With our work, we contribute to the research and development of verified, efficient, and secure implementations of PQC schemes and hence to a secure digital communication of the future.