基于编码的数字签名综述

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

Abstract

Abstract:

The rapid development of quantum computing theory and practice brings great uncertainty to the security of cryptography based on hard problems in number theory.Code-based hard problem is recognized as NP-complete problem, the complexity increases exponentially, and there is currently no threat of quantum computing to code-based cryptographic algorithm.Therefore, code-based algorithm can resist the quantum algorithm attack, which is one of the main directions of quantum-resistant cryptography.It is still an open problem to design secure and efficient code-based signatures.For many years, international researchers use classical and new methods to construct code-based signatures, but existing constructions are weak in security or poor in performance.Code-based signatures were comprehensively summarized and analyzed, and future research directions were indicated.

Key words: quantum-resistant cryptography, code-based cryptography, digital signatures, identification

CLC Number:

TP309.2

Yongcheng SONG, Xinyi HUANG, Wei WU, Haixia CHEN. Survey of code-based digital signatures[J]. Chinese Journal of Network and Information Security, 2021, 7(4): 1-17.

Figures/Tables 11

References 92

[1]	SHOR P W , . Algorithms for quantum computation:discrete logarithms and factoring[C]// The 35th Annual Symposium on Foundations of Computer Science. 1994: 124-134.
[2]	GROVER L K , . A fast quantum mechanical algorithm for database search[C]// The 28th Annual ACM Symposium on the Theory of Computing. 1996: 212-219.
[3]	SENDRIER N . Code-based cryptography:state of the art and perspectives[J]. IEEE Security ＆ Privacy, 2017,15(4): 44-50.
[4]	HOFFSTEIN J , PIPHER J , SILVERMAN J H . NTRU:a ring-based public key cryptosystem[C]// The 3rd International Algorithmic Number Theory Symposium. 1998: 267-288.
[5]	PETZOLDT A , CHEN M S , YANG B Y ,et al. Design principles for HFEv-based multivariate signature schemes[C]// The 21st International Conference on the Theory and Application of Cryptology and Information Security(ASIACRYPT). 2015: 311-334.
[6]	KILTZ E , PIETRZAK K , VENTURI D ,et al. Efficient authentication from hard learning problems[J]. Journal of Cryptology, 2017,30(4): 1238-1275.
[7]	MERKLE R C , . A certified digital signature[C]// The 9th Annual International Cryptology Conference (CRYPTO). 1990: 218-238.
[8]	JALALI A , AZARDERAKHSH R , KERMANI M M ,et al. ARMv8 SIKE:optimized supersingular isogeny key encapsulation on ARMv8 processors[J]. IEEE Transactions on Circuits and Systems I:Regular Papers, 2019,66-I(11): 4209-4218.
[9]	MC-ELIECE R J . A public-key cryptosystem based on algebraic coding theory[R]. Te DSN Progress Report,1978, 4244: 114-116.
[10]	BERNSTEIN D J , CHOU T , LANGE T ,et al. Classic McEliece[R]. Third Round Submission to the NIST Post-quantum Cryptography Call, 2020.
[11]	ARAGON N , BARRETO P , BETTAIEB S ,et al. Bike[R]. Third Round Submission to the NIST Post-quantum Cryptography Call, 2020.
[12]	MELCHOR C A , ARAGON N , BETTAIEB S ,et al. Hamming quasi-cyclic (HQC)[R]. Third Round Submission to the NIST Post-quantum Cryptography Call, 2020.
[13]	MELCHOR C A , ARAGON N , BETTAIEB S ,et al. Rank quasi-cyclic(RQC)[R]. Second Round Submission to the NIST Post-quantum Cryptography Call, 2019.
[14]	ARAGON N , BLAZY O , DENEUVILLE J D ,et al. Rollo[R]. Second Round Submission to the NIST Post-quantum Cryptography Call, 2019.
[15]	WANG X M . Digital signature scheme based on error-correcting codes[J]. Electronics Letters, 1990,26(13): 898-899.
[16]	STERN J , . A new identification scheme based on syndrome decoding[C]// The 13th Annual International Cryptology Conference (CRYPTO). 1993: 13-21.
[17]	KABATIANSKII G , KROUK E , SMEETS B . A digital signature scheme based on random error-correcting codes[C]// The 6th IMA International Conference on Cryptography and Coding. 1997: 161-167.
[18]	COURTOIS N T , FINIASZ M , SENDRIER N . How to achieve a McEliece-based digital signature scheme[C]// The 7th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 2001: 157-174.
[19]	ARAGON N , BLAZY O , GABORIT P ,et al. Durandal:a rank metric based signature scheme[C]// The 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). 2019: 728-758.
[20]	DIFFIE W , HELLMAN M . New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976,22(6): 644-654.
[21]	MACWILLIAMS F J , SLOANE N J A . The theory of error-correcting codes[M]. North-Holland: North-Holland Publishing Company, 1977.
[22]	DENEUVILLE J , GABORIT P . Cryptanalysis of a code-based one-time signature[J]. Designs,Codes and Cryptography, 2020,88(9): 1857-1866.
[23]	GABORIT P , HAUTEVILLE A , PHAN D H ,et al. Identity-based encryption from codes with rank metric[C]// The 37th Annual International Cryptology Conference (CRYPTO). 2017: 194-224.
[24]	AGUILAR-MELCHOR C , BLAZY O , DENEUVILLE J C ,et al. Efficient encryption from random quasi-cyclic codes[J]. IEEE Transactions on Information Theory, 2018,64(5): 3927-3943.
[25]	BERLEKAMP E R , MCELIECE R J , VAN TILBORG H C A . On the inherent intractability of certain coding problems[J]. IEEE Transactions on Information Theory, 1978,24: 384-386.
[26]	PRANGE E . The use of information sets in decoding cyclic codes[J]. IRE Transactions on Information Theory, 1962,8(5): 5-9.
[27]	MAY A , OZEROV I . On computing nearest neighbors with applications to decoding of binary linear codes[C]// The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). 2015: 203-228.
[28]	TORRES R C , SENDRIER N . Analysis of information set decoding for a sub-linear error weight[C]// The 7th International Conference on Post-Quantum Cryptography (PQCrypto). 2016: 144-161.
[29]	BOTH L , MAY A . Decoding linear codes with high error rate and its impact for LPN security[C]// The 9th International Conference on Post-Quantum Cryptography(PQCrypto). 2018: 25-46.
[30]	NIEBUHR R , PERSICHETTI E , CAYREL P ,et al. On lower bounds for information set decoding over F_qand on the effect of partial knowledge[J]. International Journal of Information and Coding Theory (IJICOT). 2017,4(1): 47-78.
[31]	CHABAUD F , STERN J . The cryptographic security of the syndrome decoding problem for rank distance codes[C]// The 3rd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 1996: 368-381.
[32]	GABORIT P , ZEMOR G . On the hardness of the decoding and the minimum distance problems for rank codes[J]. IEEE Transactions on Information Theory, 2016,62: 7245-7252.
[33]	GABORIT P , RUATTA O , SCHREK J . On the complexity of the rank syndrome decoding problem[J]. IEEE Transactions on Information Theory, 2016,62(2): 1006-1019.
[34]	ARAGON N , GABORIT P , HAUTEVILLE A ,et al. A new algorithm for solving the rank syndrome decoding problem[C]// IEEE International Symposium on Information Theory (ISIT). 2018: 2421-2425.
[35]	BARDET M , BROS M , CABARCAS D ,et al. Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems[C]// The 26th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 2020: 507-536.
[36]	BARDET M , BRIAUD P , BROS M ,et al. An algebraic attack on rank metric code-based cryptosystems[C]// The 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). 2020: 64-93.
[37]	SENDRIER N , . Decoding one out of many[C]// The 4th International Conference on Post-Quantum Cryptography (PQCrypto). 2011: 51-67.
[38]	GUO Q , JOHANSSON T , L?NDAHL C , . A new algorithm for solving ring-LPN with a reducible polynomial[J]. IEEE Transactions on Information Theory. 2015,61(11): 6204-6212.
[39]	L?NDAHL C , JOHANSSON T , SHOOSHTARI M K ,et al. Squaring attacks on Mceliece public-key cryptosystems using quasi-cyclic codes of even dimension[J]. Designs,Codes and Cryptography. 2016,80(2): 359-377.
[40]	OTMANI A , TILLICH J P . An efficient attack on all concrete KKS proposals[C]// The 4th International Conference on Post-Quantum Cryptography (PQCrypto). 2011: 98-116.
[41]	ALABBADI M , WICKER S B . Security of Xinmei digital signature scheme[J]. Electronics Letters, 1992,28(9): 890-891.
[42]	ALABBADI M , WICKER S B . Digital signature schemes based on error-correcting codes[C]// IEEE International Symposium on Information Theory (ISIT). 1993: 199-199.
[43]	ALABBADI M , WICKER S B . A digital signature scheme based on linear error-correcting block codes[C]// The 4th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 1993: 238-248.
[44]	王新梅 . 纠错码数字签名方案的修正[J]. 电子学报, 2000,28(2): 110-112.
	WANG X M . Modification of error-correcting code digital signature scheme[J]. Acta Electronica Sinica, 2000,28(2): 110-112.
