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

Yihong Zhu; Wenping Zhu; Chen Chen; Min Zhu; Zhengdong Li; Shaojun Wei; Leibo Liu

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Post-quantum cryptography McEliece high-throughput GF(2) Gauss elimination constant-time sorter · FP
Contact author(s): zhuyihon18 @ mails tsinghua edu cn
History: 2022-09-28: approved; 2022-09-26: received; See all versions
Short URL: https://ia.cr/2022/1277
License: CC BY-NC

BibTeX

@misc{cryptoeprint:2022/1277,
      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},
      url = {https://eprint.iacr.org/2022/1277}
}