Paper 2022/928

Universal Gaussian Elimination Hardware for Cryptographic Purposes

Jingwei Hu, Nanyang Technological University
Wen Wang, Yale University
Kris Gaj, George Mason University
Donglong Chen, BNU-HKBU United International College
Huaxiong Wang, Nanyang Technological University

In this paper, we investigate the possibility of performing Gaussian elimination for arbitrary binary matrices on hardware. In particular, we presented a generic approach for hardware-based Gaussian elimination, which is able to process both non-singular and singular matrices. Previous works on hardware-based Gaussian elimination can only process non-singular ones. However, a plethora of cryptosystems, for instance, quantum-safe key encapsulation mechanisms based on rank-metric codes, ROLLO and RQC, which are among NIST post-quantum cryptography standardization round-2 candidates, require performing Gaussian elimination for random matrices regardless of the singularity. We accordingly implemented an optimized and parameterized Gaussian eliminator for (singular) matrices over binary fields, making the intense computation of linear algebra feasible and efficient on hardware. To the best of our knowledge, this work solves for the first time eliminating a singular matrix on reconfigurable hardware and also describes the a generic hardware architecture for rank-code based cryptographic schemes. The experimental results suggest hardware-based Gaussian elimination can be done in linear time regardless of the matrix type.

Available format(s)
Publication info
Code based Cryptography Rank-Metric Codes ROLLO Gaussian Elimination
Contact author(s)
davidhu @ ntu edu sg
wen wang ww349 @ yale edu
kgaj @ gmu edu
donglongchen @ uic edu cn
hxwang @ ntu edu sg
2022-07-18: approved
2022-07-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jingwei Hu and Wen Wang and Kris Gaj and Donglong Chen and Huaxiong Wang},
      title = {Universal Gaussian Elimination Hardware for Cryptographic Purposes},
      howpublished = {Cryptology ePrint Archive, Paper 2022/928},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.