[45]	YE D , YANG J , DAI Z ,et al. Attacks on two digital signature schemes based on error correcting codes[C]// International Conference on Information and Communications Security. 2001: 84-89.
[46]	ZHANG Z , FENG D , DAI Z . Cryptanalysis on AW digital signature scheme based on error-correcting codes[J]. Science in China Series F Information Sciences, 2002,45(5): 397-400.
[47]	XU S B , DOUMEN J , VAN TILBORG H . On the security of digital signature schemes based on error-correcting codes[J]. Designs,Codes and Cryptography, 2003,28(2): 187-199.
[48]	张振峰, 冯登国, 戴宗铎 . 基于纠错码的 AW 数字签名方案的分析[J]. 中国科学, 2003,33(2): 164-167.
	ZHANG Z F , FENG D G , DAI Z Z . Analysis of AW digital signature scheme based on error-correcting code[J]. Science China. 2003,33(2): 164-167.
[49]	KATZ J , LINDELL Y . Introduction to modern cryptography[M]. Taylor ＆ Francis: CRC Press, 2014.
[50]	FIAT A , SHAMIR A . How to prove yourself:practical solutions to identification and signature problems[C]// The 6th Annual International Cryptology Conference (CRYPTO). 1986. 186-194.
[51]	VéRON P . Improved identification schemes based on error-correcting codes[J]. Applicable Algebra in Engineering,Communication and Computing, 1996,8(1): 57-69.
[52]	JAIN A , KRENN S , PIETRZAK K ,et al. Commitments and efficient zero-knowledge proofs from learning parity with noise[C]// The 18th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 2012: 663-680.
[53]	CAYREL P , VéRON P ,, ALAOUI S M E Y . A zero-knowledge identification scheme based on the q-ary syndrome decoding problem[C]// The 17th International Conference on Selected Areas in Cryptography (SAC). 2010: 171-186.
[54]	AGUILAR C , GABORIT P , SCHREK J . A new zero-knowledge code based identification scheme with reduced communication[C]// IEEE Information Theory Workshop (ITW). 2012: 648-652.
[55]	GABORIT P , SCHREK J , ZéMOR G , . Full cryptanalysis of the Chen identification protocol[C]// The 4th International Conference on Post-Quantum Cryptography (PQCrypto). 2011: 35-50.
[56]	BELLINI E , CAULLERY F , HASIKOS A ,et al. Code-based signature schemes from identification protocols in the rank metric[C]// The 17th International Conference on Cryptology and Network Security (CANS). 2018: 277-298.
[57]	BELLINI E , CAULLERY F , GABORIT P ,et al. Improved Véron identification and signature schemes in the rank metric[C]// International Symposium on Information Theory (ISIT). 2019: 1872-1876.
[58]	AYEBIE E B , ASSIDI H , SOUIDI E M . An efficient identification scheme based on rank metric[C]// The 12th International Symposium on Foundations and Practice of Security (FPS). 2019: 273-289.
[59]	BELLINI E , GABORIT P , HASIKOS A ,et al. Enhancing code based zero-knowledge proofs using rank metric[C]// The 19th International Conference on Cryptology and Network Security (CANS). 2020: 570-592.
[60]	LAU T S C , TAN C H , PRABOWO T F . Key recovery attacks on some rank metric code-based signatures[C]// The 17th IMA International Conference on Cryptography and Coding (IMACC). 2019: 215-235.
[61]	HAUTEVILLE A , TILLICH J . New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem[C]// IEEE International Symposium on Information Theory (ISIT). 2015: 2747-2751.
[62]	CAYREL P L , OTMANI A , VERGNAUD D . On Kabatianskii-Krouk-Smeets signatures[C]// The 1st International Workshop on Arithmetic of Finite Fields (WAIFI). 2007: 237-251.
[63]	BARRETO P S L M , MISOCZKI R , SIMPLICIO JR M A . One-time signature scheme from syndrome decoding over generic error-correcting codes[J]. Journal of Systems and Software, 2011,84(2): 198-204.
[64]	GABORIT P , SCHREK J . Efficient code-based one-time signature from automorphism groups with syndrome compatibility[C]// IEEE International Symposium on Information Theory (ISIT). 2012: 1982-1986.
[65]	FINIASZ M , SENDRIER N . Security bounds for the design of code-based cryptosystems[C]// The 15th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 2009: 88-105.
[66]	FAUGERE J , GAUTHIER-UMANA V ,, OTMANI A ,et al. A distinguisher for high-rate McEliece cryptosystems[J]. IEEE Transactions on Information Theory, 2013,59(10): 6830-6844.
[67]	FINIASZ M , . Parallel-CFS strengthening the CFS McEliece-based signature scheme[C]// The 17th International Conference on Selected Areas in Cryptography (SAC). 2010: 159-170.
[68]	BARRETO P S L M , CAYREL P L , MISOCZKI R ,et al. Quasi-Dyadic CFS signatures[C]// The 6th International Conference on Information Security and Cryptology (Inscrypt). 2010: 336-349.
[69]	BALDI M , BIANCHI M , CHIARALUCE F ,et al. Using LDGM codes and sparse syndromes to achieve digital signatures[C]// The 5th International Conference on Post-Quantum Cryptography (PQCypto). 2013: 1-15.
[70]	GABORIT P , RUATTA O , SCHREK J ,et al. RankSign:An efficient signature algorithm based on the rank metric[C]// The 6th International Conference on Post-Quantum Cryptography (PQCypto). 2014: 88-107.
[71]	DEBRIS-ALAZARD T , SENDRIER N , TILLICH J P . Wave:A new family of trapdoor one-way preimage sampleable functions based on codes[C]// The 25th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 2019: 21-51.
[72]	LEE Y , LEE W , KIM Y S ,et al. Modified pqsigRM:RM code-based signature scheme[J]. IEEE Access, 2020,8: 177506-177518.
[73]	PHESSO A , TILLICH J P . An efficient attack on a code-based signature scheme[C]// The 7th International Conference on Post-Quantum Cryptography (PQCypto). 2016: 86-103.
[74]	DEBRIS-ALAZARD T , TILLICH J P . Two attacks on rank metric code-based schemes:RankSign and an IBE scheme[C]// The 24th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 2018: 62-92.
[75]	ARAGON N , GABORIT P , HAUTEVILLE A ,et al. RankSign-a signature proposal for the NIST's call[R]. First Round Submission to the NIST Post-Quantum Cryptography Call, 2017.
[76]	BRICOUT R , CHAILLOUX A , DEBRIS-ALAZARD T ,, et al . Ternary syndrome decoding with large weight[C]// The 26th International Conference on Selected Areas in Cryptography (SAC). 2019: 437-466.
[77]	LEE W , KIM Y S , NO J S . A new signature scheme based on punctured reed-muller code with random insertion[J]. Computer Research Repository (CoRR), 2016.
[78]	LYUBASHEVSKY V , . Lattice signatures without trapdoors[C]// The 31th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), 2012: 738-755.
[79]	PERSICHETTI E . Improving the efficiency of code-based cryptography[D]. Auckland:University of Auckland, 2012: 111-115.
[80]	FUKUSHIMA K , ROY P S , XU R ,et al. Random code-based signature scheme (RaCoSS)[R]. First Round Submission to the NIST Post-quantum Cryptography Call. 2017.
[81]	BERNSTEIN D J , HAIJLSING A , LANGE T ,et al. Comments on RaCoSS.A submission to NIST's PQC Competition[EB]. 2018.
[82]	ROY P S , MOROZOV K , FUKUSHIMA K ,et al. Code-based signature scheme without trapdoors[R]. IEICE Technical Report,2018, 118: 17-22.
[83]	XAGAWA K . Practical attack on RaCoSS-R[J]. IACR Cryptology ePrint Archive, 2018:831.
[84]	PERSICHETTI E . Efficient one-time signatures from quasi-cyclic codes:A full treatment[J]. Cryptography, 2018,2(4): 30.
[85]	SANTINI P , BALDI M , CHIARALUCE F . Cryptanalysis of a one-time code-based digital signature scheme[C]// IEEE International Symposium on Information Theory (ISIT). 2019: 2594-2598.
[86]	SONG Y , HUANG X , MU Y ,et al. A new code-based signature scheme with shorter public key[J]. IACR Cryptology ePrint Archive, 2019: 53
[87]	ARAGON N , BLAZY O , DENEUVILLE J C ,et al. Cryptanalysis of a rank-based signature with short public keys[J]. Designs,Codes and Cryptography, 2020,88（4）： 643-653.
[88]	SONG Y , HUANG X , MU Y ,et al. An improved durandal signature scheme[J]. SCIENCE CHINA Information Sciences, 2020,63(3): 132103:1-132103:16.
[89]	SONG Y , HUANG X , MU Y ,et al. A code-based signature scheme from the Lyubashevsky framework[J]. Theoretical Computer Science, 2020,835: 15-30.
[90]	ARAGON N , BALDI M , DENEUVILLE J C ,et al. Cryptanalysis of a code-based full-time signature[J]. Designs,Codes and Cryptography, 2021.
[91]	BERNSTEIN D J , CHOU T , SCHWABE P . McBits:fast constant-time code-based cryptography[C]// The 15th International Workshop on Cryptographic Hardware and Embedded Systems (CHES). 2013: 250-272.
[92]	LANDAIS G , SENDRIER N . Implementing CFS[C]// The 13th International Conference on Cryptology in India (INDOCRYPT). 2012: 474-488.

