何彥雨 楊光

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

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

一、“格”概念的引入

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、格計算的公鑰密碼體制的研究無止境

本文簡單介紹了以格計算為基礎(chǔ)的公鑰密碼體制。對該密碼學(xué)研究方案和數(shù)字證書和協(xié)議的設(shè)計來說，我們怎樣在保全安全強度足夠高的條件下，進一步提高信息安全的實現(xiàn)效率，達到當(dāng)今我國規(guī)定的相應(yīng)的信息安全標(biāo)準(zhǔn)，還應(yīng)該進行深一步的研究工作。

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

參 考 文 獻

[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.