Paper 2022/1277

Compact GF(2) systemizer and optimized constant-time hardware sorters for Key Generation in Classic McEliece

Yihong Zhu, Tsinghua University
Wenping Zhu, Tsinghua University
Chen Chen, Tsinghua University
Min Zhu, Wuxi Micro Innovation Integrated Circuit Design Co.Ltd
Zhengdong Li, Tsinghua University
Shaojun Wei, Tsinghua University
Leibo Liu, Tsinghua University

Classic McEliece is a code-based quantum-resistant public-key scheme characterized with relative high encapsulation/decapsulation speed and small cipher- texts, with an in-depth analysis on its security. However, slow key generation with large public key size make it hard for wider applications. Based on this observation, a high-throughput key generator in hardware, is proposed to accelerate the key generation in Classic McEliece based on algorithm-hardware co-design. Meanwhile the storage overhead caused by large-size keys is also minimized. First, compact large-size GF(2) Gauss elimination is presented by adopting naive processing array, singular matrix detection-based early abort, and memory-friendly scheduling strategy. Second, an optimized constant-time hardware sorter is proposed to support regular memory accesses with less comparators and storage. Third, algorithm-level pipeline is enabled for high-throughput processing, allowing for concurrent key generation based on decoupling between data access and computation.

Available format(s)
Publication info
Post-quantum cryptography McEliece high-throughput GF(2) Gauss elimination constant-time sorter · FP
Contact author(s)
zhuyihon18 @ mails tsinghua edu cn
2022-09-28: approved
2022-09-26: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Yihong Zhu and Wenping Zhu and Chen Chen and Min Zhu and Zhengdong Li and Shaojun Wei and Leibo Liu},
      title = {Compact GF(2) systemizer and optimized constant-time hardware sorters for Key Generation in Classic McEliece},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1277},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.