Metrics

Recommended 0

No Suggested Reading articles found!

距离	协议	公钥长度/bit	执行一次通信开销/bit	欺骗概率	通信开销（或签名长度）/kB
秩距离	RStern^[55]	816	2 298	2/3	61
	RTKPT^[59]	1 309	2 955	2/3	79
	Stern^[16]	1 100	3 044	2/3	81
汉明距离	JKPT^[52]	1 873	4 075	2/3	109
	AGS^[54]	1 873	2 871	1/2	45
	CVA^[53]	1 374	3 825	1/2	60

类型	算法	公钥长度	签名长度	不足之处
	Stern^[16]	1 100 bit	81 kB
	JKPT^[52]	1 873 bit	109 kB
Stern 型	AGS^[54]	1 873 bit	45 kB	签名长
	CVA^[53]	1 374 bit	60 kB
	RStern^[55]	816 bit	61 kB
	RJKPT^[59]	1 309 bit	79 kB
Hash-Sign型	Wave^[71]	3.2 MB	8 312 bit	公钥长签名效率低
	CFS^[18]	2 GB	306 bit
Lyubashevsky型	Durandal^[19]	15 kB	4 kB	签名和公钥长度待优化
	改进的Durandal^[88]	5 kB	3 kB

Survey of code-based digital signatures

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 92

