基于格的密碼體制概述

王黎

摘要：本文主要對(duì)基于格的密碼體制進(jìn)行了概述，首先簡述了格基密碼體制的起源，而后分別分析了格基加密體制和格基簽名體制的發(fā)展歷程。

關(guān)鍵詞：格;加密體制;簽名體制

一、引言

格理論在密碼學(xué)中的首次應(yīng)用，是作為一種密碼分析工具。許多非基于格的密碼方案的安全性分析，可歸約到格上的困難問題，進(jìn)而可以利用求解這些困難問題的算法進(jìn)行安全性分析。

二、格基加密體制的發(fā)展概述

1997年，Ajtai和Dwork首次基于格上困難問題構(gòu)造了一個(gè)加密方案——AD加密體制[1]，這是第一個(gè)被證明了的系統(tǒng)中任意實(shí)例的安全性與最難實(shí)例的安全性等價(jià)的密碼方案。此后密碼學(xué)者又陸續(xù)提出了GGH密碼體制[2]和NTRU公鑰密碼體制。

2005年，Regrev提出了格上帶差錯(cuò)的學(xué)習(xí)問題，并證明了其復(fù)雜性可歸約到格上的Gap-SVP和SIVP問題的困難性上。基于LWE問題，Regrev設(shè)計(jì)出了一個(gè)選擇明文攻擊安全的格基加密算法。隨后，大量基于格的公鑰密碼算法被提出，并且隨著研究的深入，格基加密方案的安全性越來越高。2008年，Peikert和Waters設(shè)計(jì)出了第一個(gè)選擇密文攻擊安全的加密方案，其后Peikert在2009年基于LWE問題并結(jié)合混合加密的設(shè)計(jì)思想給出了第二個(gè)格基CCA安全的加密方案。

格基密碼的另一重大突破出現(xiàn)在2009年，Gentry在理想格上實(shí)現(xiàn)了全同態(tài)加密方案的構(gòu)造，從而解決了困擾密碼學(xué)者三十多年的公開難題，并且在云計(jì)算、云存儲(chǔ)日益盛行的今天，有著廣闊的應(yīng)用和發(fā)展前景。

三、格基數(shù)字簽名體制的發(fā)展概述

格基數(shù)字簽名體制的發(fā)展大體可以分為兩個(gè)階段。在第一個(gè)發(fā)展階段，主要是基于NTRU格的困難性設(shè)計(jì)出了多個(gè)NTRU簽名方案，如：NSS，R-NSS和NTRUSign等。2001年，NTRU的設(shè)計(jì)者提出了NSS簽名算法，但該算法存在重大缺陷。隨后其設(shè)計(jì)者J.Hoffstein等人對(duì)其進(jìn)行改進(jìn)并提出了R-NSS簽名算法。2008年，胡予濮教授提出了一種新的NTRU數(shù)字簽名方案，新方案同時(shí)具備NSS算法的簡潔性和NTRUSign算法的安全性。

隨著2008年Gentry等人在文章中提出了原像抽樣函數(shù)的概念，并借助PSF設(shè)計(jì)出首個(gè)隨機(jī)預(yù)言機(jī)模型下可證明安全的格基數(shù)字簽名方案，格基數(shù)字簽名進(jìn)入到了快速發(fā)展的第二階段。

2010年，Cash等人提出了盆景樹模型的概念，并基于盆景樹模型構(gòu)造了一個(gè)標(biāo)準(zhǔn)模型下可證明安全的數(shù)字簽名方案，但是盆景樹模型的結(jié)構(gòu)特點(diǎn)使得方案的公鑰和簽名的長度以及空間復(fù)雜度都很大，并且方案是EU-sCMA安全的。然而，盆景樹模型卻為密碼學(xué)者構(gòu)造具有特殊性質(zhì)的數(shù)字簽名算法提供很好的思路，并取得了大量的研究成果。同年，Boyen提出一個(gè)更加高效的格基數(shù)字簽名方案。Boyen提出了雙邊陷門的概念，并使用消息選擇技術(shù)使得簽名長度顯著減小。而Agrawal等人設(shè)計(jì)出了一種固定維數(shù)的格基委派算法，與盆景樹模型相比，該算法通過選擇合適的矩陣，利用矩陣乘而不是矩陣的級(jí)聯(lián)進(jìn)行擴(kuò)展，保證了擴(kuò)展后的格與上一級(jí)格具有相同的維數(shù)，進(jìn)而使得公鑰和簽名長度減小。值得一提的是上述方案都是以PSF為基礎(chǔ)的，因而構(gòu)造出好的陷門生成函數(shù)一直是格基數(shù)字簽名的一個(gè)重要研究方向。2011年，Alwen和Peikert對(duì)Ajtai陷門生成算法進(jìn)行了改進(jìn)。2012年，Micciancio和Peikert在歐密會(huì)上提出了一個(gè)新的陷門生成算法，與之前的算法相比，該算法更加簡單高效。在其基礎(chǔ)上，Micciancio等人提出了新的原像抽樣算法和陷門委托算法，進(jìn)而構(gòu)造了一個(gè)高效的格基數(shù)字簽名算法，并在標(biāo)準(zhǔn)模型下對(duì)方案的強(qiáng)不可偽造性進(jìn)行了證明。

另一方面，Lyubashevsky借助Fiat-Shamir模型構(gòu)造出了一種無陷門的格基簽名方案，方案通過使用拒絕性采樣來生成簽名，其安全性可歸約到SIVP問題的困難性上。并且通過改變參數(shù)，方案可以轉(zhuǎn)變成一個(gè)更加高效的基于LWE問題的數(shù)字簽名方案。相比于基于陷門構(gòu)造的簽名方案，Lyubashevsky的方案結(jié)構(gòu)更加簡單，密鑰和簽名更短，并且只需進(jìn)行矩陣乘法和拒絕性采樣運(yùn)算，因而效率更高。

四、結(jié)束語

在大數(shù)據(jù)時(shí)代，數(shù)據(jù)的價(jià)值越來越重要，而其安全性遭受到各種威脅，因而研究出高效安全的加密及簽名算法顯得及其重要。

參考文獻(xiàn)：

[1]Ajtai?M，Dwork?C.A?public-key?cryptosystem?with?worst-case/?average-case?equivalence[C].Proceedings?of?the?twenty-ninth?annual?ACM?symposium?on?Theory?of?computing.ACM，1997：284-293.

[2]Goldreich?O，Goldwasser?S，Halevi?S.Collision-free?hashing?from?lattice?problems[C].Electronic?Colloquium?on?Computational?Complexity?（ECCC）.1996，3（42）：236-241.

[3]Goldreich?O，Goldwasser?S，Halevi?S.Collision-free?hashing?from?lattice?problems[C].Electronic?Colloquium?on?Computational?Complexity?（ECCC）.1996，3（42）：236-241.

[4]Nguyen?P.Cryptanalysis?of?the?Goldreich-Goldwasser-Halevi?cryptosystem?from?crypto’97[C].Advances?in?Cryptology—CRYPTO’?99.Springer?Berlin?Heidelberg，1999：288-304.