基于編碼的數(shù)字簽名綜述

宋永成，黃欣沂，伍瑋，陳海霞

基于編碼的數(shù)字簽名綜述

宋永成1,2，黃欣沂1，伍瑋3，陳海霞1

（1. 福建師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室，福建 福州 350117；2. 密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100878；3. 福建師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福建 福州 350117）

量子計(jì)算理論和實(shí)踐的快速發(fā)展導(dǎo)致基于傳統(tǒng)數(shù)論困難問題的密碼安全性存在很大不確定性。編碼困難問題是公認(rèn)的NP完全問題，求解復(fù)雜度呈指數(shù)級增長，且目前未發(fā)現(xiàn)量子計(jì)算對基于編碼密碼算法的威脅。因此，基于編碼的密碼算法有望抵抗量子算法攻擊，是抗量子密碼的主流方向之一。設(shè)計(jì)安全高效的基于編碼的數(shù)字簽名一直是公開問題。多年來，國內(nèi)外學(xué)者使用經(jīng)典方法和新方法構(gòu)造基于編碼的數(shù)字簽名，但現(xiàn)存的構(gòu)造存在安全性弱或性能差的不足。對當(dāng)前基于編碼的數(shù)字簽名進(jìn)行了綜述，分析和評價(jià)了各類基于編碼的數(shù)字簽名，并指出未來的研究方向。

抗量子密碼；基于編碼的密碼學(xué)；數(shù)字簽名；身份認(rèn)證

1 引言

RSA、ECDSA等經(jīng)典密碼算法的安全性主要基于分解大整數(shù)、求解離散對數(shù)等傳統(tǒng)困難問題。但隨著量子計(jì)算理論和實(shí)踐的快速發(fā)展，基于傳統(tǒng)困難問題密碼算法的安全性存在很大不確定性。例如，Shor量子算法[1]可以有效求解離散對數(shù)問題和分解大整數(shù)問題。Grover量子算法[2]可以加速（最多二次方）求解困難問題。因此，研究安全高效的抗量子密碼算法成為學(xué)術(shù)界和工業(yè)界的共識(shí)。

目前，設(shè)計(jì)抗量子密碼算法基于的困難問題主要包括基于編碼的困難問題[3]、基于格的困難問題[4]、基于多變量的困難問題[5]、基于LPN（learning parity with noise）的困難問題[6]、基于哈希函數(shù)的困難問題[7]、基于同源的困難問題[8]。本文主要研究基于編碼的困難問題，設(shè)計(jì)的抗量子密碼算法簡稱基于編碼的密碼算法或基于編碼的密碼學(xué)。

1978年，Mc-Eliece[9]開創(chuàng)了基于編碼密碼學(xué)，提出首個(gè)基于編碼的公鑰加密算法。經(jīng)過長期的研究，基于編碼的加密算法和密鑰交換協(xié)議取得積極進(jìn)展，如美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST，National Institute of Standards and Technology）抗量子密碼算法標(biāo)準(zhǔn)征集的第二、三輪競選算法中，基于編碼困難問題的構(gòu)造主要是公鑰加密算法和密鑰交換協(xié)議[10-14]。但是，基于編碼的數(shù)字簽名（CBDS，code-based digital signature）算法的研究相對滯后。

自1978 年基于編碼的密碼學(xué)被正式提出以來，國內(nèi)外學(xué)者從不同角度探索構(gòu)造CBDS 算法的方法。至今，CBDS算法主要包括5類：Xinmei型CBDS算法[15]、Stern型CBDS算法[16]、KKS 型CBDS算法[17]、Hash-Sign型CBDS算法[18]、Lyubashevsky型CBDS算法[19]。但這些CBDS算法存在簽名和公鑰長、效率低、安全性弱等不足。現(xiàn)有CBDS算法及其研究現(xiàn)狀如圖1所示，帶下劃線的CBDS 算法是安全的或一次簽名算法。

