基于格計(jì)算的公鑰密碼算法研究概述

何彥雨 楊光

【摘要】 格（lattice）作為一種特殊的偏序集，是n維線(xiàn)性空間中具有周期結(jié)構(gòu)的離散加法子群。公鑰密碼的產(chǎn)生在整個(gè)密碼學(xué)研究中有著重要的意義，自1997年Ajtai和Dwork提出AD97加密系統(tǒng)之后，便誕生了許多基于格計(jì)算的公鑰密碼算法。格困難的公鑰密碼算法研究在當(dāng)今社會(huì)廣泛應(yīng)用于抗量子攻擊密碼（數(shù)字簽名、全同態(tài)加密等）等方面的研究。本文從格的基本概念出發(fā)，概述了基于格困難問(wèn)題的公鑰密碼算法研究現(xiàn)狀等內(nèi)容。

【關(guān)鍵詞】 格密碼 公鑰密碼體制 計(jì)算復(fù)雜性

一、“格”概念的引入

格這個(gè)概念最早由Guass提出，已經(jīng)有200多年的歷史。經(jīng)過(guò)幾代人的研究和發(fā)展終于演變成為一門(mén)數(shù)學(xué)理論學(xué)科。傳統(tǒng)的密碼已經(jīng)不能保證信息數(shù)據(jù)的安全性，于是人們尋求更有效的新型密碼結(jié)構(gòu)，而格應(yīng)該最可能解決這一難題。

不復(fù)雜的說(shuō)，格（L）是一個(gè)偏序集，是線(xiàn)性空間里一種有周期性、排列有規(guī)則的點(diǎn)集組成的離散加法子群。如果說(shuō)線(xiàn)性無(wú)關(guān)的向量組b1，…，bn構(gòu)成了線(xiàn)性空間中的m維向量（m>n），那么這個(gè)向量組組成的集合成為格，而向量組b1，…，bn成為格的一組基?；赜^定義我們能發(fā)現(xiàn)格有兩個(gè)特點(diǎn)：離散性和基的多樣性。

二、以R-LWE為基礎(chǔ)的數(shù)字簽名方案

R-LWE幾近完美的回應(yīng)了對(duì)于LWE（Learning With Errors）問(wèn)題設(shè)計(jì)中的缺點(diǎn)，也就是對(duì)于其加密方案的開(kāi)銷(xiāo)大而效率低。而R-LWE/∫，q，χ作為R-LWE問(wèn)題的變形假設(shè)，特別對(duì)于其缺點(diǎn)，構(gòu)造了一個(gè)算法高效、密鑰較小和結(jié)構(gòu)簡(jiǎn)單的數(shù)字簽名方案。

完整的數(shù)字簽名方案包含以下幾個(gè)概率多項(xiàng)式時(shí)間算法：密鑰生成算法（Gen）、簽名算法（Sign）和驗(yàn)證算法（Verify）。

基于R-LWE的數(shù)字簽名算法與其余的簽名算法比較可以看出，R-LWE簽名算法中的Gen、Sign和Verify的簽名都相同，即為O（nlogn），其長(zhǎng)度比其他的簽名算法的長(zhǎng)度都要短得多。

但是從實(shí)際出發(fā)來(lái)看，在時(shí)間復(fù)雜度和空間復(fù)雜度方面得到了很大的提升的根本原因是在大多數(shù)情況下R-LWE問(wèn)題假設(shè)中特定環(huán)的特征，從這個(gè)環(huán)任意選擇一個(gè)簽名密鑰，都可以對(duì)有限域Zq中n個(gè)消息中的任意一個(gè)進(jìn)行簽名，這使得R-LWE的數(shù)字簽名算法的時(shí)間復(fù)雜度和空間復(fù)雜度大大降低。

三、基于格計(jì)算的全同態(tài)加密方案

從當(dāng)今密碼學(xué)的研究現(xiàn)狀來(lái)看，全同態(tài)加密方案的加密效率高低與安全性的高低仍然受到密碼學(xué)研究界的質(zhì)疑。所以當(dāng)全同態(tài)加密方案的加密效率與安全性的難題一旦被攻破后，全同態(tài)加密這一高新技術(shù)勢(shì)必會(huì)被應(yīng)用到云計(jì)算的各個(gè)方面。

隨著大數(shù)據(jù)的概念的逐漸推廣，我們即將迎來(lái)云計(jì)算的時(shí)代。但是云計(jì)算中存在很大可能的泄密漏洞，而且這種問(wèn)題日顯嚴(yán)重。

所以，在當(dāng)今的信息安全研究中，進(jìn)一步推進(jìn)云計(jì)算中存在的信息安全技術(shù)尤為重要。以格運(yùn)算為基礎(chǔ)的全同態(tài)加密技術(shù)可以明文上進(jìn)行的任意一種運(yùn)算和相應(yīng)的密文的特定操作對(duì)應(yīng)起來(lái)，也就是說(shuō)，全同態(tài)加密技術(shù)可以對(duì)任意加密的數(shù)據(jù)進(jìn)行運(yùn)算。

下面我們以全同態(tài)的加密技術(shù)的一個(gè)經(jīng)典方案為例介紹一下格計(jì)算的全同態(tài)加密方案的優(yōu)點(diǎn)。

Squashing the Decryption Circuit作為全同態(tài)加密技術(shù)的經(jīng)典方案之一，在信息安全的研究中有著重要的意義。

這項(xiàng)經(jīng)典方案中有一點(diǎn)令人十分詫異，仿佛是存在著一種特殊的“法則”，使我們得不到完整的半同態(tài)的加密方案的結(jié)果。

四、格計(jì)算的公鑰密碼體制的研究無(wú)止境

本文簡(jiǎn)單介紹了以格計(jì)算為基礎(chǔ)的公鑰密碼體制。對(duì)該密碼學(xué)研究方案和數(shù)字證書(shū)和協(xié)議的設(shè)計(jì)來(lái)說(shuō)，我們?cè)鯓釉诒Ｈ踩珡?qiáng)度足夠高的條件下，進(jìn)一步提高信息安全的實(shí)現(xiàn)效率，達(dá)到當(dāng)今我國(guó)規(guī)定的相應(yīng)的信息安全標(biāo)準(zhǔn)，還應(yīng)該進(jìn)行深一步的研究工作。

此外，格作為一種特殊的偏序集，是n維線(xiàn)性空間中具有周期結(jié)構(gòu)的離散加法子群，對(duì)公鑰密碼體制的發(fā)展產(chǎn)生了巨大作用，該課題的研究還會(huì)推動(dòng)相關(guān)數(shù)學(xué)領(lǐng)域的發(fā)展。所以我們應(yīng)該把格困難問(wèn)題為基礎(chǔ)的公鑰密碼體制研究作為一種常態(tài)化研究工作進(jìn)行下去。

參 考 文 獻(xiàn)

[1]A.K.Lenstra， H.W.Lenstra and L.Lovasz. Factoring polynomials with rational coefficients. Mathematische Annalen， 1982，261：515-534.

[2]Babai， L.：On Lovasz lattice reduction and the nearest lattice point problem. Combinatorica 6（1）（1986）1-13 Preliminary version in STACS 1985.