Related Articles 9

Metrics

Recommended 0

[1]	Ruiqi XIA, Manman LI, Shaozhen CHEN. Identification on the structures of block ciphers using machine learning [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 79-89.
[2]	Guozhen SHI, Kunyang LI, Yao LIU, Yongjian YANG. Encrypted traffic identification method based on deep residual capsule network with attention mechanism [J]. Chinese Journal of Network and Information Security, 2023, 9(1): 32-41.
[3]	Tao JIANG, Hang XU, Liangmin WANG, Jianfeng MA. Proof of storage with corruption identification and recovery for dynamic group users [J]. Chinese Journal of Network and Information Security, 2022, 8(5): 75-87.
[4]	Tong QIAO, Hongwei YAO, Binmin PAN, Ming XU, Yanli CHEN. Research progress of digital image forensic techniques based on deep learning [J]. Chinese Journal of Network and Information Security, 2021, 7(5): 13-28.
[5]	Xiang ZOU, Jinsong HAN, Yuhang QU, Jian XIAO, Xian XU. Passive biometric electronic lock via UHF RFID [J]. Chinese Journal of Network and Information Security, 2021, 7(2): 126-140.
[6]	Xiaokang YIN,Liu LIU,Long LIU,Shengli LIU. Function argument number identification in stripped binary under PPC and MIPS instruction set [J]. Chinese Journal of Network and Information Security, 2020, 6(4): 95-103.
[7]	Tianqi HE,Xinghao JIANG,Tanfeng SUN. Review of video frame rate up conversion detection [J]. Chinese Journal of Network and Information Security, 2018, 4(10): 1-11.
[8]	Mao-guang WANG,Zi-jun ZHU. Credit risk identification of high-risk online lending enterprises based on neural network model [J]. Chinese Journal of Network and Information Security, 2017, 3(12): 15-21.
[9]	Bo WANG,Jian-feng YIN,Ya-bin LI. Performance evaluation for JPEG compression on model-based source camera identification [J]. Chinese Journal of Network and Information Security, 2016, 2(9): 65-71.