本文對CBDS算法進(jìn)行綜述，分析和評價(jià)各類CBDS算法，并指出每一類的研究狀態(tài)和未來可能的研究方向。

圖1 現(xiàn)有CBDS算法及其研究現(xiàn)狀

Figure 1 Existing CBDS and its research status

2 基礎(chǔ)知識(shí)

本節(jié)主要介紹數(shù)字簽名算法、編碼學(xué)（糾錯(cuò)碼）基礎(chǔ)、編碼困難問題。

2.1 數(shù)字簽名算法

Diffie和Hellman[20]于1976年提出數(shù)字簽名的概念。數(shù)字簽名算法由如下3個(gè)多項(xiàng)式時(shí)間算法構(gòu)成。

2) 簽名生成算法Sign(,sk) ：該算法是 PPT 算法，它的輸入為簽名人的私鑰sk和消息，輸出為消息的簽名。

3) 簽名驗(yàn)證算法Verify(pk,(,))：該算法是確定多項(xiàng)式時(shí)間（DPT，deterministic polynomial time）算法，它的輸入為簽名人的公鑰pk和消息/簽名對(,)，輸出為一個(gè)比特。若=1，表明消息/簽名對(,)是有效的；若=0，表明消息/簽名對(,)是無效的。

數(shù)字簽名算法的標(biāo)準(zhǔn)安全要求：在自適應(yīng)選擇消息攻擊下滿足存在不可偽造性（EUF-CMA，existential unforgeability under adaptive chosen message attacks）。對于PPT敵手，即使在獲得他希望得到的有效消息/簽名對后，其能為新消息計(jì)算有效簽名的概率也是可忽略的。

2.2 編碼學(xué)基礎(chǔ)

本節(jié)給出漢明距離碼和秩距離碼、生成矩陣、校驗(yàn)矩陣的基本定義。

根據(jù)線性空間的封閉性，無論是漢明距離還是秩距離線性碼，最小距離等于所有碼字的最小重量。

在編碼密碼學(xué)中，通常使用準(zhǔn)循環(huán)碼[24]和理想碼[13,19]的系統(tǒng)生成矩陣和校驗(yàn)矩陣減少公鑰的存儲(chǔ)。

2.3 編碼困難問題

編碼困難問題[25]是一類量子計(jì)算機(jī)無法有效求解的 NP完全問題。因此，基于編碼困難問題設(shè)計(jì)抗量子密碼算法是一個(gè)可靠的候選。本文涉及漢明距離碼和秩距離碼，因此分別介紹在兩種距離下編碼困難問題。

HSD問題和HGD問題是等價(jià)的，它們都是 NP完全問題[25]。1962年，Prange[26]首次使用信息集合譯碼（ISD，information set decoding）算法解HGD問題，在此基礎(chǔ)上大量ISD 優(yōu)化算法被提出，如文獻(xiàn)[27-30]的研究成果。

文獻(xiàn)[23]表明解RSL問題的復(fù)雜度比解 RSD 問題的復(fù)雜度小。

3 基于編碼的數(shù)字簽名

本節(jié)分別分析和評價(jià)5類基于編碼的數(shù)字簽名（CBDS）算法：Xinmei型CBDS算法[15]、Stern型CBDS算法[16]、KKS型CBDS算法[17]、Hash-Sign型CBDS算法[18]、Lyubashevsky 型CBDS算法[19]。

3.1 Xinmei型CBDS算法

王新梅[15]于1990年提出第一個(gè)CBDS算法，簡稱Xinmei算法。1992年，Alabbadi和Wicker[41]對Xinmei算法提出有效的選擇消息攻擊，簡稱AW攻擊，隨后給出一種可以抵抗AW 攻擊的新算法，簡稱AW算法[42-43]。同時(shí)王新梅對Xinmei算法作出修正[44]，該算法可以抵抗AW攻擊。但是，在2001—2003年，文獻(xiàn)[45-48]分別對這一系列算法進(jìn)行了分析總結(jié)，找到了有效攻擊方法，表明Xinmei型的設(shè)計(jì)很難構(gòu)造出安全有效的CBDS算法，該類型CBDS算法的研究至此終止。

