基于LWE的數(shù)字簽名方案

黃建鑫 李豪 羅燁 白鳳娥

摘要：數(shù)字簽名是實(shí)現(xiàn)身份識(shí)別、安全計(jì)算、信息可信發(fā)布的基本密碼原語。現(xiàn)有簽名方案大多是基于大整數(shù)因式分解和離散對數(shù)問題。但隨著量子技術(shù)的實(shí)現(xiàn)與發(fā)展，這些方案都不能抵抗量子計(jì)算攻擊。該文基于LWE的數(shù)字簽名方案，該方案的安全性基于格的最壞情況難解性LWE問題，具有較好的抗量子特性。

關(guān)鍵詞：格；數(shù)字簽名方案；LWE；公鑰密碼體制；hash函數(shù)

中圖分類號(hào)：TN918.91 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-5039（2018）17-0047-03

Abstract： Digital signature is the basic cryptic primitives for identity identification， security calculation and information trustworthiness release. Most of existing signature schemes are based on big integer factorization and discrete logarithm problem. But with the development and implementation of quantum technology， these schemes will be cracked by quantum computation attacks. We proposed a signature scheme based on LWE problem and its security is based on solving lattice problem in worst case. So， our scheme is good at anti-quantum attack.

Key words： lattice； digital signature scheme； LWE； public key cryptosystem； hash function

1 引言

計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的發(fā)展將人類帶入信息化社會(huì)，隨之而來的是備受關(guān)注的信息安全問題?，F(xiàn)代密碼學(xué)已成為信息安全技術(shù)的核心，數(shù)字簽名是現(xiàn)代密碼學(xué)主要研究的內(nèi)容之一。數(shù)字簽名技術(shù)在身份識(shí)別和認(rèn)證、數(shù)據(jù)完整性、抗抵賴等方面具有其他技術(shù)所無法替代的作用，它在電子商務(wù)和電子政務(wù)等領(lǐng)域有著極其廣泛的應(yīng)用。[1]數(shù)字簽名技術(shù)能夠進(jìn)行技術(shù)驗(yàn)證，這是書寫簽名與印章簽名所不具有的優(yōu)點(diǎn)。數(shù)字簽名技術(shù)不僅具有更強(qiáng)的操作性、更加成熟的技術(shù)，而且也是應(yīng)用最為廣泛的電子簽名方法，其程序更加規(guī)范與科學(xué)，能夠準(zhǔn)確地驗(yàn)證相關(guān)電子文件數(shù)據(jù)在傳輸?shù)倪^程中是否被改動(dòng)，從而使電子文件的真實(shí)性、完整性以及其不可抵賴性得到有效保證。數(shù)字簽名在電子數(shù)據(jù)內(nèi)容的認(rèn)可以及對簽名人身份的驗(yàn)證方面應(yīng)用得也比較多。數(shù)字簽名能夠有效地避免出現(xiàn)收件人在收到信息之后又對其進(jìn)行否認(rèn)，或者是對偽造信息進(jìn)行發(fā)送以及信息修改[2]等問題，對于信息安全防護(hù)、實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)的保密性、完整性、不可抵賴性有著重要的作用。

數(shù)字簽名就是一段數(shù)字串，它是非對稱密鑰加密技術(shù)與數(shù)字摘要技術(shù)的應(yīng)用，是公開密鑰加密技術(shù)與報(bào)文分解函數(shù)相結(jié)合的產(chǎn)物，其特點(diǎn)是只有信息的發(fā)送者才可以產(chǎn)生，除此之外，任何人不能對其進(jìn)行偽造，這段數(shù)字串能夠?qū)Πl(fā)送者信息進(jìn)行確認(rèn)。它的安全性是基于某種數(shù)學(xué)難題，而在數(shù)字簽名中都是基于傳統(tǒng)的大整數(shù)分解問題和離散對數(shù)問題等困難問題。隨著量子計(jì)算的發(fā)展，現(xiàn)在已經(jīng)出現(xiàn)了解決這些困難問題的量子算法，為了避免量子時(shí)代到來后的危機(jī)，研究基于新型困難問題的算法是重中之重。

1996年，Ajtai在提出了一個(gè)開創(chuàng)性的結(jié)論[3]，提出了一個(gè)基于格的公鑰密碼方案，基于某些格問題的任意一個(gè)密碼體制，其安全性等價(jià)于最難情況下的密碼體制的安全性，這個(gè)結(jié)論提供了基于格的公鑰密碼體制的理論基礎(chǔ)。1997年Ajtai和Dwork合作提出了基于格中最難情況下的u-SVP問題的AD加密體制[4]。Lyubashevsky證明其與GapSVP的困難性等價(jià)，從而證明了AD加密體制的安全性，但在實(shí)際應(yīng)用中其存在著運(yùn)算速度太慢和容易被攻破的缺陷。

2005年，Regev [5]首次提出了一類基于LWE（Learning With Error）問題的加密方案[6]，在文中Regev證明了LWE問題的困難性依賴于格上最難情況下的GapSVP問題，從而證明了其安全性。故簡單而又安全的LWE問題常常被用來構(gòu)造基于格的各種加密體制和簽名方案。目前，LWE和SIS兩個(gè)難題假設(shè)是構(gòu)造格公鑰密碼的最實(shí)用的格難題，可證明安全理論的提出和發(fā)展，解決了密碼算法或協(xié)議依靠猜想設(shè)計(jì)并反復(fù)修補(bǔ)漏洞的缺陷，將破解密碼算法或協(xié)議的難度規(guī)約到解決“極微本原”難題，從而能夠可靠地保證方案的安全性。本項(xiàng)目通過對于格技術(shù)的分析選取了LWE技術(shù)。

