基于编码的数字签名综述

宋永成; 黄欣沂; 伍玮; 陈海霞

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

您当前的位置：

首页 >

文章列表页 >

基于编码的数字签名综述

综述 | 更新时间：2024-06-03

- 基于编码的数字签名综述
- Survey of code-based digital signatures
- 网络与信息安全学报 2021年7卷第4期页码：1-17
- 作者机构：
  
  1. 福建师范大学计算机与网络空间安全学院福建省网络安全与密码技术重点实验室，福建福州 350117
  2. 密码科学技术国家重点实验室，北京 100878
  3. 福建师范大学数学与统计学院，福建福州 350117
- 作者简介：
  
  [ "宋永成（1993- ），男，安徽亳州人，博士，主要研究方向为基于编码的密码学、数字签名与身份认证" ]
  [ "黄欣沂（1981- ），男，江苏仪征人，福建师范大学教授、博士生导师，主要研究方向为密码学与信息安全" ]
  [ "伍玮（1981- ），女，江苏南京人，福建师范大学教授，主要研究方向为密码学与信息安全" ]
  [ "陈海霞（1982- ），女，江苏南通人，福建师范大学博士生，主要研究方向为图像认证、图像取证、网络安全与密码学等" ]
- 基金信息：
  
  国家自然科学基金;TheNational Natural Science Foundation of China(62032005;61822202;61872087;61841701;61902070;61872089;61972094);福建省科学技术厅科学基金;Science Foundation of Fujian Provincial Science and Technology Agency(2020J02016);国家密码技术重点实验室项目;State Key La-boratory of Cryptology Research Fund(MMKFKT202008)
- DOI：10.11959/j.issn.2096-109x.2021079
  中图分类号： TP309.2
- 网络首发：2021-08，
  
  纸质出版：2021-08-15
- 稿件说明：
移动端阅览
宋永成, 黄欣沂, 伍玮, 等. 基于编码的数字签名综述[J]. 网络与信息安全学报, 2021,7(4):1-17.

Yongcheng SONG, Xinyi HUANG, Wei WU, et al. Survey of code-based digital signatures[J]. Chinese Journal of Network and Information Security, 2021, 7(4): 1-17.
宋永成, 黄欣沂, 伍玮, 等. 基于编码的数字签名综述[J]. 网络与信息安全学报, 2021,7(4):1-17. DOI： 10.11959/j.issn.2096-109x.2021079.

Yongcheng SONG, Xinyi HUANG, Wei WU, et al. Survey of code-based digital signatures[J]. Chinese Journal of Network and Information Security, 2021, 7(4): 1-17. DOI： 10.11959/j.issn.2096-109x.2021079.

摘要

量子计算理论和实践的快速发展导致基于传统数论困难问题的密码安全性存在很大不确定性。编码困难问题是公认的NP完全问题，求解复杂度呈指数级增长，且目前未发现量子计算对基于编码密码算法的威胁。因此，基于编码的密码算法有望抵抗量子算法攻击，是抗量子密码的主流方向之一。设计安全高效的基于编码的数字签名一直是公开问题。多年来，国内外学者使用经典方法和新方法构造基于编码的数字签名，但现存的构造存在安全性弱或性能差的不足。对当前基于编码的数字签名进行了综述，分析和评价了各类基于编码的数字签名，并指出未来的研究方向。

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.

关键词

Keywords

references

SHOR P W , . Algorithms for quantum computation:discrete logarithms and factoring [C ] // The 35th Annual Symposium on Foundations of Computer Science . 1994 : 124 - 134 .

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 .

SENDRIER N . Code-based cryptography:state of the art and perspectives [J ] . IEEE Security ＆ Privacy , 2017 , 15 ( 4 ): 44 - 50 .

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 .

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 .

KILTZ E , PIETRZAK K , VENTURI D , et al . Efficient authentication from hard learning problems [J ] . Journal of Cryptology , 2017 , 30 ( 4 ): 1238 - 1275 .

MERKLE R C , . A certified digital signature [C ] // The 9th Annual International Cryptology Conference (CRYPTO) . 1990 : 218 - 238 .

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 .

MC-ELIECE R J . A public-key cryptosystem based on algebraic coding theory [R ] . Te DSN Progress Report,1978 , 4244 : 114 - 116 .

BERNSTEIN D J , CHOU T , LANGE T , et al . Classic McEliece [R ] . Third Round Submission to the NIST Post-quantum Cryptography Call , 2020 .