3.2 Stern型CBDS算法

1993 年，Stern[16]首次提出安全的CBID 協(xié)議，簡稱Stern協(xié)議，如圖2所示。Stern協(xié)議需運(yùn)行三輪，欺騙概率（2/3）不可忽略。本文稱欺騙概率不可忽略的CBID協(xié)議為Stern型CBID協(xié)議或Stern型協(xié)議；稱使用Fiat-Shamir變換將Stern型CBID協(xié)議轉(zhuǎn)化成的數(shù)字簽名算法為Stern型CBDS算法。

圖2 Stern身份認(rèn)證協(xié)議

Figure 2 Stern identification protocol

在減少單次通信開銷方面，Véron[51]于1996年提出一個(gè)欺騙概率2/3三輪CBID協(xié)議，簡稱Véron協(xié)議，如圖3所示。Véron協(xié)議的安全性依賴于解HGD 問題的困難性，它的目的是：允許證明者向驗(yàn)證者證明他擁有HGD問題的解。證明者的私鑰是一個(gè)待編碼消息和一個(gè)重量為的錯(cuò)誤，公開一個(gè)隨機(jī)線性碼的生成矩陣和。通過承諾、挑戰(zhàn)、回應(yīng)三輪交互，驗(yàn)證者確定證明者擁有和。Véron協(xié)議的優(yōu)勢是單次通信開銷比Stern 協(xié)議更小。但文獻(xiàn)[52]表明，是公開的，會(huì)泄露置換的信息，從而的信息被泄露，進(jìn)而Véron協(xié)議不滿足零知識(shí)性。同時(shí)Jain 等[52]提出一個(gè)基于HGD問題的身份認(rèn)證協(xié)議，簡稱JKPT協(xié)議，如圖4所示。是由生成矩陣決定的碼。JKPT 協(xié)議和Véron 協(xié)議類型相同，但JKPT協(xié)議比Stern協(xié)議的通信開銷更大（128 bit安全級別，為109 kB）。

圖3 Véron 身份認(rèn)證協(xié)議

Figure 3 Véron identification protocol

圖4 JKPT身份認(rèn)證協(xié)議

Figure 4 JKPT identification protocol

圖5 CVA 身份認(rèn)證協(xié)議

Figure 5 CVA identification protocol

圖6 AGS身份認(rèn)證協(xié)議

Figure 6 AGS identification protocol

目前，秩距離CBID協(xié)議都是Stern、Véron、AGS、CVA、JKPT協(xié)議的秩距離變體[55-59]。但這些秩距離變體存在通信開銷大、不滿足完備性、不滿足零知識(shí)性等，具體如下。

①盡管Stern和JKPT協(xié)議的秩距離變體[55,59]（分別簡稱RStern和RJKPT協(xié)議）是安全的CBID協(xié)議，但它們的通信開銷仍然很大（128 bit安全級別，分別為61 kB和79 kB）。

②文獻(xiàn)[60]表明Véron協(xié)議的秩距離變體[56]不滿足零知識(shí)性。CVA協(xié)議的秩距離變體[56]通信開銷更大（128 bit安全級別，為3 MB）。

③ AGS和CVA協(xié)議的秩距離變體[56-58]不滿足完備性。AGS協(xié)議的兩個(gè)秩距離變體[57-58]使用秩距離循環(huán)碼，受疊碼攻擊[61]的影響。為避免疊碼攻擊的影響，需選擇更大的安全參數(shù)實(shí)現(xiàn)標(biāo)準(zhǔn)的安全級別，這會(huì)降低協(xié)議的性能。

