[發(fā)明專(zhuān)利]一種基于格的密鑰封裝方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910682004.5
• 申請(qǐng)日: 2019-07-26
• 公開(kāi)（公告）號(hào): CN110460442B
• 公開(kāi)（公告）日: 2020-08-14
• 發(fā)明（設(shè)計(jì)）人: 潘彥斌;李昊宇;謝天元;劉珍;楊照民;朱熠銘
• 申請(qǐng)（專(zhuān)利權(quán)）人: 中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院
• 主分類(lèi)號(hào): H04L9/30
• 分類(lèi)號(hào): H04L9/30;H04L29/06
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司 11200
• 代理人: 司立彬

本發(fā)明公開(kāi)了一種基于格的密鑰封裝方法。本方法首先選取特殊的b＝α，然后計(jì)算相應(yīng)的a，對(duì)經(jīng)典LWE加密體制做更進(jìn)一步的壓縮，提供一種快速、高效的基于格的密鑰封裝方法。其中涉及的剩余類(lèi)環(huán)Z_j,當(dāng)j為偶數(shù)時(shí)，選取作為環(huán)Z_j的代表元。當(dāng)j為奇數(shù)時(shí)，選取作為環(huán)Z_j的代表元；選取的公開(kāi)參數(shù)N,q,α及小系數(shù)多項(xiàng)式f,g,e的選取方式，應(yīng)保證以很大概率成立，其中||gr+ef||_∞表示多項(xiàng)式gr+ef所有系數(shù)的絕對(duì)值中最大的那個(gè)。

技術(shù)領(lǐng)域

本發(fā)明屬于信息安全技術(shù)領(lǐng)域，具體涉及一種基于格的密鑰封裝方法。

背景技術(shù)

目前使用的公鑰加密算法，密鑰封裝體制的構(gòu)造主要是基于經(jīng)典的數(shù)學(xué)問(wèn)題，例如目前廣泛使用的RSA公鑰密碼體制或橢圓曲線公鑰密碼體制，其依賴(lài)的困難數(shù)學(xué)問(wèn)題——大整數(shù)分解或橢圓曲線群上的離散對(duì)數(shù)問(wèn)題。

理論上量子算法可以有效求解整數(shù)分解和離散對(duì)數(shù)等經(jīng)典問(wèn)題，使得現(xiàn)有公鑰密碼體制的安全性面臨極大的威脅，因此能夠抵抗量子計(jì)算機(jī)攻擊的密碼(后量子密碼)受到了廣泛的關(guān)注。根據(jù)底層困難數(shù)學(xué)問(wèn)題的不同，后量子公鑰密碼主要可以分為：基于格的密碼、基于編碼的密碼、基于哈希的密碼以及基于多變量的密碼。

對(duì)于基于格的公鑰密碼體制來(lái)說(shuō)，2005年Regev提出基于LWE問(wèn)題的公鑰加密體制后，越來(lái)越多的密碼學(xué)家對(duì)其進(jìn)行了深入的研究。具體來(lái)說(shuō)，基于LWE的公鑰加密體制一般具有如下結(jié)構(gòu)，發(fā)送方利用接收方的公鑰(a,b＝as+e₁)對(duì)消息m進(jìn)行加密得到密文(c₁，c₂)，其中c₁＝ar+e_a,c₂＝br+e_b+Encode(m)，Encode(m)是對(duì)消息m的編碼，最常見(jiàn)的是最后接收方利用自己的私鑰s來(lái)對(duì)密文解密恢復(fù)消息。為了減少密文規(guī)模，通常會(huì)對(duì)密文c₂進(jìn)行壓縮。最常見(jiàn)的方法是將c₂的每個(gè)系數(shù)的低位比特舍棄，僅保留2到3個(gè)高位比特，這就需要我們選擇足夠大的q來(lái)兼容這種壓縮，從而保證解密正確率。

除了基于格的公鑰加密體制，基于格的密鑰封裝機(jī)制，也是格密碼研究的重要內(nèi)容。在密鑰封裝機(jī)制中，發(fā)送方運(yùn)行一個(gè)封裝算法產(chǎn)生一個(gè)會(huì)話密鑰以及與之對(duì)應(yīng)的密文，該密文也被稱(chēng)為會(huì)話密鑰封裝。隨后發(fā)送方將會(huì)話密鑰封裝發(fā)送給接收方。接收方運(yùn)行解封裝算法得到與發(fā)送方相同的會(huì)話密鑰。通過(guò)經(jīng)典的Fujisaki-Okamoto(FO)變換，可以將具有IND-CPA安全的密鑰封裝機(jī)制轉(zhuǎn)換為具有IND-CCA2安全的密鑰封裝機(jī)制。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種基于格的密鑰封裝方法。與經(jīng)典LWE加密體制首先隨機(jī)選取a，然后計(jì)算相應(yīng)的b不同，本發(fā)明通過(guò)首先選取特殊的b＝α，然后計(jì)算相應(yīng)的a，對(duì)經(jīng)典LWE加密體制做更進(jìn)一步的壓縮，提供一種快速、高效的基于格的密鑰封裝方法。

本發(fā)明涉及的剩余類(lèi)環(huán)Z_j,當(dāng)j為偶數(shù)時(shí)，我們選取作為環(huán)Z_j的代表元。當(dāng)j為奇數(shù)時(shí)，我們選取作為環(huán)Z_j的代表元。

一種基于格的密鑰封裝方法，其步驟包括：

步驟1.1:密鑰生成方法：接收方首先選取正整數(shù)N，大于1的整數(shù)q，正整數(shù)α使得選取N次整系數(shù)多項(xiàng)式F(x)，令環(huán)R_q＝Z_q[x]/F(x)，其中Z_q[x]是剩余類(lèi)環(huán)Z_q上的多項(xiàng)式環(huán)，并將(N,q,α)及環(huán)R_q做為公共參數(shù)公開(kāi)。接收方選擇環(huán)R_q中的小系數(shù)多項(xiàng)式f，g，多項(xiàng)式f作為私鑰要在環(huán)R_q中可逆，其逆表示為f^-1。最后計(jì)算公鑰h＝f^-1(g+α)mod q。