ARAGON N , BARRETO P , BETTAIEB S , et al . Bike [R ] . Third Round Submission to the NIST Post-quantum Cryptography Call , 2020 .

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 .

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 .

ARAGON N , BLAZY O , DENEUVILLE J D , et al . Rollo [R ] . Second Round Submission to the NIST Post-quantum Cryptography Call , 2019 .

WANG X M . Digital signature scheme based on error-correcting codes [J ] . Electronics Letters , 1990 , 26 ( 13 ): 898 - 899 .

STERN J , . A new identification scheme based on syndrome decoding [C ] // The 13th Annual International Cryptology Conference (CRYPTO) . 1993 : 13 - 21 .

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 .

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 .

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 .

DIFFIE W , HELLMAN M . New directions in cryptography [J ] . IEEE Transactions on Information Theory , 1976 , 22 ( 6 ): 644 - 654 .

MACWILLIAMS F J , SLOANE N J A . The theory of error-correcting codes [M ] . North-Holland : North-Holland Publishing Company , 1977 .

DENEUVILLE J , GABORIT P . Cryptanalysis of a code-based one-time signature [J ] . Designs,Codes and Cryptography , 2020 , 88 ( 9 ): 1857 - 1866 .

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 .

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 .

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 .

PRANGE E . The use of information sets in decoding cyclic codes [J ] . IRE Transactions on Information Theory , 1962 , 8 ( 5 ): 5 - 9 .

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 .

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 .

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 .

NIEBUHR R , PERSICHETTI E , CAYREL P , et al . On lower bounds for information set decoding over F q and on the effect of partial knowledge [J ] . International Journal of Information and Coding Theory (IJICOT) . 2017 , 4 ( 1 ): 47 - 78 .

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 .

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 .

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 .

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 .

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 .

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 .

SENDRIER N , . Decoding one out of many [C ] // The 4th International Conference on Post-Quantum Cryptography (PQCrypto) . 2011 : 51 - 67 .

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 .

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 .

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 .

ALABBADI M , WICKER S B . Security of Xinmei digital signature scheme [J ] . Electronics Letters , 1992 , 28 ( 9 ): 890 - 891 .

ALABBADI M , WICKER S B . Digital signature schemes based on error-correcting codes [C ] // IEEE International Symposium on Information Theory (ISIT) . 1993 : 199 - 199 .

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 .

王新梅 . 纠错码数字签名方案的修正 [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 .

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 .

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 .

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 .

张振峰 , 冯登国 , 戴宗铎 . 基于纠错码的 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 .

KATZ J , LINDELL Y . Introduction to modern cryptography [M ] . Taylor ＆ Francis : CRC Press , 2014 .

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 .

VÉRON P . Improved identification schemes based on error-correcting codes [J ] . Applicable Algebra in Engineering,Communication and Computing , 1996 , 8 ( 1 ): 57 - 69 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

LEE Y , LEE W , KIM Y S , et al . Modified pqsigRM:RM code-based signature scheme [J ] . IEEE Access , 2020 , 8 : 177506 - 177518 .

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 .

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 .

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 .

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 .

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 .

LYUBASHEVSKY V , . Lattice signatures without trapdoors [C ] // The 31th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) , 2012 : 738 - 755 .

PERSICHETTI E . Improving the efficiency of code-based cryptography [D ] . Auckland:University of Auckland , 2012 : 111 - 115 .

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 .

BERNSTEIN D J , HAIJLSING A , LANGE T , et al . Comments on RaCoSS.A submission to NIST's PQC Competition [EB ] . 2018 .

ROY P S , MOROZOV K , FUKUSHIMA K , et al . Code-based signature scheme without trapdoors [R ] . IEICE Technical Report,2018 , 118 : 17 - 22 .

XAGAWA K . Practical attack on RaCoSS-R [J ] . IACR Cryptology ePrint Archive , 2018 :831.

PERSICHETTI E . Efficient one-time signatures from quasi-cyclic codes:A full treatment [J ] . Cryptography , 2018 , 2 ( 4 ): 30 .

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 .

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

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 .

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 .

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 .

ARAGON N , BALDI M , DENEUVILLE J C , et al . Cryptanalysis of a code-based full-time signature [J ] . Designs,Codes and Cryptography , 2021 .

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 .

LANDAIS G , SENDRIER N . Implementing CFS [C ] // The 13th International Conference on Cryptology in India (INDOCRYPT) . 2012 : 474 - 488 .

浏览量

533

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据