表1統(tǒng)計(jì)了安全CBID協(xié)議的性能（128 bit安全級別）。該方向需要研究的問題是：①構(gòu)造單次通信開銷或欺騙概率更小的Stern型CBID協(xié)議；②在秩距離下，構(gòu)造安全高效的Stern型CBID協(xié)議。

表 1 安全CBID協(xié)議的性能（128 bit安全級別）

3.3 KKS型CBDS算法

1997 年，Kabatianskii等[17]基于HSL問題提出KKS簽名算法（算法1）。KKS算法的核心思想是：把給定線性碼的可譯校驗(yàn)子構(gòu)成一個(gè)集合，用給定線性碼的校驗(yàn)矩陣（公鑰）和另一個(gè)隨機(jī)碼的生成矩陣（私鑰）構(gòu)造新公鑰，使得公鑰和消息的乘積屬于上述集合中的校驗(yàn)子，該校驗(yàn)子對應(yīng)的錯(cuò)誤（簽名值）是消息和生成矩陣的乘積。KKS型CBDS算法不需要譯碼操作。

算法1 KKS 簽名算法

密鑰生成 簽名者進(jìn)行下面步驟。

算法2 KKS簽名算法變體

密鑰生成 簽名者進(jìn)行下面步驟。

算法3 GS 簽名算法

密鑰生成 簽名者進(jìn)行下面步驟

因此，KKS型CBDS算法的主要不足是安全性不高，被認(rèn)為是一次簽名算法。這一方向需要研究的問題是：在保持簽名算法良好簽名效率的前提下，減小公鑰長度，尋求更安全的變體，突破一次簽名的限制，實(shí)現(xiàn)標(biāo)準(zhǔn)數(shù)字簽名的功能。

3.4 Hash-Sign 型CBDS算法

圖 7 兩種CFS 框架

Figure 7 Two frameworks of CFS

算法4 CFS 簽名算法

密鑰生成 簽名者進(jìn)行下面步驟。

2010年，F(xiàn)iniasz[67]提出并行CFS算法。新算法在安全參數(shù)較小的情況下可以達(dá)到標(biāo)準(zhǔn)的安全級別，但簽名變長，簽名效率更低。

2010年，Barreto等[68]基于Quasi-Dyadic碼改進(jìn)CFS簽名算法。改進(jìn)的簽名算法雖然能減小公鑰長度，但降低了簽名效率。

2013年，Baldi等[69]基于LDGM碼改進(jìn)CFS算法，簡稱LDGM。由于改進(jìn)的算法生成的簽名具有某種相關(guān)性，敵手可以利用多個(gè)簽名獲得的信息，為新消息偽造簽名[73]。因此，LDGM算法被視為一次簽名算法。

2014年，Gabori等[70]提出基于秩距離LRPC碼的 Hash-Sign 型CBDS算法，簡稱RankSign算法。但是，Debris-Alazard等[74]利用擴(kuò)張LRPC 碼秩重量很小的特點(diǎn)，攻破了RankSign 算法和NIST中的改進(jìn)版[75]。

2020年，Yongwoo等[72]基于修改的RM碼改進(jìn)了CFS算法，簡稱MpqsigRM算法。MpqsigRM 算法是NIST第一輪中pqsigRM 算法[77]的修正，它的安全性被歸約到SD 問題和修改的RM 碼區(qū)分問題。在能抵抗現(xiàn)有攻擊的條件下，MpqsigRM算法的性能比CFS算法更優(yōu)，具有公鑰短、生成簽名快的優(yōu)點(diǎn)，但該算法的安全性存疑。

上述改進(jìn)的CFS 算法都無法滿足實(shí)際需求。目前，構(gòu)造Hash-Sign型CBDS算法需要進(jìn)一步研究的問題是：①探索可譯校驗(yàn)子稠密的Goppa 碼類或其他碼類代替Goppa碼，在保證標(biāo)準(zhǔn)安全級別的前提下，提高簽名的效率，減小公鑰長度；②提高Wave簽名算法的簽名效率和公鑰長度；③研究不依賴糾錯(cuò)能力的Hash-Sign型CBDS算法。

