基于格計算的公鑰密碼算法研究概述

何彥雨 楊光

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

【關鍵詞】 格密碼 公鑰密碼體制 計算復雜性

一、“格”概念的引入

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

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

二、以R-LWE為基礎的數字簽名方案

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

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

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

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

三、基于格計算的全同態加密方案

從當今密碼學的研究現狀來看，全同態加密方案的加密效率高低與安全性的高低仍然受到密碼學研究界的質疑。所以當全同態加密方案的加密效率與安全性的難題一旦被攻破后，全同態加密這一高新技術勢必會被應用到云計算的各個方面。

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

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

下面我們以全同態的加密技術的一個經典方案為例介紹一下格計算的全同態加密方案的優點。

Squashing the Decryption Circuit作為全同態加密技術的經典方案之一，在信息安全的研究中有著重要的意義。

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

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

本文簡單介紹了以格計算為基礎的公鑰密碼體制。對該密碼學研究方案和數字證書和協議的設計來說，我們怎樣在保全安全強度足夠高的條件下，進一步提高信息安全的實現效率，達到當今我國規定的相應的信息安全標準，還應該進行深一步的研究工作。

此外，格作為一種特殊的偏序集，是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.