基于纠错码的数字签名技术综述

doi:10.11959/j.issn.2096-109x.2016.00108

网络与信息安全学报 ›› 2016, Vol. 2 ›› Issue (11): 1-10.doi: 10.11959/j.issn.2096-109x.2016.00108

• 综述 • 下一篇

基于纠错码的数字签名技术综述

任方^1,²,郑东^1,²,范九伦²

¹ 西安邮电大学无线网络安全技术国家工程实验室，陕西西安 710121
² 西安邮电大学通信与信息工程学院，陕西西安 710121

修回日期:2016-10-19 出版日期:2016-11-01 发布日期:2016-11-15
作者简介:任方（1981-），男，陕西西安人，博士，西安邮电大学副教授，主要研究方向为密码学与信息安全。|郑东（1964-），男，山西翼城人，博士，西安邮电大学教授、博士生导师，主要研究方向为后量子密码及云计算安全技术。|范九伦（1964-），男，河南焦作人，博士，西安邮电大学教授、博士生导师，主要研究方向为信号与信息处理、信息安全。
基金资助:
国家自然科学基金资助项目(61272037);国家自然科学基金资助项目(61472472);陕西省自然科学基础研究计划基金资助项目(2015JQ6262);陕西省教育厅专项科研计划基金资助项目(15JK1669)

Survey of digital signature technology based on error correcting codes

Fang REN^1,²,Dong ZHENG^1,²,Jiu-lun FAN²

¹ National Engineering Laboratory for Wireless Security,Xi’an University of Posts and Telecommunications,Xi’an 710121,China
² Department of Communication and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710121,China

Revised:2016-10-19 Online:2016-11-01 Published:2016-11-15
Supported by:
The National Natural Science Foundation of China(61272037);The National Natural Science Foundation of China(61472472);The Natural Science Basic Research Plan of Shaanxi Province(2015JQ6262)

摘要/Abstract

摘要：

量子算法的出现对当前广泛使用的基于数论困难问题的数字签名算法造成了严重威胁，而基于纠错码的数字签名算法可以抵抗已知的量子算法攻击，近年来，得到了众多研究者的关注，成为最有发展潜力的数字签名技术之一。基于纠错码的数字签名算法具有较高的安全性和较快的运算速度，其研究成果遍及普通签名、盲签名、环签名、群签名等多个领域。对基于纠错码的数字签名技术进行了综述，分析和评价了当前的主流算法，并指出未来可能的研究方向。

关键词: 纠错码, 数字签名, 校验子译码, 后量子密码

Abstract:

The emergence of quantum algorithms have threatened the security of digital signature algorithms widely used currently,most of which based on some hard problems in number theory.The digital signature algorithms based on error correcting codes,which can resist quantum attack,has been studied by many researchers in recent years and there have been many research results in different areas,such as normal digital signature,blind signature,ring signature,group signature.Because of the fast computation speed and high security,it has become one of the most promising digital signature technologies.A comprehensive introduction was given and digital signature technologies based on error correcting codes were summarized,the key technologies were analyzed and the possible research directions in the future were pointed out.

Key words: error correcting codes, digital signature, syndrome decoding, post quantum cryptography

中图分类号:

TP309.2

任方,郑东,范九伦. 基于纠错码的数字签名技术综述[J]. 网络与信息安全学报, 2016, 2(11): 1-10.

Fang REN,Dong ZHENG,Jiu-lun FAN. Survey of digital signature technology based on error correcting codes[J]. Chinese Journal of Network and Information Security, 2016, 2(11): 1-10.

参考文献 73