3.5 Lyubashevsky 型CBDS算法

2012年，Lyubashevsky[78]提出基于格的無陷門簽名算法，該簽名算法可視為由身份認(rèn)證協(xié)議結(jié)合Fiat-Shamir變換轉(zhuǎn)化而來。Lyubashevsky簽名算法包含的身份認(rèn)證協(xié)議稱為Lyubashevsky身份認(rèn)證協(xié)議。根據(jù)Lyubashevsky身份認(rèn)證協(xié)議的設(shè)計(jì)思路，基于編碼困難問題設(shè)計(jì)的身份認(rèn)證協(xié)議被稱為Lyubashevsky（也稱Schnorr- Lyubashevsky）型CBID協(xié)議；使用Fiat-Shamir變換將Lyubashevsky 型CBID協(xié)議轉(zhuǎn)化成的數(shù)字簽名算法稱為Lyubashevsky型CBDS算法。

圖8 Lyubashevsky型CBID 協(xié)議

Figure 8 CBID in Lyubashevsky framework

Lyubashevsky 型CBID協(xié)議的特點(diǎn)是：欺騙概率可忽略，執(zhí)行一次就能滿足安全要求；不依賴陷門和譯碼算法。因此，Lyubashevsky型CBDS 算法可以克服Hash-Sign 型和Stern 型CBDS算法的不足。Stern 型CBID協(xié)議欺騙概率大（2/3 或1/2），必須重復(fù)多次，才能滿足安全要求，這導(dǎo)致Stern 型CBDS算法簽名太長，實(shí)用性差。Hash-Sign 型CBDS算法使用陷門和譯碼算法，極大限制了安全參數(shù)的選擇，這導(dǎo)致公鑰太長、效率太低，實(shí)用性差。

2012年，Persichetti[79]使用Lyubashevsky 型CBID協(xié)議的簡單形式構(gòu)造CBDS算法。在Persichetti算法中，挑戰(zhàn)是有限域的元素，而不是向量，簽名人首先計(jì)算挑戰(zhàn)和私鑰（小重量向量）的乘積，然后加上隨機(jī)小重量錯(cuò)誤。但根據(jù)Persichetti 的分析，在漢明距離下，可以通過統(tǒng)計(jì)分析恢復(fù)私鑰；在秩距離下，可以通過代數(shù)攻擊恢復(fù)私鑰。換句話說，這種簡單構(gòu)造不能很好地隱藏私鑰。

另一個(gè)類似的工作是NIST 第一輪中的RaCoSS 簽名算法[80]。該算法使用很大的Chernoff 界限制簽名的重量，而且安全參數(shù)小，這使得敵手僅利用公鑰就能偽造簽名[81]。之后，文獻(xiàn)[82]通過減小生成簽名的重量，選擇大安全參數(shù)修正該算法。但由于重量限制一直很寬松，大于HGV界，所以改進(jìn)的算法再一次被攻破[83]。

