A QC-LDPC Code Based Digital Signature Algorithm

摘要

Courtois-Finiasz-Sendrier (CFS) digital signature algorithm, which proposed in 2001, is the most important code based digital signature algorithm and can resist the known attack of quantum algorithms such as Shor algorithm and Grover algorithm. But the efficiency of CFS is very low because of the extremely low signing speed and the large public key size. In this paper, a variation of CFS algorithm is presented. Instead of the Goppa code and the Patterson decoding algorithm, the new algorithm selects the Quasi-Cyclic Low Density Parity Check (QC-LDPC) code and the Belief Propagation (BP) decoding algorithm in the signing process. Compared with CFS algorithm, the new algorithm greatly reduces the storage space of public key and improves the efficiency of signature without compromising the security.