[發(fā)明專利]一種后量子密碼構(gòu)造中環(huán)上舍入學(xué)習(xí)的通用軟件實(shí)現(xiàn)方法

有效

• 申請?zhí)枺?/td>: 202110313030.8
• 申請日: 2021-03-24
• 公開（公告）號(hào): CN113179151B
• 公開（公告）日: 2022-08-16
• 發(fā)明（設(shè)計(jì)）人: 周永彬;姜子銘;張銳
• 申請（專利權(quán)）人: 中國科學(xué)院信息工程研究所
• 主分類號(hào): H04L9/06
• 分類號(hào): H04L9/06;H04L9/08;H04L9/30;G06N10/00
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司 11200
• 代理人: 司立彬

1.一種后量子密碼構(gòu)造中環(huán)上舍入學(xué)習(xí)的通用軟件實(shí)現(xiàn)方法，其中環(huán)上舍入學(xué)習(xí)RLWR分布定義為其中a、s是多項(xiàng)式環(huán)上的多項(xiàng)式，f為N次首一多項(xiàng)式，正整數(shù)q≥p≥2，舍入計(jì)算具體為映射多項(xiàng)式a的系數(shù)多項(xiàng)式s的系數(shù)其步驟包括：

A、設(shè)定RLWR參數(shù)N、f、p、q、S，以及實(shí)際運(yùn)行平臺(tái)的CPU位數(shù)B，其中N、p、q、S為正整數(shù)，f為N次首一多項(xiàng)式f(x)，計(jì)算q的所有素因子{p₁,…,p_t}，以及p₁-1,…,p_t-1的最大公因數(shù)O(q)；用M_max(n,B)表示可在B位CPU平臺(tái)上實(shí)現(xiàn)的n階NTT的模數(shù)最大值，計(jì)算和若S＝2，則需要設(shè)定多項(xiàng)式s系數(shù)不為0的概率P[s_i≠0]；

B、根據(jù)參數(shù)N、f、q、S、B，選取一多項(xiàng)式乘法實(shí)現(xiàn)算法，記為PMA，生成該多項(xiàng)式乘法實(shí)現(xiàn)方案中可預(yù)計(jì)算的參數(shù)；

C、根據(jù)參數(shù)q和已選取的多項(xiàng)式乘法的實(shí)現(xiàn)方案PMA，選取一可用模約化方法作為模約化的實(shí)現(xiàn)方案，記為MRA；

D、根據(jù)參數(shù)p、q選取一舍入計(jì)算實(shí)現(xiàn)方法，記為RA，生成該舍入計(jì)算實(shí)現(xiàn)中可預(yù)計(jì)算的參數(shù)；

E、對于輸入的多項(xiàng)式a(x)和s(x)，計(jì)算并輸出RLWR分布中的對應(yīng)值b(x)：首先計(jì)算整數(shù)域上的多項(xiàng)式乘法b₁(x)←PMA(a(x),s(x))，具體計(jì)算為b₁(x)＝a(x)·s(x)；其次執(zhí)行模約化操作b₂(x)←MRA(b₁(x))，具體計(jì)算為b₂(x)＝((b₁(x)mod f(x))mod q)；然后計(jì)算舍入值b(x)←RA(b₂(x))，具體計(jì)算為最后輸出b(x)；

2.如權(quán)利要求1所述的方法，其特征在于，步驟B中，所述多項(xiàng)式乘法實(shí)現(xiàn)方案為稀疏乘法、基于NTT負(fù)折疊卷積的多項(xiàng)式乘法、基于NTT的多項(xiàng)式乘法或基于FFT的多項(xiàng)式乘法。

3.如權(quán)利要求2所述的方法，其特征在于，所述多項(xiàng)式乘法實(shí)現(xiàn)方案為稀疏乘法時(shí)，稀疏乘法的使用條件為：S＝2。

4.如權(quán)利要求2所述的方法，其特征在于，所述多項(xiàng)式乘法實(shí)現(xiàn)方案為基于NTT負(fù)折疊卷積的多項(xiàng)式乘法時(shí)，基于NTT負(fù)折疊卷積的多項(xiàng)式乘法的使用條件為：f(x)＝x^N+1；N|O(q)且或

5.如權(quán)利要求2所述的方法，其特征在于，所述多項(xiàng)式乘法實(shí)現(xiàn)方案為基于NTT的多項(xiàng)式乘法，且使用條件為：且或

6.如權(quán)利要求2所述的方法，其特征在于，步驟B中，根據(jù)算法的效率選取效率最高的多項(xiàng)式乘法實(shí)現(xiàn)方案；其中，輸入規(guī)模N相等的情況下，基于NTT負(fù)折疊卷積的多項(xiàng)式乘法、基于NTT的多項(xiàng)式乘法、基于FFT的多項(xiàng)式乘法三者的效率依次遞減；時(shí)，稀疏乘法算法的效率高于基于NTT負(fù)折疊卷積的多項(xiàng)式乘法；時(shí)，稀疏乘法算法的效率高于基于NTT的多項(xiàng)式乘法；時(shí)，稀疏乘法算法的效率高于基于FFT的多項(xiàng)式乘法，其中

7.如權(quán)利要求1所述的方法，其特征在于，步驟D中，舍入計(jì)算實(shí)現(xiàn)方案選自移位運(yùn)算、傳統(tǒng)預(yù)計(jì)算算法和新型舍入算法；其中，若q/p是2的方冪，則舍入計(jì)算實(shí)現(xiàn)方案采用移位算法；若是2的方冪，則舍入計(jì)算實(shí)現(xiàn)方案采用新型舍入算法；否則，舍入計(jì)算實(shí)現(xiàn)方案采用傳統(tǒng)預(yù)計(jì)算算法。