Accelerating the Classic McEliece Post-quantum Cryptosystem using the RISC-V Vector Extension

Abstract

Skalierbare Quantencomputersysteme sind nur noch eine Frage der Zeit, wann diese großräumig eingesetzt werden. Man weiß noch nicht, was mit dieser Technologie alles möglich ist, jedoch ist bekannt, dass die derzeitigen kryptographischen Systeme unsicher werden. Die derzeitigen asymmetrischen Kryptographie-Algorithmen, basierend auf RSA, Diffie-Hellman oder Elliptische-Kurven, können mit Shor’s Algorithmus in polynomieller Zeit gebrochen werden. Um dies vorzubeugen, werden neue sogenannte Post-Quanten-Kryptographie (PQC) Systeme entwickelt. Das PQC Verfahren Classic McEliece, welches auf fehlerkorrigierenden Codes aufbaut, wurde von der National Institute of Standards and Technology (NIST) und der Internationalen Organisation für Normung (ISO) als langfristige quantenresistente Lösung anerkannt. Um mit der erwarteten Leistung von modernen Computersystemen mitzuhalten, muss dieser Algorithmus verbessert werden. Ein üblicher Weg dafür ist ein Hardware-Beschleuniger, jedoch wird in dieser Arbeit die Methode von spezialisierten Instruktionen angewendet. Dieser Ansatz hat eine bessere Effizienz bezüglich der Chip-Fläche und der Leistung, was bei eingebetteten Systemen wichtig ist. Die Open-Source Befehlssatzarchitektur RISC-V mit ihrer Vektor Erweiterung wird als Grundlage dafür hergenommen. Die Verschlüsselungs- und Entschlüsselungsoperationen von Classic McEliece wurden untersucht und die Syndrome Funktion und die GF(2) Multiplikation wurden als Laufzeitengpass identifiziert. Zuerst wurden beide Funktionen mit den RISC-V kryptographischen Vektor-Erweiterungen verbessert. Jedoch sind diese Instruktionen nicht optimal für Classic McEliese, weswegen neue maßgeschneiderte Vektor-Instructionen erstellt wurden. Diese verschiedenen Implementierungen der Funktionen wurden auf dem RISC-V Vektorprozessor Vicuna simuliert und deren Beschleunigung gegenüber dessen originalen Funktionen bestimmt. In Experimenten stellte es sich heraus, dass die existierenden RISC-V Vektor-Erweiterungen eine Beschleunigung von 3,5 für die Syndrome Funktion und 3 für die GF(2) Multiplikation schaffen. Hingegen erreichen die neu erstellten Vektor-Instruktionen sogar jeweils eine Beschleunigung von 4,3 und 14,7. Darüber hinaus brauchen sie in der Hardwareimplementierung auf dem Vicuna Prozessor 60% weniger Ressourcen als die RISC-V kryptographischen Vektor-Erweiterungen.

The introduction of large-scale quantum computing is on the horizon. The full extent of this new computational power is far from known. However, one thing that is sure with this new technology is the threat to the current cryptographic systems. All the current Public-Key Cryptosystems (PKEs) based on RSA, Diffie-Hellman or elliptic curves can be broken in polynomial time with Shor's algorithm. Therefore, new quantum-resilient cryptosystems called Post-Quantum Cryptography (PQC) are being developed and implemented. The code-based PQC Classic McEliece is one of the new systems, which was recognised by the National Institute of Standards and Technology (NIST) and the International Organization for Standardization (ISO) to be a great contender for long-term quantum security. However, to introduce it into modern systems, the Classic McEliece needs to be improved to keep up with the performance requirements expected from cryptosystems. This thesis will try to achieve that using specialized instructions instead of the conventional hardware accelerator. This approach has much better chip area and power efficiency, which is essential in embedded applications. As the Instruction Set Architecture (ISA) basis, the open-source standard RISC-V is used in combination with its vector extension. The PKE operations Encryption and Decryption were profiled and it was discovered that the syndrome function and the GF(2) multiplication were the main bottle-neck, respectively. Both functions were first vectorized with the existing RISC-V cryptography vector extensions and then new custom vector instructions were proposed, which either fixed limitations or significantly improved performance of the previous implementations. The different implementations were simulated on the hardware implementation of the RISC-V vector core Vicuna to determine their speed-up compared to their respective base implementation. The experiments showed that the implementations with the existing RISC-V vector cryptography extensions can reach a speed-up of up to 3.5/3 for the syndrome function/GF(2) multiplication, respectively. However, the implementations with the new custom vector instructions can achieve a speed-up of up to 4.3/14.7 with the same configurations. Moreover, when implemented on the Vicuna core, the new custom instructions require on average 60% less area overhead than the RISC-V vector cryptography extensions.