Erstmalige FPGA-Implementierung des Falcon Post-Quantum-Kryptografischen Signatur Algorithmus

21.03.2023

Eine Masterarbeit am IMES zeigt die weltweit erste vollständige Implementierung von Falcon auf einem FPGA.

Quantum
Quantum

Das National Institute of Standards and Technology  der Vereinigten Staaten von Amerika (NIST) begann den Prozess der Post-Quantum-Kryptographie-Standardisierungsprozesses im Jahr 2017. Die ersten Algorithmen werden im Juli 2022 für die Standardisierung ausgewählt.  Die FGPA-Hardwarebeschleunigung wurden für alle Algorithmen ausser Falcon durchgeführt. Eine Masterarbeit am IMES zeigt die weltweit erste vollständige Implementierung von Falcon auf einem FPGA.

Einführung

In den letzten zehn Jahren wurde viel Forschung zum Thema der Quantencomputern betrieben. Theoretisch könnten diese Quantencomputer die meisten der herkömmlichen Krypto-Systeme knacken. Dies würde die Vertraulichkeit und Integrität in jeder Form der digitalen Kommunikation gefährden. Post-Quantum-Kryptographie befasst sich mit kryptographischen Algorithmen, die resistent gegen Angriffe von sowohl Quanten- als auch für konventionelle Computer sind. Kleine Quantencomputer existieren bereits in einem nicht-kommerziellen Forschungsumfeld, aber um Krypto-Systeme erfolgreich anzugreifen, müssten noch viel größere Quantencomputer realisiert werden. Selbst wenn ihr Erscheinen sicher ist, ist es schwierig vorherzusagen, wann genau solche Quantencomputer zur Verfügung stehen werden.

Vorgehen

Für die Implementierung von Falcon wurde die High Level Synthesis (HLS) gegenüber einer traditionellen Hardware-Beschreibungssprache wie Verilog oder VHDL vorgezogen. Die Referenzimplementierung des Algorithmus wurde in der Programmiersprache C geschrieben. HLS nimmt C-Code und übersetzt ihn in eine Register Transfer Level (RTL) Hardware-Beschreibung, daher kann die Referenzimplementierung direkt in der HLS verwendet werden. Viele kleinere Änderungen am Code mussten vorgenommen werden, um die mit der HLS kompatibel zu sein. Die grössten und offensichtlichsten Änderungen waren das Umschreiben aller rekursiven Funktionen in eine iterative Version.

Fazit

Alle wichtigen Teile des Falcon Algorithmus konnten auf einem FPGA implementiert werden. Soweit es uns bekannt ist, wurde die Schlüsselgenerierung Schlüssel- und Signaturgenerierung zum ersten Mal auf einem auf einem FPGA implementiert. Weitere Optimierungen sind notwendig, um sowohl die Hardwareauslastung und Leistung zu verbessern.

Abstract