LWE加密技術(shù)方案與數(shù)字簽名是本項(xiàng)目的主要研究對象，借鑒基于LWE的多比特IBE類和多比特BGN類及其他LWE方案，在理論和實(shí)際應(yīng)用上進(jìn)行更深入的研究和拓展。

而基于格的公鑰密碼算法是后量子密碼中的典型代表，基于格的密碼算法，其安全性是基于最壞情況難解性的，相比于平均情況下難解性會(huì)更安全些，并且其可以抵抗量子攻擊。同時(shí)基于格的密碼算法系統(tǒng)相對高效且易于實(shí)現(xiàn)。

基于LWE技術(shù)的數(shù)字簽名方案，主要在數(shù)字簽名中運(yùn)用格技術(shù)中的LWE技術(shù)使其擁有抵御量子攻擊的能力，并提高其有效性，安全性及效率。數(shù)字簽名的主要過程：將摘要信息與發(fā)送者的私鑰加密，與原文一起傳送給接收者。接收者只有用發(fā)送者的公鑰才能解密被加密的摘要信息，然后用HASH函數(shù)對收到的原文產(chǎn)生一個(gè)摘要信息，與解密的摘要信息對比。如果相同，則說明收到的信息是完整的，在傳輸過程中沒有被修改，否則說明信息被修改過。

本文主要研究內(nèi)容如下：

（1）在現(xiàn)有的數(shù)字簽名方案中，將具有高效性、安全性、可抵御量子攻擊特性的LWE加密技術(shù)融入其中，使其在性能，安全，效率等多方面得到其提升。

（2）完成數(shù)字簽名過程的解析與實(shí)施，探究LWE技術(shù)融入的方向。

（3）研究私鑰加密的過程中是如何結(jié)合LWE技術(shù)的加密機(jī)理。

（4）對比LWE技術(shù)中多個(gè)加密方案分類，探究并選取其中安全性與高效性最佳的方案進(jìn)行實(shí)施。

（5）在研究完成后的加密方案中，設(shè)法在不影響安全性的情況下，從下面三個(gè)角度改進(jìn)現(xiàn)有方案：①密鑰及密文長度；②空間復(fù)雜性；③計(jì)算復(fù)雜性。

2 預(yù)備知識(shí)

4 基于LWE的數(shù)字簽名的實(shí)現(xiàn)

（1）sender 對目標(biāo)信息m使用hash函數(shù)加密；

（2）再對加密后的目標(biāo)信息m和私鑰使用sign函數(shù)生成信息；

（3）將目標(biāo)信息m和該信息發(fā)送到receiver；

（4）receiver接收信息后，對m使用hash函數(shù)，并將它與sender發(fā)送的信息與公鑰一起使用verify函數(shù)；

（5）使用verify函數(shù)后，若為true，則表示受到的信息是由發(fā)送方發(fā)出，為false則不是由發(fā)送方發(fā)出。

上述過程如圖1所示。

5 結(jié)束語

基于LWE技術(shù)的數(shù)字簽名方案，主要在數(shù)字簽名中運(yùn)用格技術(shù)中的LWE技術(shù)使其擁有抵御量子攻擊的能力，并提高其有效性，安全性及效率。數(shù)字簽名的主要過程：將摘要信息與發(fā)送者的私鑰加密，與原文一起傳送給接收者。接收者只有用發(fā)送者的公鑰才能解密被加密的摘要信息，然后用HASH函數(shù)對收到的原文產(chǎn)生一個(gè)摘要信息，與解密的摘要信息對比。

基于格的密碼算法，其安全性是基于最壞情況難解性的，相比于平均情況下難解性會(huì)更安全些，并且其可以抵抗量子攻擊。同時(shí)基于格的密碼算法系統(tǒng)相對高效且易于實(shí)現(xiàn)。這已經(jīng)成為后量子時(shí)代密碼算法系統(tǒng)的有力競爭者。

參考文獻(xiàn)：

[1] 趙維武，王維.數(shù)字證書驗(yàn)證系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].實(shí)驗(yàn)技術(shù)與管理， 2008，25（1）：1-1.

[2] GOLDWASSER S， MICALI S， RIVEST R L. A digital signature scheme secure against chosen-message attacks[J]. SIAM joumal on computing， 1988，17（2）：281-308.

[3] M.Ajtal. Generating hard instances of lattice Problems （extended abstract）[C]. In STOC， 1996：99-108.

[4] AjtaiM， Dwork C. A public-key cryptosystem with worst-case/average-case equivalence[C]//ACM Symposium on Theory of Computing（STOC）. EI Paso：ACM Press， 1997：284-293.

[5] Regev O. On Lattices， Learning with Errors，Random Linear Codes， and Cryptography[J]. Journal of the Association for Computing Machincry， 2009，56（6）：1-40.

[6] Daniele Micciancio and OdedRegev. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM- J. Comput. Preliminary version in FOCS 2004，37（1）：267-302.

[7] LyubashevskyV， PeikertC， RegevO. On ideal lattices and learning with errors over rings[C]//Crypto10.French Riviera：Springer， 2010：1-23.

[8] REGEV O.Onlattices，learning with errors，random linear codes，and cryptography[J]. Journal of the ACM（JACM）， 2009，56（6）：34.