2018年，Persichetti[84]提出改進(jìn)算法，并聲稱新算法可以實(shí)現(xiàn)一次簽名。在該算法中，私鑰是由小重量向量生成的循環(huán)矩陣，承諾向量和挑戰(zhàn)向量都是小重量的，簽名的重量接近GV界。由于簽名的重量接近GV界，所以它克服了RaCoSS算法的弱點(diǎn)，但簽名重量很小帶來另一個(gè)不足。文獻(xiàn)[22, 85]分別利用簽名重量很小的性質(zhì)，提出代數(shù)和統(tǒng)計(jì)攻擊。Deneuville 等[22]將挑戰(zhàn)轉(zhuǎn)化成LDPC碼的校驗(yàn)矩陣，生成的簽名作為LDPC碼的校驗(yàn)子。由于要求生成簽名的重量接近GV界，導(dǎo)致私鑰、承諾向量、挑戰(zhàn)向量的重量都很小且達(dá)到相應(yīng)LDPC碼的譯碼能力，所以使用LDPC碼的譯碼算法可解出私鑰和承諾向量。Santini等[85]提出的統(tǒng)計(jì)攻擊表明，僅通過一個(gè)簽名就可以恢復(fù)出私鑰。該統(tǒng)計(jì)攻擊利用小重量承諾的特性，由于私鑰向量循環(huán)移位后與承諾向量幾乎沒有交集，所以通過對挑戰(zhàn)向量進(jìn)行重量次循環(huán)后，可以很大概率決定私鑰的支集。Deneuville等[22]提出進(jìn)一步的改進(jìn)，新改進(jìn)算法使用一系列固定重量的向量構(gòu)成私鑰矩陣（不是循環(huán)矩陣），挑戰(zhàn)依然是小重量向量。但是，這個(gè)構(gòu)造生成的簽名會(huì)泄露私鑰信息，僅對有限數(shù)量的簽名是安全的。

2019年，Song等[86]根據(jù)Lyubashevsky架構(gòu)提出一個(gè)秩距離CBDS算法，簡稱SHMW算法。該算法的不足類似Persichetti 算法[84]（要求承諾小重量，簽名的重量接近GV界）。因此，Aragon等[87]利用該不足提出一個(gè)有效攻擊：首先用挑戰(zhàn)向量構(gòu)造LRPC碼的校驗(yàn)矩陣，然后用LRPC碼譯碼算法解出小重量承諾向量和私鑰。

圖9 Durandal 算法的身份認(rèn)證形式

Figure 9 Durandal algorithm in the identification form

2020年，Song等[88]在理想碼情形下，利用多項(xiàng)式乘積可以表達(dá)成向量?矩陣乘積的性質(zhì)，改進(jìn)了Durandal算法。在改進(jìn)算法中，簽名人僅僅選擇兩個(gè)相同小支集向量作為私鑰，不必選擇元素來自同一支集的矩陣作為私鑰。改進(jìn)的Durandal算法依賴可靠的RSD問題，不再依賴RSL問題。對于128 bit安全級別，在簽名效率和密鑰長度方面，改進(jìn)算法都有明顯改進(jìn)。

2020年，Song等[89]根據(jù)Lyubashevsky型CBID協(xié)議的架構(gòu)提出漢明距離CBDS算法，簡稱SNMWW算法。在SNMWW算法中，私鑰由一些高碼率隨機(jī)線性碼的系統(tǒng)生成矩陣構(gòu)成，挑戰(zhàn)是小重量向量，要求簽名重量接近GV界。之后，Aragon 等[90]提出一個(gè)新統(tǒng)計(jì)攻擊，對于80 bit安全級別，通過10個(gè)簽名，240的計(jì)算代價(jià)可恢復(fù)私鑰。但僅知一個(gè)簽名無法成功攻擊。該簽名算法簽名很短（80 bit安全級別，簽名長度為4 990 bit），公開矩陣可由320 bit長的種子生成。因此，該算法被視為目前最優(yōu)的編碼一次簽名算法。

Lyubashevsky型CBDS算法需要研究的問題是：①優(yōu)化Durandal簽名算法的公鑰長度和簽名長度，提高該算法的可用性；②提高Durandal簽名算法依賴?yán)щy問題的可靠性。

綜上所述，CBDS算法的研究情況總結(jié)如下。

