Toward Practical Code-Based Signature: Implementing Fast and Compact QC-LDGM Signature Scheme on Embedded Hardware

In this paper, fast and compact implementations for code-based signature are presented. Existing designs are either using enormous memory storage or suffering from slow issuing speed of signatures. A vastly optimized new design solving these problems is proposed by exploiting quasi-cyclic low-density generator matrix codes at different levels. In particular, this paper provides a new algorithmic enhancement of signature generation and gives detailed and optimized solutions for critical steps of this algorithm. The design presented in this paper is the fastest implementation of code-based signatures in open literature. It is shown, for instance, that our implementation of signature generation engine can generate approximately 60,000 signatures per second on a Xilinx Virtex-6 FPGA, requiring only 5992 slices and 60 memory blocks. In addition, a very compact implementation is also provided, producing 5438 signatures per second with only 18 memory blocks.