買專利賣專利找龍圖騰，真高效！ 查專利查商標(biāo)用IPTOP,全免費！專利年費監(jiān)控用IP管家,真方便！

龍圖騰網(wǎng)獲悉西北工業(yè)大學(xué)申請的專利基于GPU并行優(yōu)化KNTT算法的全同態(tài)加密門自舉方法獲國家發(fā)明授權(quán)專利權(quán)，本發(fā)明授權(quán)專利權(quán)由國家知識產(chǎn)權(quán)局授予，授權(quán)公告號為：CN116545605B 。

龍圖騰網(wǎng)通過國家知識產(chǎn)權(quán)局官網(wǎng)在2025-08-15發(fā)布的發(fā)明授權(quán)授權(quán)公告中獲悉：該發(fā)明授權(quán)的專利申請?zhí)?專利號為：202310365159.2，技術(shù)領(lǐng)域涉及：H04L9/00；該發(fā)明授權(quán)基于GPU并行優(yōu)化KNTT算法的全同態(tài)加密門自舉方法是由李慧賢;鄒信元;潘登;王浩設(shè)計研發(fā)完成，并于2023-04-07向國家知識產(chǎn)權(quán)局提交的專利申請。

本基于GPU并行優(yōu)化KNTT算法的全同態(tài)加密門自舉方法在說明書摘要公布了：本發(fā)明提供了一種基于GPU并行優(yōu)化KNTT算法的全同態(tài)加密門自舉方法，解決了現(xiàn)有TFHE方案中門自舉算法的存在效率低的不足之處。該方法從原來的計算多項式相乘TLWE密文擴(kuò)展到矩陣和多項式的乘法運算TGSW密文和TLWE密文，在原方案的基礎(chǔ)上省略了NTT變換生成的中間項，統(tǒng)一采用特定的矩陣矩陣I和矩陣E進(jìn)行相乘獲得最終結(jié)果，大幅簡化了算法的步驟，使其運行效率比原始的NTT算法更高。