[1]	DIFFIE W , HELLMAN M E . New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976,22(6): 644-654.
[2]	RIVEST R L , SHAMIR A , ADLEMAN L . A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978,21(2): 120-126.
[3]	KATZ J , LINDELL Y . Introduction to modern cryptography[M]. Boca Raton: CRC PressPress, 2014.
[4]	SHOR P W , . Algorithms for quantum computation:discrete logarithms and factoring[C]// The 35th Annual Symposium onFoundations of Computer Science,IEEE. 1994: 124-134.
[5]	GROVER L K , . A fast quantum mechanical algorithm for database search[C]// The 28th Annual ACM Symposium on Theory of Computing. 1996: 212-219.
[6]	Post-quantum cryptography[M]. Springer Science ＆ Business Media, 2009.
[7]	OVERBECK R , SENDRIER N . Code-based cryptography[C]// Post-quantum Cryptography. Berlin Heidelberg, 2009: 95-145.
[8]	MERKLE R C , . A certified digital signature[C]// Advances in Cryptology--CRYPTO’89, Springer New York. 1990: 218-238.
[9]	HOFFSTEIN J , PIPHER J , SILVERMAN J H . NTRU:a ring-based public key cryptosystem[M]// Algorithmic Number Theory. Berlin Heidelberg, 1998: 267-288.
[10]	REGEV O . On lattices,learning with errors,random linear codes,and cryptography[J]. Journal of the ACM (JACM), 2009,56(6): 34.
[11]	MATSUMOTO T , IMAI H . Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[C]// Advances in Cryptology-EUROCRYPT’88, Berlin Heidelberg. 1988: 419-453.
[12]	MCELIECE R J . A public-key cryptosystem based on algebraic coding theory[J]. DSN Progress Report, 1978,42(44): 114-116.
[13]	NIEDERREITER H . Knapsack-type cryptosystems and algebraic coding theory[J]. Problems of Control and Information Theory, 1986,15(2): 159-166.
[14]	LI Y X , DENG R H , WANG X M . On the equivalence of McEliece's and Niederreiter's public-key cryptosystems[J]. IEEE Transactions on Information Theory, 1994,40(1): 271-273.
[15]	WANG X M . Digital signature scheme based on error-correcting codes[J]. Electronics Letters, 1990,26(13): 898-899.
[16]	ALABBADI M , WICKER S B . Security of Xinmei digital signature scheme[J]. Electronics Letters, 1992,28(9): 890-891.
[17]	ALABBADI M , WICKER S B . Digital signature schemes based on error-correcting codes[C]// IEEE International Symposium on Information Theory. 1993: 199-199.
[18]	王新梅 . 纠错码数字签名方案的修正[J]. 电子学报, 2000,28(2): 110-112.
	WANG X M . Correction of digital signature scheme for error correcting codes[J]. Journal of Electronics, 2000,28(2): 110-112.
[19]	XU S B , DOUMEN J , TILBORG H V . On the security of digital signature schemes based on error-correcting codes[J]. Designs Codes ＆ Cryptography, 2003,28(2): 187-199.
[20]	张振峰, 冯登国, 戴宗铎 . 基于纠错码的AW数字签名方案的分析[J]. 中国科学, 2003,33(2): 164-167.
	ZHANG Z F , FENG D G , DAI Z D . Analysis of AW digital signature scheme based on error correcting codes[J]. Chinese Journal of Science, 2003,33(2): 164-167.
