基于背包问题的可纠错数字签名方案

Error-Correcting Digital Signature Scheme Based on Knapsack Problem

因特网的高速发展导致普通的数字签名在网络传输过程中会出现传输错误,而传统的数字签名方案没有考虑纠错问题,因此无法对传输中可能出现的错误进行恢复.为了解决一般数字签名中的纠错问题,同时保证签名的效率,文中基于超递增向量背包问题的可解性,参考已提出的可纠错数字签名方案,利用矩阵的思想,提出了一种可纠错数字签名方案.该方案能纠正在网络传输中出错的消息,与现有几个纠错数字签名方案相比,其所需的附加数据和计算量都是最少的.文中还在随机预言机的模型下证明了该方案的安全性.

The rapid development of the Internet tends to cause transmission errors of digital signature in networks.However,the traditional digital signature schemes cannot correct the errors because these schemes never take error-correction into consideration.In order to solve this problem and to implement high-efficiency signature,an error-correcting digital signature scheme is presented according to the existing schemes.The proposed scheme is based on the thought of matrix and the knapsack problem of ultra-increasing vector.As compared with several existing error-correcting digital signature schemes,the proposed scheme,which effectively corrects the transmission errors of di-gital signature in networks,is of the least additional data and calculation load.The security of the scheme is also proven based on the random oracle model.