A New Post-Quantum Signature Based on Punctured QC-LDPC Code with Random Insertion

This paper proposes an enhanced version of the CFS signature scheme, leveraging QC-LDPC codes with puncturing and random insertion techniques. The puncturing process is designed based on the selection of minimum Hamming weight codewords, ensuring that the remaining structure of the parity-check matrix retains sufficient error-correcting capabilities. Random insertion of new rows into the punctured parity-check matrix further enhances security by introducing randomness. The cyclic structure of QC-LDPC codes greatly reduces the key size while the BP decoding algorithm improves the decoding success rate, thereby enhancing the signature generation efficiency. The scheme proposed in this paper reduces the key size to 6144 bytes compared to the original CFS scheme's 6283256 bytes under the similar parameters setting. Additionally, the average number of signing attempts is reduced from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t!$</tex> to a constant multiple of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t$</tex>. It also greatly enhances security compared to recent improvements, particularly in resisting structural attacks, Stern's attacks, OTD attacks, and forgery attacks. Similar to the original CFS scheme, the proposed scheme can be proven to satisfy Existential Unforgeability under Chosen Message Attacks (EUF-CMA) security.