①存在性能差、安全性弱等不足，具體如表2所示。性能差主要體現(xiàn)在公鑰長、簽名長、簽名效率低。簽名效率低主要體現(xiàn)在Hash-Sign型CBDS 算法生成簽名時(shí)間較長，文獻(xiàn)[71,91-92]測試了Wave和CFS的簽名時(shí)間，每生成一個(gè)簽名平均需要幾秒。需要優(yōu)化Stern型CBDS算法的簽名長度、Hash-Sign型CBDS算法的公鑰長度和簽名效率、Lyubashevsky型CBDS算法的簽名和公鑰長度。

②構(gòu)造安全CBDS算法的方法少，有待進(jìn)一步研究探索。目前CBDS 算法的類型主要有Xinmei型、KKS型、Stern型、Hash-Sign型、Lyubashevsky型。僅最后三類存在安全的CBDS算法，且有待進(jìn)一步改進(jìn)安全性和性能。

表2 現(xiàn)存安全CBDS算法的性能（128 bit安全級別）

4 結(jié)束語

基于編碼的密碼算法能夠抵抗量子算法攻擊，是抗量子密碼的主流方向之一。設(shè)計(jì)安全高效的基于編碼的數(shù)字簽名是待解決的難題。本文綜述了基于編碼的數(shù)字簽名技術(shù)，介紹了現(xiàn)有構(gòu)造基于編碼的數(shù)字簽名的方法及其研究進(jìn)展；分析了算法安全性和性能，同時(shí)指出了基于編碼的數(shù)字簽名未來可能的研究目標(biāo)和發(fā)展方向。

[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 Fand 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] 王新梅. 糾錯(cuò)碼數(shù)字簽名方案的修正[J]. 電子學(xué)報(bào), 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] 張振峰, 馮登國, 戴宗鐸. 基于糾錯(cuò)碼的 AW 數(shù)字簽名方案的分析[J]. 中國科學(xué), 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-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.

Survey of code-based digital signatures

SONG Yongcheng1,2, HUANG Xinyi1, WU Wei3, CHEN Haixia1

1. Fujian Provincial Key Laboratory of Network Security and Cryptology, College of Computer and Cyber Security, Fujian Normal University, Fuzhou 350117, China2. State Key Laboratory of Cryptology, Beijing 100878, China3. School of Mathematics and Statistics, Fujian Normal University, Fuzhou 350117, China

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.

quantum-resistant cryptography, code-based cryptography, digital signatures, identification

TP309.2

A

10.11959/j.issn.2096?109x.2021079

2021?03?01；

2021?06?10

黃欣沂，xyhuang@fjnu.edu.cn

國家自然科學(xué)基金（62032005, 61822202, 61872087, 61841701, 61902070, 61872089, 61972094）；福建省科學(xué)技術(shù)廳科學(xué)基金（2020J02016）；國家密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室項(xiàng)目（MMKFKT202008）

The National Natural Science Foundation of China (62032005, 61822202, 61872087, 61841701, 61902070, 61872089, 61972094), Science Foundation of Fujian Provincial Science and Technology Agency (2020J02016), State Key Laboratory of Cryptology Research Fund (MMKFKT202008)

宋永成, 黃欣沂, 伍瑋, 等. 基于編碼的數(shù)字簽名綜述[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2021, 7(4): 1-17.

SONG Y C, HUANG X Y, WU W, et al. Survey of code-based digital signatures[J]. Chinese Journal of Network and Information Security, 2021, 7(4): 1-17.

宋永成（1993?），男，安徽亳州人，博士，主要研究方向?yàn)榛诰幋a的密碼學(xué)、數(shù)字簽名與身份認(rèn)證。

黃欣沂（1981? ），男，江蘇儀征人，福建師范大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)與信息安全。

伍瑋（1981?），女，江蘇南京人，福建師范大學(xué)教授，主要研究方向?yàn)槊艽a學(xué)與信息安全。

陳海霞（1982?），女，江蘇南通人，福建師范大學(xué)博士生，主要研究方向?yàn)閳D像認(rèn)證、圖像取證、網(wǎng)絡(luò)安全與密碼學(xué)等。