[21]	COURTOIS N T , FINIASZ M , SENDRIER N . How to achieve a McEliece-based digital signature scheme[C]// Advances in Cryptology-ASIACRYPT 2001. 2001: 157-174.
[22]	STERN J , . A new identification scheme based on syndrome decoding[C]// Advances in Cryptology—CRYPTO’93, Berlin Heidelberg. 1994: 13-21.
[23]	KABATIANSKII G , KROUK E , SMEETS B . A digital signature scheme based on random error-correcting codes[C]// Crytography and Coding,, Berlin Heidelberg. 1997: 161-167.
[24]	MACWILLIAMS F J , SLOANE N J A . The theory of error correcting codes[M]. Elsevier, 1977.
[25]	PATTERSON N . The algebraic decoding of Goppa codes[J]. IEEE Transactions on Information Theory, 1975,21(2): 203-207.
[26]	BERLEKAMP E R , MCELIECE R J , VANTILBORG H C A . On the inherent intractability of certain coding problems[J]. IEEE Transactions on Information Theory, 1978,24(3): 384-386.
[27]	FIAT A , SHAMIR A . How to prove yourself:Practical solutions to identification and signature problems[C]// Advances in Cryptology-CRYPTO’86, Berlin Heidelberg. 1987: 186-194.
[28]	DALLOT L . Towards a concrete security proof of Courtois,Finiasz and Sendrier signature scheme[M]// Research in Cryptology. Berlin Heidelberg: SpringerPress, 2008: 65-77.
[29]	BELLARE M , ROGAWAY P . Random oracles are practical:a paradigm for designing efficient protocols[C]// The 1st ACM Conference on Computer and Communication Security,Association for Computing Machinery. 1993: 62-73.
[30]	FAUGERE J C,GAUTHIER-UMANA V , OTMANI A ,et al. A distinguisher for high-rate McEliececryptosystems[J]. IEEE Transactions on Information Theory, 2013,59(10): 6830-6844.
[31]	FINIASZ M , . Parallel-CFS[C]// Selected Areas in Cryptography. Berlin Heidelberg:Springer, 2011: 159-170.
[32]	FINIASZ M , SENDRIER N . Security bounds for the design of code-based cryptosystems[C]// Advances in Cryptology-ASIACRYPT 2009. 2009: 88-105.
[33]	BARRETO P S L M , CAYREL P L , MISOCZKI R ,et al. Quasi-dyadic CFS signatures[C]// Information Security and Cryptology, Berlin Heidelberg. 2011: 336-349.
[34]	GABORIT P , GIRAULT M . Lightweight code-based identification and signature[C]// IEEE International Symposium on Information Theory. 2007: 191-195.
[35]	CAYREL P L,VéRON P , ALAOUI S M E Y . A zero-knowledge identification scheme based on the qary syndrome decoding problem[C]// Selected Areas in Cryptography. 2011: 171-186.
[36]	GOLDWASSER S , KALAI Y T . On the (in) security of the Fiat-Shamir paradigm[C]// The Annual Symposium onFoundations of Computer Science. 2003: 102-113.
[37]	CAYREL P L , OTMANI A , VERGNAUD D . On kabatianskii-krouk-smeets signatures[C]// Arithmetic of Finite Fields. Berlin Heidelberg, 2007: 237-251.
[38]	OTMANI A , TILLICH J P . An efficient attack on all concrete KKS proposals[C]// Post-quantum Cryptography. Berlin Heidelberg, 2011: 98-116.
[39]	BARRETO P S L M , MISOCZKI R , SIMPLICIO M A . One-time signature scheme from syndrome decoding over generic error-correcting codes[J]. Journal of Systems ＆ Software, 2011,84(2): 198-204.
[40]	CHAUM D , . Blind signatures for untraceable payments[C]// Advances in Cryptology. Springer US, 1983: 199-203.
[41]	CHAUM D , FIAT A , NAOR M . Untraceable electronic cash[C]// Advances in Cryptology. 1990: 319-327.
[42]	STADLER M , PIVETEAU J M , CAMENISCH J . Fair blind signatures[C]// Advances in Cryptology—Eurocrypt’95. 1995: 209-219.
[43]	OKAMOTO T , . Provably secure and practical identification schemes and corresponding signature schemes[C]// Advances in Cryptology-CRYPTO’92. 1993: 31-53.
[44]	POINTCHEVAL D , STERN J . Provably secure blind signature schemes[C]// Advances in Cryptology—ASIACRYPT'96. 1996: 252-265.
[45]	SCHNORR C P . Efficient signature generation by smart cards[J]. Journal of Cryptology, 1991,4(3): 161-174.
[46]	OVERBECK R . A step towards QC blind signatures[J]. IACR Cryptology ePrint Archive, 2009: 102.
[47]	SHAMIR A , . An efficient identification scheme based on permuted kernels[C]// Advances in Cryptology-CRYPTO’89. 1990: 606-609.
[48]	王倩, 郑东, 任方 . 基于编码的盲签名方案[J]. 计算机应用, 2015,35(10): 2867-2871.
	WANG Q , ZHENG D , REN F . A blind signature scheme based on coding[J]. Computer Application, 2015,35(10): 2867-2871.
