An Efficient Code Based Digital Signature Algorithm

10.6633/IJNS.201711.19(6).24

Fang Ren；Dong Zheng；WeiJing Wang

Digital Signature ； Hash Function ； Quantum Attack ； Syndrome

International Journal of Network Security

19卷6期（2017 / 11 / 01）

1072 - 1079

英文

In the case of most current digital signature algorithm can be attacked by quantum algorithm, code based digital signature algorithm, which represents the Post-Quantum Cryptography, has become the hotspot of current re- search. CFS algorithms proposed in 2001 is one of the most important code based digital signature algorithm, but its signature efficiency is very low. In this paper, an improved CFS algorithm is proposed by means of code based hash function. The output of this hash function is a syndrome of a regular word whose weight is no more than error correcting capacity t of the code. By using this hash function instead of the random hash function, the de- coding algorithm can avoid the time-consuming syndrome decoding attempts. The signing time of the improved algorithm reduces t! times than the original. At the same time, the signature efficiency is no longer restricted to error correcting capacity of the code. Furthermore, the securities of these two algorithms both rely on the equivalent NP complete problems.