-
-
- 銷售咨詢：
- TEL:021-6125 9080
-
被喻(yu)為(wei)“重(zhong)要數(shu)據保險箱”的(de)(de)安全(quan)芯(xin)片(pian)已經(jing)滲入人們生活(huo)的(de)(de)方方面(mian)面(mian)。隨著5G、物聯網(wang)、車聯網(wang)的(de)(de)迅速發展(zhan)，為(wei)安全(quan)芯(xin)片(pian)開啟了(le)新(xin)的(de)(de)應用場景，同(tong)時也帶來了(le)新(xin)的(de)(de)挑(tiao)戰(zhan)。
本(ben)文將帶大家深入了解安(an)全芯片的(de)核心，后量(liang)子密(mi)碼認證技(ji)術。
安全(quan)認(ren)證技術概述
安全認(ren)(ren)證技(ji)術是防止信息被篡(cuan)改、刪除、重(zhong)放和(he)偽造的(de)一種有(you)效方法。它(ta)使接(jie)收者能夠(gou)識別和(he)確認(ren)(ren)消息的(de)來源和(he)真偽。目前認(ren)(ren)證技(ji)術主要有(you)4種：
（1）數字摘要
（2）數字(zi)摘要+對(dui)稱密鑰認證
（3）數字摘(zhai)要+非對稱密(mi)鑰認證
（4）數字證書認(ren)證
不過隨著量子(zi)計算機的(de)(de)發展，現(xian)有的(de)(de)絕(jue)大(da)(da)多數公(gong)鑰密(mi)碼(ma)(ma)算法（RSA、Diffie-Hellman、橢圓曲線等）能被(bei)足夠大(da)(da)和穩定(ding)的(de)(de)量子(zi)計算機攻破，也(ye)就是(shi)說(shuo)目前基(ji)(ji)于非對稱(cheng)密(mi)鑰的(de)(de)認證技(ji)(ji)術(shu)都不安全(quan)，會(hui)被(bei)攻破。所以需要研究基(ji)(ji)于后(hou)量子(zi)密(mi)碼(ma)(ma)的(de)(de)認證技(ji)(ji)術(shu)。
1.1 數字摘要(yao)
該技術就是使(shi)用(yong)單向的(de)HASH函(han)數將需發(fa)送(song)的(de)消息摘要成為(wei)一串固定(ding)長度的(de)數據，然后發(fa)送(song)給接收方(fang)。
具體步驟如(ru)下：
（1）使用Hash函數(shu)計算消息的(de)摘要(yao)，將(jiang)其與消息一起發(fa)送。
（2）當Bob收到消息，使用(yong)同(tong)樣(yang)算(suan)法(fa)計算(suan)摘要，與(yu)收到的摘要進行(xing)比較。
主要優點：
（1）對消息的任何改變，摘要必然變化(hua)。
（2）單向函數：無法從摘(zhai)要(yao)構造出原文(wen)。
主要(yao)缺(que)點：
（1）僅僅Hash沒(mei)法保證(zheng)完整性。
（2）改變這個消(xiao)息，重新計(ji)算摘要(yao)，用改變后的消(xiao)息+摘要(yao)替換原來(lai)的報文。
1.2 數(shu)字摘要+對稱密鑰認證
該技(ji)術就是使用共享(xiang)的對稱密鑰加密隨機(ji)數，再使用HASH函數將密文(wen)信息摘要成為一串固定長度的數據，然后發(fa)送(song)給接收方。
具體步驟如(ru)下：
（1）通過安全通道，Bob和Alice共享(xiang)一個(ge)密鑰。
（2）Bob發送一個隨機(ji)數給Alice。
（3）Alice用共享密(mi)鑰加密(mi)隨機數，并對加密(mi)結果(guo)進行(xing)HASH運算，HASH值發送(song)給Bob。
（4）Bob也用共享密(mi)鑰(yao)加密(mi)隨機數(shu)，并對加密(mi)結(jie)果(guo)進行(xing)HASH運算，計算的(de)結(jie)果(guo)與接收的(de)HASH進行(xing)比較，相等則表示是(shi)Alice發送過來的(de)。
主要優點：
（1）在確保密(mi)鑰安(an)全下(xia)，可以防止信(xin)息被篡改。
（2）分組加密(mi)性能快。
主要缺點(dian)：
（1）需要通過安全通道共享密鑰。
（2）雙(shuang)方(fang)(fang)都保存密(mi)鑰，只(zhi)要(yao)一方(fang)(fang)泄漏密(mi)鑰即可破(po)解信(xin)息。
1.3 數字摘要+非對稱(cheng)密鑰認證
該技(ji)術就是使用自己(ji)的私鑰對(dui)發送信息進行簽(qian)名，然后接收方使用公鑰驗證這(zhe)個簽(qian)名。
具(ju)體步驟如下：
（1）Bob拿到Alice的公鑰(yao)，發(fa)送一個隨(sui)機數(shu)給(gei)Alice。
（2）Alice收到(dao)隨機數后用自己的私鑰進去簽(qian)名，簽(qian)名結果(guo)發(fa)送給Bob。
（3）Bob使(shi)用Alice的公鑰對接收的簽名進行(xing)驗簽，如果(guo)驗簽通過則確認是Alice發(fa)出來(lai)的信息。
主要優點(dian)：
（1）公鑰可以公開(kai)，無需保密。
（2）只需發(fa)送方保存自(zi)己的(de)私鑰(yao)。
主要(yao)缺(que)點(dian)：
（1）如何確定公鑰來自Alice？易受中間人(ren)攻擊。
1.4 數(shu)字證書認證
該技術就是需(xu)要有(you)一個CA（可信(xin)的授權中心），發(fa)(fa)送(song)方Alice從CA申請(qing)證(zheng)書，CA確認Alice確實(shi)是Alice，生成和(he)發(fa)(fa)布Alice的證(zheng)書。Alice的證(zheng)書包含：
· 主題Subject：需要鑒別的個人Alice
· Alice的公鑰public key
· 數字(zi)簽名digital signature：CA對證書的簽名
· 發布者Issuer：驗證了信(xin)息并發布證書的實(shi)體
· 簽名算法Signature Algorithm
具體步驟如(ru)下：
（1）Bob申請(qing)Alice的證書公鑰(yao)。
（2）Alice把自己的證書發送給(gei)Bob，Bob收(shou)到后使(shi)用CA公鑰(yao)驗證證書，并(bing)獲(huo)取(qu)得到Alice的公鑰(yao)。
（3）Bob拿到Alice的公鑰(yao)后，發送一個隨機數給Alice。
（4）Alice收到隨(sui)機(ji)數(shu)后用(yong)自己的私鑰進去簽(qian)名，簽(qian)名結果發(fa)送給Bob。
（5）Bob使(shi)用Alice的(de)公鑰對接(jie)收(shou)的(de)簽(qian)名進行驗(yan)簽(qian)，如(ru)果驗(yan)簽(qian)通過則確認是(shi)Alice發出來的(de)信息。
主要優點：
（1）可以抵抗中間人攻擊，確認Alice的公鑰(yao)。
主要(yao)缺點：
（1）無法抵抗量子(zi)計(ji)算機攻擊。
后(hou)量子密碼算法(fa)概述
后(hou)量(liang)子(zi)密(mi)(mi)碼(ma)是能夠抵(di)抗量(liang)子(zi)計(ji)算機對現(xian)有密(mi)(mi)碼(ma)算法攻(gong)擊(ji)的新一代密(mi)(mi)碼(ma)算法。實現(xian)后(hou)量(liang)子(zi)密(mi)(mi)碼(ma)算法主(zhu)要有以下(xia) 4 種(zhong)途徑 ：
（1）基于哈希 (Hash-based)：最(zui)早出現于1979 年，主要用于構造(zao)數字簽(qian)名。代表算法：Merkle 哈希樹簽(qian)名、XMSS、Lamport 簽(qian)名等。
（2）基于編碼(ma) (Code-based)：最(zui)早出現(xian)于1978 年，主(zhu)要(yao)用于構造加密算(suan)法，代(dai)表算(suan)法：McEliece。
（3）基(ji)于多(duo)變量（Multivariate-based）：最早(zao)出現于1988年，主要(yao)用(yong)于構造數字簽名(ming)、加密、密鑰交(jiao)換等。代表方(fang)法(fa)(fa)/算法(fa)(fa)：HFE (Hidden Field Equations)、Rainbow (Unbalanced Oil and Vinegar (UOV) 方(fang)法(fa)(fa))、HFEv- 等。
（4）基于(yu)(yu)格（Lattice-based）：最早出(chu)現于(yu)(yu)1996 年，主要用于(yu)(yu)構造加(jia)密(mi)、數字簽名、密(mi)鑰交換，以(yi)及眾(zhong)多高(gao)級密(mi)碼(ma)學應用，如：屬性加(jia)密(mi) (Attribute-based encryption)、陷(xian)門函數 (Trapdoor functions)、偽(wei)隨機函數 (Pseudorandom functions)、同態加(jia)密(mi) (Homomorphic Encryption) 等(deng)。代(dai)表算法：NTRU 系列、NewHope (Google 測試過(guo)的)、一系列同態加(jia)密(mi)算法 (BGV、GSW、FV 等(deng))。由于(yu)(yu)其計算速度快、通信開銷較小(xiao)，且能被用于(yu)(yu)構造各類(lei)密(mi)碼(ma)學算法和應用，因此被認為是最有希望(wang)的后量子密(mi)碼(ma)技術(shu)。
當參數選取適當時，目前沒有已知的經典和量子算法可以快速(su)求解這些問(wen)題。
再次(ci)強調，這些(xie)算(suan)法(fa)的(de)(de)安全性，依賴于有沒有可(ke)以快速求解其(qi)底層數學問題或(huo)直(zhi)接對(dui)算(suan)法(fa)本身的(de)(de)高效攻擊算(suan)法(fa)。這也正是(shi)量子(zi)計算(suan)機對(dui)于公鑰密碼算(suan)法(fa)有很(hen)大威脅(xie)的(de)(de)原(yuan)因。
除這4種(zhong)問題(ti)之外(wai)，還有基(ji)于超奇異(yi)橢圓曲線 (Supersingular elliptic curve isogeny)、量子隨機(ji)漫步 (Quantum walk) 等(deng)技術的(de)后量子密(mi)碼(ma)構造方法。另外(wai)，對稱(cheng)密(mi)碼(ma)算法在密(mi)鑰長度較大(da)時 (例如 AES-256)，也可被認為是后量子安全的(de)。
為(wei)什么(me)上(shang)面列的(de)(de) 4 種是最(zui)(zui)重要的(de)(de)？因(yin)為(wei)這(zhe) 4 類途(tu)徑是最(zui)(zui)能(neng)構造出公鑰密碼學中已(yi)有的(de)(de)各類算(suan)法的(de)(de)后量子版本，甚至還能(neng)超越(yue)（例(li)如基(ji)于格的(de)(de)(全(quan))同(tong)態加密）等。
1.1 基于哈希(xi) (Hash-based)
基(ji)(ji)于(yu)(yu)哈(ha)(ha)(ha)(ha)希(xi)(xi)的(de)(de)(de)(de)(de)簽名(ming)算法(fa)(fa)由(you)(you) Ralph Merkel 提出(chu)，被(bei)認為(wei)是傳統數字(zi)簽名(ming) (RSA、DSA、ECDSA 等 ) 的(de)(de)(de)(de)(de)可(ke)行代替算法(fa)(fa)之(zhi)一(yi)。基(ji)(ji)于(yu)(yu)哈(ha)(ha)(ha)(ha)希(xi)(xi)的(de)(de)(de)(de)(de)簽名(ming)算法(fa)(fa)由(you)(you)一(yi)次性(xing)簽名(ming)方(fang)案演(yan)變而來，并(bing)使用(yong) Merkle 的(de)(de)(de)(de)(de)哈(ha)(ha)(ha)(ha)希(xi)(xi)樹(shu)(shu)認證機(ji)制。哈(ha)(ha)(ha)(ha)希(xi)(xi)樹(shu)(shu)的(de)(de)(de)(de)(de)根是公(gong)鑰(yao)，一(yi)次性(xing)的(de)(de)(de)(de)(de)認證密鑰(yao)是樹(shu)(shu)中(zhong)的(de)(de)(de)(de)(de)葉子節點(dian)。基(ji)(ji)于(yu)(yu)哈(ha)(ha)(ha)(ha)希(xi)(xi)的(de)(de)(de)(de)(de)簽名(ming)算法(fa)(fa)的(de)(de)(de)(de)(de)安全性(xing)依賴(lai)哈(ha)(ha)(ha)(ha)希(xi)(xi)函(han)數的(de)(de)(de)(de)(de)抗碰(peng)撞性(xing)。由(you)(you)于(yu)(yu)沒有有效的(de)(de)(de)(de)(de)量子算法(fa)(fa)能快(kuai)速找到哈(ha)(ha)(ha)(ha)希(xi)(xi)函(han)數的(de)(de)(de)(de)(de)碰(peng)撞，因(yin)此(ci)（輸(shu)出(chu)長(chang)度足(zu)夠(gou)長(chang)的(de)(de)(de)(de)(de)）基(ji)(ji)于(yu)(yu)哈(ha)(ha)(ha)(ha)希(xi)(xi)的(de)(de)(de)(de)(de)構造可(ke)以(yi)(yi)抵抗量子計算機(ji)攻擊。此(ci)外，基(ji)(ji)于(yu)(yu)哈(ha)(ha)(ha)(ha)希(xi)(xi)的(de)(de)(de)(de)(de)數字(zi)簽名(ming)算法(fa)(fa)的(de)(de)(de)(de)(de)安全性(xing)不(bu)依賴(lai)某一(yi)個特定的(de)(de)(de)(de)(de)哈(ha)(ha)(ha)(ha)希(xi)(xi)函(han)數。即使目前使用(yong)的(de)(de)(de)(de)(de)某些哈(ha)(ha)(ha)(ha)希(xi)(xi)函(han)數被(bei)攻破(po)，則可(ke)以(yi)(yi)用(yong)更安全的(de)(de)(de)(de)(de)哈(ha)(ha)(ha)(ha)希(xi)(xi)函(han)數直接代替被(bei)攻破(po)的(de)(de)(de)(de)(de)哈(ha)(ha)(ha)(ha)希(xi)(xi)函(han)數。
1.2 基于(yu)編碼 (Code-based)
基(ji)于(yu)編碼(ma)(ma)(ma)的(de)(de)(de)算法使用(yong)錯(cuo)誤糾正(zheng)碼(ma)(ma)(ma)對加(jia)(jia)入的(de)(de)(de)隨(sui)機性錯(cuo)誤進行糾正(zheng)和計算。一個(ge)著名(ming)的(de)(de)(de)基(ji)于(yu)編碼(ma)(ma)(ma)的(de)(de)(de)加(jia)(jia)密算法是 McEliece 。McEliece使用(yong)隨(sui)機二(er)進制的(de)(de)(de)不可約 Goppa碼(ma)(ma)(ma)作為私(si)(si)鑰(yao)(yao)，公鑰(yao)(yao)是對私(si)(si)鑰(yao)(yao)進行變換后的(de)(de)(de)一般線性碼(ma)(ma)(ma)。Courtois、Finiasz 和Sendrier 使用(yong) Niederreiter 公鑰(yao)(yao)加(jia)(jia)密算法構造了(le)基(ji)于(yu)編碼(ma)(ma)(ma)的(de)(de)(de)簽名(ming)方案(an)。基(ji)于(yu)編碼(ma)(ma)(ma)的(de)(de)(de)算法（例如 McEliece）的(de)(de)(de)主要問題是公鑰(yao)(yao)尺寸過(guo)大。基(ji)于(yu)編碼(ma)(ma)(ma)的(de)(de)(de)算法包(bao)括加(jia)(jia)密、密鑰(yao)(yao)交(jiao)換等。
1.3 基于(yu)多變量 (Multivariate-based)
基于多(duo)變(bian)量(liang)(liang)的算法(fa)(fa)使用有(you)限(xian)(xian)域(yu)上(shang)具有(you)多(duo)個(ge)變(bian)量(liang)(liang)的二(er)次(ci)多(duo)項式(shi)(shi)組構造(zao)加密、簽名、密鑰(yao)交換等算法(fa)(fa) 。多(duo)變(bian)量(liang)(liang)密碼(ma)的安全性(xing)依賴于求(qiu)解(jie)(jie)非(fei)線性(xing)方程組的困難(nan)程度，即多(duo)變(bian)量(liang)(liang)二(er)次(ci)多(duo)項式(shi)(shi)問題(ti)。該問題(ti)被證明為非(fei)確定性(xing)多(duo)項式(shi)(shi)時(shi)間困難(nan)。目前沒有(you)已知的經(jing)典和量(liang)(liang)子算法(fa)(fa)可以快(kuai)速(su)求(qiu)解(jie)(jie)有(you)限(xian)(xian)域(yu)上(shang)的多(duo)變(bian)量(liang)(liang)方程組。與經(jing)典的基于數論問題(ti)的密碼(ma)算法(fa)(fa)相比，基于多(duo)變(bian)量(liang)(liang)的算法(fa)(fa)的計算速(su)度快(kuai)，但公(gong)鑰(yao)尺寸較大，因此(ci)適(shi)用于無需(xu)頻繁進行公(gong)鑰(yao)傳輸的應用場(chang)景，例如物聯網設(she)備等。
1.4 基(ji)于格 (Lattice-based)
基于格(ge)的(de)(de)(de)(de)(de)算(suan)(suan)(suan)法(fa)由于在安(an)(an)全(quan)(quan)性(xing)、公私(si)鑰(yao)尺(chi)寸(cun)、計(ji)(ji)算(suan)(suan)(suan)速度(du)上達(da)到了更好的(de)(de)(de)(de)(de)平衡，被認為是最有前景的(de)(de)(de)(de)(de)后(hou)量子密碼(ma)(ma)(ma)算(suan)(suan)(suan)法(fa)之(zhi)一。與基于數論問題的(de)(de)(de)(de)(de)密碼(ma)(ma)(ma)算(suan)(suan)(suan)法(fa)構造(zao)(zao)相(xiang)比(bi)，基于格(ge)的(de)(de)(de)(de)(de)算(suan)(suan)(suan)法(fa)可以實現(xian)(xian)明(ming)顯提升的(de)(de)(de)(de)(de)計(ji)(ji)算(suan)(suan)(suan)速度(du)、更高的(de)(de)(de)(de)(de)安(an)(an)全(quan)(quan)強度(du)和(he)(he)略微增(zeng)加的(de)(de)(de)(de)(de)通(tong)信開(kai)銷。與其(qi)他幾種實現(xian)(xian)后(hou)量子密碼(ma)(ma)(ma)的(de)(de)(de)(de)(de)方式相(xiang)比(bi)，格(ge)密碼(ma)(ma)(ma)的(de)(de)(de)(de)(de)公私(si)鑰(yao)尺(chi)寸(cun)更小，并(bing)且安(an)(an)全(quan)(quan)性(xing)和(he)(he)計(ji)(ji)算(suan)(suan)(suan)速度(du)等(deng)指標更優(you)。此外，基于格(ge)的(de)(de)(de)(de)(de)算(suan)(suan)(suan)法(fa)可以實現(xian)(xian)加密、數字(zi)簽名、密鑰(yao)交換(huan)、屬性(xing)加密、函數加密、全(quan)(quan)同態加密等(deng)各類現(xian)(xian)有的(de)(de)(de)(de)(de)密碼(ma)(ma)(ma)學(xue)構造(zao)(zao)。基于格(ge)的(de)(de)(de)(de)(de)算(suan)(suan)(suan)法(fa)的(de)(de)(de)(de)(de)安(an)(an)全(quan)(quan)性(xing)依賴于求解格(ge)中(zhong)問題的(de)(de)(de)(de)(de)困難性(xing)。
在達到相同（甚至更(geng)(geng)高）的(de)安全強度時，基于格(ge)的(de)算(suan)法的(de)公私鑰尺寸比上述三種(zhong)構造(zao)更(geng)(geng)小，計(ji)算(suan)速(su)度也更(geng)(geng)快，且能被(bei)(bei)用于構造(zao)多種(zhong)密碼(ma)(ma)學(xue)原(yuan)語(yu)，因此更(geng)(geng)適用于真實世界中(zhong)的(de)應(ying)用。近年來，基于LWE (Learning with Errors) 問(wen)題(ti) 和 RLWE (Ring-LWE) 問(wen)題(ti)的(de)格(ge)密碼(ma)(ma)學(xue)構造(zao)發展迅速(su)，被(bei)(bei)認(ren)為是(shi)最有希(xi)望(wang)被(bei)(bei)標準化的(de)技術路線之一。
格密碼(ma)算法(fa)概述
格(ge)(ge)（lattice）是一(yi)種數(shu)學結構，定(ding)義為(wei)一(yi)組(zu)線性無關(guan)的(de)非0向(xiang)(xiang)量（稱(cheng)作(zuo)格(ge)(ge)基）的(de)整(zheng)系數(shu)線性組(zu)合。具體來說，給定(ding)一(yi)組(zu)格(ge)(ge)基X1,......,Xn對任意的(de)整(zheng)數(shu)C1,...,Cn，C1X1+...+CnXn都(dou)是屬于(yu)這(zhe)個格(ge)(ge)的(de)向(xiang)(xiang)量，n稱(cheng)為(wei)格(ge)(ge)的(de)維(wei)數(shu)。例(li)如，下(xia)圖表示了(le)一(yi)個二維(wei)格(ge)(ge)和(he)兩(liang)組(zu)不(bu)同的(de)格(ge)(ge)基：X1
一(yi)個(ge)格(ge)(ge)(ge)的(de)(de)(de)格(ge)(ge)(ge)基(ji)(ji)(ji)(ji)可(ke)(ke)以不(bu)是唯一(yi)的(de)(de)(de)，例如，（（2,1），（1,1））和(he)（（1,0），（0,1））都是二(er)維整數(shu)格(ge)(ge)(ge)的(de)(de)(de)一(yi)組(zu)(zu)格(ge)(ge)(ge)基(ji)(ji)(ji)(ji)。從上圖中(zhong)可(ke)(ke)以看(kan)到(dao)，即使(shi)是定(ding)義(yi)了同樣的(de)(de)(de)格(ge)(ge)(ge)的(de)(de)(de)兩(liang)組(zu)(zu)格(ge)(ge)(ge)基(ji)(ji)(ji)(ji)，其長度也(ye)可(ke)(ke)能(neng)相差(cha)很大(da)。數(shu)學(xue)家和(he)密(mi)碼學(xue)家們普遍認為，對于一(yi)個(ge)維數(shu)足夠高的(de)(de)(de)格(ge)(ge)(ge)，通(tong)過一(yi)組(zu)(zu)隨機(ji)選取的(de)(de)(de)格(ge)(ge)(ge)基(ji)(ji)(ji)(ji)找(zhao)到(dao)一(yi)組(zu)(zu)短(duan)(duan)格(ge)(ge)(ge)基(ji)(ji)(ji)(ji)，或得(de)到(dao)一(yi)組(zu)(zu)線性(xing)無關的(de)(de)(de)短(duan)(duan)格(ge)(ge)(ge)向量(liang)是困難(nan)的(de)(de)(de)。這個(ge)問(wen)題(ti)(ti)(ti)稱(cheng)作最(zui)短(duan)(duan)獨(du)立向量(liang)問(wen)題(ti)(ti)(ti)（SIVP）。除此之外，還有一(yi)些其他的(de)(de)(de)基(ji)(ji)(ji)(ji)于格(ge)(ge)(ge)的(de)(de)(de)困難(nan)問(wen)題(ti)(ti)(ti)，如gap-SVP、BDD等。以上的(de)(de)(de)困難(nan)問(wen)題(ti)(ti)(ti)通(tong)常屬于數(shu)學(xue)上的(de)(de)(de)理論研究范疇(chou)。在(zai)密(mi)碼學(xue)的(de)(de)(de)實(shi)際(ji)應用(yong)當中(zhong)，格(ge)(ge)(ge)密(mi)碼算(suan)法所基(ji)(ji)(ji)(ji)于的(de)(de)(de)困難(nan)問(wen)題(ti)(ti)(ti)更多采用(yong)容錯(cuo)學(xue)習（LWE）問(wen)題(ti)(ti)(ti)。
LWE問(wen)(wen)題(ti)這樣表述(shu)：給(gei)定隨機矩陣(zhen)A和向量As+e mod q，其中e是小(xiao)的(de)(de)誤差項，q是模(mo)數(shu)（通常(chang)取(qu)較大的(de)(de)素(su)數(shu)），從中恢復(fu)隨機的(de)(de)s是困難(nan)(nan)的(de)(de)。我們稱(A,b=As+e mod q)為(wei)LWE樣本，s為(wei)LWE秘密。容易(yi)看到，如果不(bu)存在誤差項e，這一問(wen)(wen)題(ti)即為(wei)求解線性方程組，是易(yi)解的(de)(de)。然而，當引入誤差e之后，LWE問(wen)(wen)題(ti)可(ke)歸約到SIVP等格(ge)上的(de)(de)困難(nan)(nan)問(wen)(wen)題(ti)，即求解LWE問(wen)(wen)題(ti)的(de)(de)難(nan)(nan)度不(bu)低(di)于(yu)求解格(ge)上的(de)(de)困難(nan)(nan)問(wen)(wen)題(ti)。
在(zai)(zai)應(ying)用于(yu)(yu)密碼(ma)算法時，LWE問(wen)題(ti)(ti)存(cun)在(zai)(zai)一(yi)(yi)個很(hen)大(da)(da)的(de)(de)優勢：存(cun)在(zai)(zai)“最壞(huai)情(qing)況到(dao)平均情(qing)況的(de)(de)歸(gui)約”，即求(qiu)解平均情(qing)況下的(de)(de)LWE問(wen)題(ti)(ti)，其難度不低(di)于(yu)(yu)最難的(de)(de)SIVP問(wen)題(ti)(ti)實例(li)。在(zai)(zai)一(yi)(yi)些早(zao)期的(de)(de)公鑰密碼(ma)算法，如基于(yu)(yu)背(bei)包(bao)(bao)問(wen)題(ti)(ti)的(de)(de)密碼(ma)體制中(zhong)，由于(yu)(yu)存(cun)在(zai)(zai)一(yi)(yi)些易解的(de)(de)背(bei)包(bao)(bao)問(wen)題(ti)(ti)實例(li)，使得當參數選(xuan)取不恰當時，密碼(ma)算法的(de)(de)安全性(xing)易受攻(gong)擊。而對于(yu)(yu)基于(yu)(yu)LWE問(wen)題(ti)(ti)的(de)(de)格密碼(ma)來(lai)說，由于(yu)(yu)存(cun)在(zai)(zai)最壞(huai)情(qing)況到(dao)平均情(qing)況的(de)(de)歸(gui)約，因而可(ke)以避免這(zhe)種攻(gong)擊的(de)(de)產生(sheng)。這(zhe)為基于(yu)(yu)LWE問(wen)題(ti)(ti)設計的(de)(de)密碼(ma)算法帶來(lai)了(le)很(hen)大(da)(da)安全性(xing)上的(de)(de)優勢。
直接通(tong)過(guo)LWE問(wen)題(ti)(ti)構造的密碼學方案(an)效(xiao)率并不是很高(gao)。更(geng)多(duo)(duo)的時候，我(wo)們將(jiang)整(zheng)數(shu)向量用多(duo)(duo)項式代替，得到(dao)多(duo)(duo)項式LWE或稱(cheng)環LWE。一個環LWE樣(yang)本為(wei)(a,b=as+e mod q)，其中(zhong)a,s,e 均為(wei)多(duo)(duo)項式。環LWE的安全性建立在理想格(ge)中(zhong)相應數(shu)學問(wen)題(ti)(ti)困(kun)難性的基礎(chu)之上(shang)。盡管這(zhe)(zhe)些(xie)問(wen)題(ti)(ti)在困(kun)難性上(shang)面(mian)被認為(wei)不如格(ge)問(wen)題(ti)(ti)更(geng)可靠，但目前還(huan)沒有(you)(you)發現(xian)可以有(you)(you)效(xiao)求解(jie)這(zhe)(zhe)些(xie)問(wen)題(ti)(ti)的算法。此外(wai)，還(huan)有(you)(you)可靠性介于LWE和(he)環LWE問(wen)題(ti)(ti)之間(jian)的模LWE問(wen)題(ti)(ti)，以及這(zhe)(zhe)些(xie)問(wen)題(ti)(ti)的變種LWR、環LWR、模LWR問(wen)題(ti)(ti)。格(ge)密碼的安全性基本上(shang)都依賴于這(zhe)(zhe)些(xie)問(wen)題(ti)(ti)的困(kun)難性。
1.1 基(ji)于格的公鑰(yao)加密算法
通常(chang)，在一(yi)個基于(yu)LWE問題設計的密碼算法中(zhong)，我們將(jiang)LWE樣本作為(wei)公(gong)(gong)(gong)鑰(yao)(yao)使(shi)(shi)用(yong)，而將(jiang)LWE秘(mi)密作為(wei)私(si)鑰(yao)(yao)使(shi)(shi)用(yong)，這(zhe)保證了公(gong)(gong)(gong)鑰(yao)(yao)不(bu)會(hui)泄露關于(yu)私(si)鑰(yao)(yao)的信息。我們令公(gong)(gong)(gong)鑰(yao)(yao)為(wei) (a,b=as+e mod q)，私(si)鑰(yao)(yao)為(wei) s ，這(zhe)里 a,b,s,e均為(wei)多項式(shi)，且s,e的系(xi)數相比于(yu)q是較小的（理(li)論(lun)上s和e的系(xi)數應取為(wei)離散正態分(fen)布(bu)，但(dan)在實(shi)際(ji)應用(yong)中(zhong)，出于(yu)實(shi)現(xian)上的效率和安全，s和e通常(chang)使(shi)(shi)用(yong)二項分(fen)布(bu)或(huo)均勻(yun)分(fen)布(bu)來(lai)模擬）。我們下面描(miao)述最基礎的格公(gong)(gong)(gong)鑰(yao)(yao)加密方案。
對于需要(yao)加密的消息，我們將消息記為 0-1 系數的多項(xiang)式 m 。
(1)首先隨機選取系數(shu)較小的多項式 r,e1,e2
(2)計算密文(wen)c=ar+e1 mod q和 d=br+e2+m(q-1)/2 mod q
容(rong)易看(kan)到，由(you)(you)于(yu) as≈b mod q，故ars≈br mod q，且 (ar+e1)s≈br+e2 mod q。當s,e,r,e1,e2均足(zu)夠小(xiao)時，可以(yi)保證br+e2-(ar+e1)s mod q的(de)(de)(de)系數均不超過(q-1)/4。故d-cs和m(q-1)/2的(de)(de)(de)每個系數之差(cha)都不超過(q-1)/4。我們(men)可以(yi)通(tong)過這(zhe)(zhe)樣(yang)的(de)(de)(de)方(fang)式(shi)從d-cs中還(huan)原m;若d-cs的(de)(de)(de)第(di)i個系數距離0更(geng)(geng)近，則令m的(de)(de)(de)第(di)i位為0；若 d-cs的(de)(de)(de)第(di)i位系數距離(q-1)/2更(geng)(geng)近，則令m的(de)(de)(de)第(di)i位系數為1。這(zhe)(zhe)樣(yang)我們(men)成功(gong)通(tong)過私鑰(yao)(yao)s解密(mi)了密(mi)文(c,d)，得到消(xiao)息(xi)(xi)m。這(zhe)(zhe)一算法(fa)的(de)(de)(de)安全(quan)性(xing)(xing)由(you)(you)兩個部分保證：其(qi)一是私鑰(yao)(yao)的(de)(de)(de)安全(quan)性(xing)(xing)，由(you)(you)于(yu)公(gong)(gong)鑰(yao)(yao)為LWE樣(yang)本，通(tong)過公(gong)(gong)鑰(yao)(yao)不會(hui)泄露私鑰(yao)(yao)的(de)(de)(de)信息(xi)(xi)；其(qi)二(er)是消(xiao)息(xi)(xi)的(de)(de)(de)安全(quan)性(xing)(xing)，由(you)(you)于(yu)密(mi)文同樣(yang)為LWE樣(yang)本，通(tong)過密(mi)文在未知私鑰(yao)(yao)的(de)(de)(de)前提下，不會(hui)泄露消(xiao)息(xi)(xi)。以(yi)上(shang)描述的(de)(de)(de)簡單(dan)方(fang)案(an)(an)是選擇明文安全(quan)，而非選擇密(mi)文安全(quan)的(de)(de)(de)。對(dui)于(yu)具(ju)體的(de)(de)(de)方(fang)案(an)(an)，則需要應(ying)用密(mi)碼學(xue)中著名的(de)(de)(de)Fujisaka-Okamoto變換，將以(yi)上(shang)的(de)(de)(de)基礎方(fang)案(an)(an)轉變為選擇密(mi)文安全(quan)的(de)(de)(de)方(fang)案(an)(an)。
1.2 基(ji)于格的數字簽(qian)名算法
對于RSA、橢圓曲線等密碼體制來說，其中的(de)公(gong)鑰加(jia)密和數字簽名算法存(cun)在一定的(de)對偶性：可通過簡單的(de)交換公(gong)私鑰，將公(gong)鑰加(jia)密算法轉化為(wei)數字簽名算法。
然(ran)而(er)(er)，對(dui)(dui)(dui)于格密(mi)碼而(er)(er)言，這(zhe)(zhe)種(zhong)(zhong)對(dui)(dui)(dui)偶性并不存在，這(zhe)(zhe)意味著(zhu)我(wo)(wo)們(men)需要(yao)通過新的(de)(de)(de)(de)方(fang)式構造(zao)數字(zi)簽(qian)名算法。被密(mi)碼學家(jia)廣泛采用(yong)的(de)(de)(de)(de)一(yi)(yi)種(zhong)(zhong)方(fang)式，即(ji)通過零(ling)知(zhi)識(shi)證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)協(xie)議構造(zao)數字(zi)簽(qian)名。零(ling)知(zhi)識(shi)證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)可能是(shi)(shi)密(mi)碼學中最為神奇的(de)(de)(de)(de)一(yi)(yi)類應(ying)(ying)用(yong)。零(ling)知(zhi)識(shi)證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)解(jie)決這(zhe)(zhe)樣一(yi)(yi)個(ge)問題：我(wo)(wo)們(men)是(shi)(shi)否可以向他人提供對(dui)(dui)(dui)一(yi)(yi)個(ge)命題的(de)(de)(de)(de)證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)，但卻(que)不泄露證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)這(zhe)(zhe)一(yi)(yi)命題所需要(yao)的(de)(de)(de)(de)知(zhi)識(shi)？盡管看起(qi)來有些(xie)反(fan)直覺，但這(zhe)(zhe)一(yi)(yi)點事實(shi)上是(shi)(shi)可以做到的(de)(de)(de)(de)。實(shi)現(xian)安(an)全的(de)(de)(de)(de)數字(zi)簽(qian)名，最基本的(de)(de)(de)(de)需求是(shi)(shi)令(ling)驗證(zheng)(zheng)(zheng)(zheng)(zheng)者(zhe)有能力對(dui)(dui)(dui)簽(qian)名者(zhe)的(de)(de)(de)(de)身份進行認證(zheng)(zheng)(zheng)(zheng)(zheng)。而(er)(er)這(zhe)(zhe)等(deng)價于這(zhe)(zhe)樣的(de)(de)(de)(de)一(yi)(yi)個(ge)零(ling)知(zhi)識(shi)證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)：證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)者(zhe)可證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)自己擁有（和對(dui)(dui)(dui)應(ying)(ying)身份的(de)(de)(de)(de)公鑰(yao)匹配的(de)(de)(de)(de)）私鑰(yao)，但不向驗證(zheng)(zheng)(zheng)(zheng)(zheng)者(zhe)泄露關于私鑰(yao)的(de)(de)(de)(de)信息。這(zhe)(zhe)是(shi)(shi)一(yi)(yi)類最簡單的(de)(de)(de)(de)零(ling)知(zhi)識(shi)證(zheng)(zheng)(zheng)(zheng)(zheng)明(ming)(ming)協(xie)議，通常稱為∑協(xie)議。
∑協議由以(yi)下三個步驟(zou)構成：
（1）證明者(zhe)給出承諾w。證明者(zhe)首先隨機選擇(ze)y，并通過(guo)y生成承諾w，交給驗證者(zhe)。
（2）驗(yan)(yan)證(zheng)者提出挑(tiao)戰 c。驗(yan)(yan)證(zheng)者給出均勻隨機的挑(tiao)戰c。
（3）證(zheng)明者(zhe)給出應答(da)z。證(zheng)明者(zhe)通(tong)過(guo)第一步中的y、挑戰(zhan)(zhan)c以(yi)及用(yong)戶私(si)鑰，得到應答(da) z。（我們(men)額外要(yao)求(qiu)z在其值域上是(shi)均勻隨機的）驗(yan)證(zheng)者(zhe)可通(tong)過(guo)用(yong)戶公(gong)鑰、挑戰(zhan)(zhan)c以(yi)及承諾w確(que)認z是(shi)否是(shi)由證(zheng)明者(zhe)合法生成(cheng)的。
我們將(w,c,z)三元(yuan)組稱為協議的(de)(de)(de)(de)抄(chao)本(transcript)。在(zai)具備(bei)零(ling)知識性的(de)(de)(de)(de) ∑ 協議中(zhong)，我們通(tong)常要求在(zai)未(wei)知私鑰(yao)的(de)(de)(de)(de)情(qing)況下(1) 通(tong)過w和(he)c得(de)到z是困難的(de)(de)(de)(de)；(2) 通(tong)過c和(he)z得(de)到w是容(rong)易的(de)(de)(de)(de)。因(yin)此，即使在(zai)未(wei)知私鑰(yao)的(de)(de)(de)(de)前提下，(w,c,z)三元(yuan)組也(ye)可以通(tong)過這(zhe)(zhe)(zhe)樣的(de)(de)(de)(de)方式(shi)生成：首先隨機選取c和(he)z，然后得(de)到w。由于這(zhe)(zhe)(zhe)一生成方式(shi)不需要私鑰(yao)的(de)(de)(de)(de)參與，故協議的(de)(de)(de)(de)抄(chao)本不包含關(guan)于私鑰(yao)的(de)(de)(de)(de)任(ren)何知識!這(zhe)(zhe)(zhe)就保證了協議的(de)(de)(de)(de)零(ling)知識性。
由于(yu)(yu)∑協(xie)議(yi)需(xu)要(yao)證(zheng)(zheng)明者和驗(yan)證(zheng)(zheng)者之間實施交互(hu)，故(gu)無法(fa)直接應用于(yu)(yu)構(gou)造數(shu)字簽(qian)名(ming)。但注意(yi)到∑協(xie)議(yi)要(yao)求(qiu)挑(tiao)戰c均(jun)勻隨(sui)機選取(qu)，而(er)正如我(wo)們所知(zhi)，一個(ge)安(an)(an)全的(de)(de)(de)(de)哈希函(han)數(shu)，其輸出(chu)和隨(sui)機值是不(bu)可(ke)區(qu)分的(de)(de)(de)(de)。因(yin)此，我(wo)們可(ke)以將承諾(nuo)w和需(xu)要(yao)簽(qian)名(ming)的(de)(de)(de)(de)消(xiao)息(xi)m輸入哈希函(han)數(shu)H，并用哈希函(han)數(shu)的(de)(de)(de)(de)輸出(chu)模擬(ni)挑(tiao)戰 c，從而(er)不(bu)需(xu)要(yao)額外的(de)(de)(de)(de)驗(yan)證(zheng)(zheng)者提(ti)出(chu)挑(tiao)戰。與此同時，由于(yu)(yu)有簽(qian)名(ming)消(xiao)息(xi)的(de)(de)(de)(de)參與，也實現了消(xiao)息(xi)和∑協(xie)議(yi)抄本(ben)的(de)(de)(de)(de)綁定。這(zhe)個(ge)方法(fa)稱為Fiat-Shamir變換。可(ke)以證(zheng)(zheng)明，安(an)(an)全的(de)(de)(de)(de)∑協(xie)議(yi)通(tong)過Fiat-Shamir變換，得到安(an)(an)全的(de)(de)(de)(de)數(shu)字簽(qian)名(ming)方案。
下面我(wo)們簡單介紹如何基于LWE問題構造∑協議，進(jin)而構造數字(zi)簽名(ming)。和公鑰(yao)加密算法(fa)類(lei)似，我(wo)們令公鑰(yao)為(wei) (a,b=as+e mod q)，私鑰(yao)為(wei) s 。
(1)首先隨機選(xuan)取(qu)較小(xiao)的y
(2)令承諾w為ay的(de)高(gao)比特位(wei)，以排除誤差項的(de)影(ying)響
(3)對于挑(tiao)戰c，令(ling)應答z = y + cs。（注(zhu)意(yi)到我們要求z均勻隨機，故需要排(pai)除(chu)一些令(ling)z不隨機的邊緣(yuan)取(qu)值(zhi)：當z為邊緣(yuan)取(qu)值(zhi)時(shi)，需要重新選取(qu)y并再次計算z。我們這里(li)不展開細節）
由于ay = az – cas ≈ az – cb mod q，故只需(xu)驗(yan)(yan)證w 是否為 az–cb的高比特位即可(ke)。對于需(xu)要(yao)(yao)簽名的消(xiao)息m和雜湊函(han)數H，我們令c = H(w||m)，即可(ke)將這一協議轉化為簽名算法(fa)（在驗(yan)(yan)簽時需(xu)要(yao)(yao)驗(yan)(yan)證c = H(w||m)）。
上海航芯ACL16安(an)全芯片
上海航(hang)芯(xin)(xin)自主(zhu)研發的ACL16芯(xin)(xin)片，已通過AEC-Q100車(che)規認證(zheng)、EAL5+認證(zheng)，是(shi)一(yi)款高(gao)安(an)全、高(gao)可(ke)靠性的車(che)載安(an)全芯(xin)(xin)片。芯(xin)(xin)片工作溫(wen)度(du)達到AEC-Q100 Grade1等級(ji)，溫(wen)度(du)范圍-40℃~+125℃，其安(an)全性、可(ke)靠性等級(ji)均超越國產同類芯(xin)(xin)片，是(shi)當前車(che)載終端(duan)應用中極具(ju)性價(jia)比優勢的一(yi)款安(an)全芯(xin)(xin)片，已適配數十種前裝和(he)后裝產品，為智能(neng)網聯汽車(che)車(che)內安(an)全和(he)車(che)聯網安(an)全護(hu)航(hang)。
如(ru)需銷(xiao)售咨詢，請聯系(xi)：
