Q1：傳統(tǒng)公鑰密碼面臨的挑戰(zhàn)
(1)安全性挑戰(zhàn):Shor量子分解算法利用量子計(jì)算的并行性，對任意大的整數(shù)進(jìn)行快速因子分解，大大降低目前普遍使用的RSA算法的破解時(shí)間。隨后又出現(xiàn)了針對基于離散對數(shù)問題的量子求解算法。這些量子算法的提出意味著只要出現(xiàn)實(shí)際的量子計(jì)算機(jī)，現(xiàn)有的以傳統(tǒng)公鑰密碼為基石建立的安全系統(tǒng)將喪失所有的安全性。

(2)效率挑戰(zhàn):傳統(tǒng)公鑰密碼算法的密鑰長度一直在增加，使得傳統(tǒng)密碼算法碼效率很低。通過尋找具有更簡單運(yùn)算的數(shù)學(xué)難題，來降低加解密操作的復(fù)雜性，有代表性的是基于格的密碼系統(tǒng)，其基本運(yùn)算為矢量的加法和乘法。和RSA相比，橢圓曲線算法盡管密鑰和密文較短，但在橢圓曲線加法群上所進(jìn)行的操作還是十分復(fù)雜，效率改善不大。
Q2格密碼的定義
格是n維線性空間中離散點(diǎn)的集合,格中的每個元素都是一個向量。在n維線性空間中m(m≤n)個線性無關(guān)的向量(b1,b2,…,bm)所生成的向量集合稱為格。向量組(b1,b2,…,bm)稱為格的一組基;格的基中的向量個數(shù)稱為格的維數(shù);同一個格可以有多組不同的基,但是基的維數(shù)相同。

上圖中的格密碼以v1與v2為基，空間中所有的點(diǎn)都可以用v1,v2線性表示出來。（真實(shí)空間中的點(diǎn)是無窮的）
Q3:格上的困難問題
格密碼的主要數(shù)學(xué)基礎(chǔ)是格中的兩個困難問題:
(1)格的最短矢量問題(SVP):對于給定的一組基,找出其所生成的格中歐氏距離（兩點(diǎn)之間的距離）最小的非零向量。
即在格上找到一個非零向量v,滿足對格上的任意非零向量u,均有||v||≤||u||。
(2)格的最近矢量問題(CVP):對于給定的格及任一向量,找出格中與該向量距離最近的向量。
即在格上找到一個向量v,滿足對格上的任意非零向量u,均有||v-y||≤||u-y||。
格上的困難問題在代數(shù)上是很好解決的，但在幾何上是困難的
Q4：格密碼的優(yōu)勢
基于格的密碼系統(tǒng)是后量子計(jì)算時(shí)代的密碼候選方案之一。
(一)由于格的最短矢量問題(SVP)和格的最近矢量問題(CVP)被證明在隨機(jī)歸約下均屬于NP-hard類問題。即某一類格中一些問題的平均難度等價(jià)于格上一類NP問題的難度。因此,在這些格問題基礎(chǔ)上構(gòu)建的公鑰密碼體制,其任意一個實(shí)例的安全性與其最難實(shí)例的安全性相同;
(二)由于格是一種線性結(jié)構(gòu),格上的運(yùn)算大多是線性運(yùn)算,因此利用格難題所構(gòu)建的新型公鑰密碼體質(zhì)比現(xiàn)有方案運(yùn)算速度更快;
(三)目前還不存在解決某些格困難問題的多項(xiàng)式量子算法,因此,基于格難題所設(shè)計(jì)的新型公鑰密碼體質(zhì)可以抵御量子攻擊。
Q5：LWE算法
LWE算法與最壞情況下的格問題一樣難，而最壞情況下的格問題被認(rèn)為是指數(shù)級難(即使面對的是量子計(jì)算機(jī))。

這里的圖可以轉(zhuǎn)化為符號表示：
As+e=b;根據(jù)圖上所示A與b是已知的，e是很小的數(shù)（相當(dāng)于噪聲），s是秘鑰。
如果沒有隨機(jī)產(chǎn)生的噪聲e，就是一個簡單的線性問題，求出秘鑰很簡單，但是增加了e，問題就變成了NP問題。
LWE問題(Learning With Errors)是一個格上的平均性困難問題，可以被歸約到格的SVP等困難問題,也是抗量子的。目前主流的格上加密方案都是構(gòu)建在LWE之上。
Q6:LWE算法的基本思想

1）取一個隨機(jī)向量為秘鑰s；
2）矩陣A,向量b已知，e為很小的分布且e的模遠(yuǎn)小于q；
3）通過b=As+e%q 最后計(jì)算s的值。
Q7:計(jì)算s的方法
NP-hard問題（NP是指非確定性多項(xiàng)式（non-deterministic polynomial，縮寫NP）。所謂的非確定性是指，可用一定數(shù)量的運(yùn)算去解決多項(xiàng)式時(shí)間內(nèi)可解決的問題。）：任意NP問題都可以在多項(xiàng)式時(shí)間內(nèi)歸約為該問題，但該問題本身不一定是NP問題。歸約的意思是為了解決問題A，先將問題A歸約為另一個問題B，解決問題B同時(shí)也間接解決了問題A.

1)現(xiàn)給定一個b與A已知，目的為求s；
2）選擇一個確定的值r，使得b’=Ar+b(此式子中所有參數(shù)都已知)
3)把b=As+e帶入上式
4）b’=A(r+s)+e(mod q)
5)s’=r+s---->b’=As’+e
6)解出s’后即可解出s
Q8:LWE的加密過程

Q9：傳統(tǒng)的秘鑰交換算法（DH算法）
傳統(tǒng)密鑰交換算法(DH算法):基于有限域上的離散對數(shù)難題,通過DH算法進(jìn)行密鑰分配，使得消息的收發(fā)雙方可以安全地交換一個密鑰，再通過這個密鑰對數(shù)據(jù)進(jìn)行加密和解密處理。

Q10：基于格的密鑰交換方案
基于LWE問題構(gòu)造的被動安全密鑰交換協(xié)議:與傳統(tǒng)DH協(xié)議類似,稱為LDH協(xié)議,執(zhí)行流程如下：

用戶A作為發(fā)送者,用戶B作為接受者。
協(xié)議執(zhí)行之后,雙方會完成交換一個會話密鑰。
LDH協(xié)議正確性:

Q11:實(shí)例
基于格的統(tǒng)計(jì)零知識證明的一個案例過程:


1）首先rs與re是隨機(jī)的,前者相當(dāng)于秘鑰，后者相當(dāng)于噪聲。
2）t,a屬于已知且整個過程不發(fā)生變化
3）從V方傳來的c的作用相當(dāng)于一個隨機(jī)變量，是不確定的。其目的是即如果P方證明成功，則不管V方傳來什么參數(shù)，等式都應(yīng)該是成立的；

總結(jié)

以上是生活随笔為你收集整理的基于格密码的算法研究的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。