[49]	CHAUM D , VAN HEYST E . Group signatures[C]// Advances in Cryptology-EUROCRYPT’91. 1991: 257-265.
[50]	BONEHD , BOYEN X , SHACHAM H . Short group signatures[C]// Advances in Cryptology-CRYPTO. 2004: 41-55.
[51]	LYSYANSKAYA A , RAMZAN Z . Group blind digital signatures:a scalable solution to electronic cash[C]// Financial Cryptography. 1998: 184-197.
[52]	ZHENG D , LI X , MA C ,et al. Democratic group signatures with threshold traceability[J]. IACR Cryptology ePrint Archive, 2008: 112.
[53]	EZERMAN M F , LEE H T , LING S ,et al. A provably secure group signature scheme from code-based assumptions[J]. IACR Cryptology ePrint Archive, 2015: 479.
[54]	RIVEST R L , SHAMIR A , TAUMAN Y . How to leak a secret[C]// Advances in Cryptology—ASIACRYPT 2001. 2001: 552-565.
[55]	ZHENG D , LI X , CHEN K . Code-based ring signature scheme[J]. IJ Network Security, 2007,5(2): 154-157.
[56]	BRESSON E , STERN J , SZYDLO M . Threshold ring signatures and applications to ad-hoc groups[C]// Advances in Cryptology-CRYPTO 2002. 2002: 465-480.
[57]	WONG D S , FUNG K , LIU J K ,et al. On the RS-code construction of ring signature schemes and a threshold setting of RST[C]// Information and Communications Security. 2003: 34-46.
[58]	LIU J K , WEI V K , WONG D S . A separable threshold ring signature scheme[J]. Lecture Notes in Computer Science, 2003,2971: 12-26.
[59]	MELCHOR C A , CAYREL P L , GABORIT P ,et al. A new efficient threshold ring signature scheme based on coding theory[J]. IEEE Transactions on Information Theory, 2011,57(7): 4833-4842.
[60]	GABORIT P , GIRAULT M . Lightweight code-based identification and signature[C]// IEEE International Symposium on Information Theory. 2007: 191-195.
[61]	DALLOT L , VERGNAUD D . Provably secure code-based threshold ring signatures[C]// Cryptography and Coding. 2009: 222-235.
[62]	BRESSON E , STERN J , SZYDLO M . Threshold ring signatures and applications to ad-hoc groups[C]// Advances in CryptologyCRYPTO 2002. 2002: 465-480.
[63]	SHAMIR A . Identity-based cryptosystems and signature schemes[J]. Lecture Notes in Computer Science, 1985,21(2): 47-53.
[64]	BONEH D , FRANKLIN M . Identity-based encryption from the weil pairing[C]// Advances in Cryptology-CRYPTO 2001. 2001: 213-229.
[65]	BAEK J , ZHENG Y . Identity-based threshold decryption[C]// Public Key Cryptography–PKC 2004. 2004: 262-276.
[66]	ZHAO S , AGGARWAL A , FROST R ,et al. A survey of applications of identity-based cryptography in mobile ad-hoc networks[J]. Communications Surveys ＆ Tutorials,IEEE, 2012,14(2): 380-400.
[67]	SILVA D E , PESSOA A L C . Towards a fully self-organized identity-based key management system for MANETs[C]// 2013 IEEE 9th International Conference on Wireless and Mobile Computing,Networking and Communications (WiMob). 2013: 717-723.
[68]	SAHAI A , WATERS B . Fuzzy identity-based encryption[C]// Advances in Cryptology–EUROCRYPT 2005. 2005: 457-473.
[69]	CHASE M . Multi-authority attribute based encryption[M]// Theory of Cryptography,Berlin Heidelberg. 2007: 515-534.
[70]	LI J , REN K , KIM K . A2BE:accountable attribute-based encryption for abuse free access control[J]. IACR Cryptology ePrint Archive, 2009,2009: 118-12.
[71]	BELLARE M , NAMPREMPRE C , NEVEN G . Security proofs for identity-based identification and signature schemes[J]. Journal of Cryptology, 2009,22(1): 1-61.
[72]	GALINDO D , HERRANZ J , KILTZ E . On the generic construction of identity-based signatures with additional properties[C]// Advances in Cryptology–ASIACRYPT 2006. 2006: 178-193.
[73]	CAYREL P L , GABORIT P , GIRAULT M . Identity-based identification and signature schemes using correcting codes[C]// WCC. 2007: 69-78.

基于纠错码的数字签名技术综述

Survey of digital signature technology based on error correcting codes

在线阅读

pdf下载

可视化

摘要/Abstract

引用本文

使用本文

参考文献 73

相关文章 6

Metrics

推荐阅读 0

[1]	谢绒娜,毛卫华,史国振. 基于签名认证的电子发票真伪性验证方案[J]. 网络与信息安全学报, 2019, 5(6): 105-112.
[2]	付钰,孙连亮,吴晓平. 基于WPKI和虹膜识别的二维码安全管理系统[J]. 网络与信息安全学报, 2018, 4(5): 62-68.
[3]	唐紫鑫,黄欣沂. 基于批量签名思想的可截取签名构造[J]. 网络与信息安全学报, 2018, 4(12): 44-53.
[4]	郭青霄,张大伟,常亮,刘晓东,宋靖文. 基于SM2的代理保护代理签名的设计与实现[J]. 网络与信息安全学报, 2017, 3(9): 47-54.
[5]	高天寒,李艳强. 车载自组织网匿名接入认证机制研究综述[J]. 网络与信息安全学报, 2016, 2(8): 10-16.
[6]	张彩娟,游林. 基于双线性对的多重数字签名方案[J]. 网络与信息安全学报, 2016, 2(6): 66-70.