本發(fā)明授權(quán)基于GPU并行優(yōu)化KNTT算法的全同態(tài)加密門自舉方法在權(quán)利要求書中公布了：1.基于GPU并行優(yōu)化KNTT算法的全同態(tài)加密門自舉方法，其特征在于，包括以下步驟： 步驟1、門自舉初始化 定義門自舉的輸入為一個TLWE密文c＝TLWEsμ＝a,b∈Tp+1，其中a＝a1,a2,...,ap∈Tp，T表示實環(huán)RZ，e為從高斯分布上選取的噪聲； 所述TLWE密文對應(yīng)的明文空間為M，M∈{μ0,μ1}，其中，μ0＝0，μ1∈T，且μ0≠μ1； 所述TLWE密文的加密密鑰為s＝s1,s2,...,sp∈Bp，B∈{0,1}； 1.1選取用于門自舉過程中盲旋轉(zhuǎn)算法的自舉密鑰 自舉密鑰為p個TRGSW密文，p為正整數(shù)； 所述p個TRGSW密文對應(yīng)的加密密鑰為s”∈BN[X]K； 其中，K為正整數(shù)；N為2的整數(shù)次冪，表示TRGSW密文中的多項式的項數(shù)； 每個TRGSW密文中對應(yīng)的明文分別為組成加密密鑰s＝s1,s2,...,sp∈Bp的p個比特，該自舉密鑰BK＝BK1,BK2,...,BKp表示為如下形式： BKi＝TRGSWs'si,i＝1,2,...,p 1.2選取用于門自舉過程中密鑰轉(zhuǎn)換算法的轉(zhuǎn)換密鑰 轉(zhuǎn)換密鑰表示為如下形式： KSKs'→s＝{KSKi,j},i＝1,2,...,p,j＝1,2,...,t 其中，KSKi,j∈TLWEss'i·2-j，p和t均為正整數(shù)，t表示密鑰轉(zhuǎn)換過程的精度； 轉(zhuǎn)換密鑰的功能為將密鑰s'∈Bp變換到步驟1.1中的加密密鑰s∈Bp； 其中，s'∈Bp是TRGSW密文對應(yīng)的加密密鑰s”∈BN[X]K經(jīng)過密鑰提取得到的結(jié)果，即s'＝KeyExtracts”； 1.3進(jìn)行門自舉初始化 令令為最接近2Nai的整數(shù)，令為最接近2Nb的整數(shù)，則初始密文中的元素變?yōu)榱擞谐跏级囗検綐?gòu)造0,v，0表示n維的0向量，則0,v為一個對應(yīng)明文為多項式v的TRLWE密文，得到初始的并將ACC0存儲在全局內(nèi)存中； 步驟2、近似gadget分解得到密文矩陣和多項式 將步驟1初始化得到的ACC0，初始密文和自舉密鑰BK＝BK1,BK2,...,BKp作為下述整個過程的輸入，令 將ACC進(jìn)行g(shù)adget分解的結(jié)果表示為ACC＝A1,A2,...,AK,AK+1∈TNxK+1，其中對于每一個Ak＝c0k+c1kx+c2kx2+...+cN-1kxN-1,k＝1,2,...,K+1，將多項式Ak的全部系數(shù)改寫為： 令這里k＝1,2,...,K+1,q＝1,2,...,L，得到最終結(jié)果 decHACC＝A11,...,A1L,...,AK+11,...,AK+1L 其中，K，L表示近似gadget分解矩陣的大小，均為正整數(shù)，Bg表示分解矩陣中的元素； 步驟3、利用GPU并使用結(jié)合Karatsuba乘法的NTT優(yōu)化算法實現(xiàn)密文中矩陣與多項式的乘法 以Karatsuba乘法的分解次數(shù)α為基準(zhǔn)，設(shè)定α的取值范圍為α∈{1，2}，執(zhí)行下述的矩陣與多項式乘法步驟： 3.1將大的多項式和矩陣分解為小的子多項式和矩陣 對于步驟2中的和BK1，將其作為輸入，設(shè)定支持環(huán)多項式分解的環(huán)同構(gòu)如下： 其中 依據(jù)上述同構(gòu)選擇α的取值； 當(dāng)α＝1時，上述同構(gòu)為Zq[ξ']＝R，ξ'＝η2； 將大的多項式Akq進(jìn)行拆分，即其中Ar為Akq拆分多項式后所得的子項，其中Ar與N和α的關(guān)系為： 當(dāng)α＝1時，Akq展開寫成如下形式： Akq＝A0+η·A1 同理，對密鑰BK中的子項BK1進(jìn)行同等拆分； 由于BK1為一個矩陣，將其每一行表示為多項式其中，為Bk拆分后所得子項，其中與N和α的關(guān)系為： 當(dāng)α＝1時，將BK1中的子多項式Bk展開寫成如下形式： 上述的Akq∈Zq[η]，BK1∈Zq[η]K， 當(dāng)α＝2時，上述同構(gòu)為Zq[η]＝Zq[ξ'][x]x4-ξ'＝R[η]，ξ'＝η4，將大的多項式Akq進(jìn)行拆分，即其中Ar為Akq拆分多項式后所得的子項，Ar中的元素值參考上述Ar的通項；將Akq展開寫成如下形式： Aik＝A0+η·A1+η2·A2+η3·A3 同理，對密鑰BK1進(jìn)行同等拆分； 將其每一行表示為多項式其中為Bk拆分后所得子項，中的元素值參考上述的通項；將BK1展開寫成如下形式： 上述的Akq∈Zq[η]，BK1∈Zq[η]K，B0 k,B1 k,B2 k,B3 k,A0,A1,A2,A3∈Zq[ξ'],0k≤K； 3.2子多項式的NTT變換 以步驟3.1中得到的子項Ar和作為輸入進(jìn)行NTT變換，將NTT過程中的模素數(shù)b的原根代入多項式中代替復(fù)平面上的單位根進(jìn)行FFT的數(shù)學(xué)變換即為NTT變換，即： 在NTT變換中，W為模素數(shù)b的一個原根； 將多項式分解后得到的每一個子項對應(yīng)W為模素數(shù)b的一個原根；并將Ar中的保存在共享內(nèi)存xi中，i根據(jù)α分為r部分； 同理，對多項式也進(jìn)行上述NTT變換，根據(jù)BK1的行數(shù)K分配線程數(shù)，并提前對NTTξ進(jìn)行計算； 當(dāng)α＝1時，計算NTTA0，NTTA1，其中0＜k≤K，共需2K+2次的NTT變換； 當(dāng)α＝2時，計算NTTA0，NTTA1，NTTA2，NTTA3， 其中0＜k≤K，共需4K+4次的NTT變換； 當(dāng)Karatsuba乘法的分解次數(shù)為α?xí)r，NTT變換為2αK+1次； 3.3多項式NTT變換后的Karatsuba乘法 將該過程的最終結(jié)果用多項式形式S表示； 利用Karatsuba乘法對上述得到的經(jīng)過NTT變換的子多項式進(jìn)行計算； 該步驟在GPU上實現(xiàn)，基于矩陣BK1的大小安排各個線程，對于一個K×L大小的矩陣BK1來說，共安排K個線程，在每一個線程內(nèi)，對于矩陣BK1中的每一個多項式和Akq相乘來說，依據(jù)α的取值生成如下初始矩陣； 當(dāng)α＝1時，Karatsuba乘法為如下形式： 生成初始矩陣I和初始矩陣E如下： 得到最終結(jié)果多項式S中的每一個子項如下表示，其中0＜k≤K： 當(dāng)α＝2，Karatsuba乘法為如下形式： 生成初始矩陣I和初始矩陣E如下： 得到最終結(jié)果多項式S中的每一個子項如下表示，其中0＜k≤K： 3.4NTT逆變換 根據(jù)步驟3.3中所得的多項式S進(jìn)行NTT的逆變換，獲取多項式乘積最終結(jié)果，并存儲在全局內(nèi)存中，該結(jié)果即為ACC1； ACC1＝S＝NTT-1Skξ，其中0＜k≤K； 步驟4、得到門自舉的最終結(jié)果 4.1將步驟3中得到的ACC1代替ACC0，用BK2代替BK1，重復(fù)上述步驟2和步驟3；而后將步驟3中得到的結(jié)果ACC和密鑰BK中的子項作為輸入返回進(jìn)行步驟2和步驟3，直到密鑰BKp已得到使用，得到ACCp； 4.2將所得ACCp進(jìn)行密文提取，選擇ACCp＝A'0,A'1,...,A'K中的每個多項式的常數(shù)項組成一個新的密文，并且將最后一項加上μ'，得到密文c'＝c00,c01,...,c0K+μ'，令其中c'kr∈{0,1}，最終得到門自舉的結(jié)果，密文為：

如需購買、轉(zhuǎn)讓、實施、許可或投資類似專利技術(shù)，可聯(lián)系本專利的申請人或?qū)＠麢?quán)人西北工業(yè)大學(xué)，其通訊地址為：710072 陜西省西安市友誼西路127號；或者聯(lián)系龍圖騰網(wǎng)官方客服，聯(lián)系龍圖騰網(wǎng)可撥打電話0551-65771310或微信搜索“龍圖騰網(wǎng)”。