High Weight Code-Based Signature Scheme from QC-LDPC Codes

We propose a new Hamming metric code-based signature scheme (called HWQCS) based on quasi-cyclic low density parity-check (QC-LDPC) codes. We propose the use of high error on QC-LDPC codes for constructing this signature and analyse its complexity. We show that HWQCS signature scheme achieves EUF-CMA security in the classical random oracle model, assuming the hardness of the syndrome decoding problem and the codeword finding problem for QC-LDPC codes. Furthermore, we also give a detailed security analysis of the HWQCS signature scheme. Based on the complexities of solving the underlying problems, the public key size and signature size of the HWQCS signature scheme are 1568 bytes and 4759 bytes respectively at 128-bit security level.