[發明專利]一種后量子密碼構造中環上舍入學習的通用軟件實現方法

有效

• 申請號: 202110313030.8
• 申請日: 2021-03-24
• 公開（公告）號: CN113179151B
• 公開（公告）日: 2022-08-16
• 發明（設計）人: 周永彬;姜子銘;張銳
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: H04L9/06
• 分類號: H04L9/06;H04L9/08;H04L9/30;G06N10/00
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 司立彬

1.一種后量子密碼構造中環上舍入學習的通用軟件實現方法，其中環上舍入學習RLWR分布定義為其中a、s是多項式環上的多項式，f為N次首一多項式，正整數q≥p≥2，舍入計算具體為映射多項式a的系數多項式s的系數其步驟包括：

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

B、根據參數N、f、q、S、B，選取一多項式乘法實現算法，記為PMA，生成該多項式乘法實現方案中可預計算的參數；

C、根據參數q和已選取的多項式乘法的實現方案PMA，選取一可用模約化方法作為模約化的實現方案，記為MRA；

D、根據參數p、q選取一舍入計算實現方法，記為RA，生成該舍入計算實現中可預計算的參數；

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

2.如權利要求1所述的方法，其特征在于，步驟B中，所述多項式乘法實現方案為稀疏乘法、基于NTT負折疊卷積的多項式乘法、基于NTT的多項式乘法或基于FFT的多項式乘法。

3.如權利要求2所述的方法，其特征在于，所述多項式乘法實現方案為稀疏乘法時，稀疏乘法的使用條件為：S＝2。

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

5.如權利要求2所述的方法，其特征在于，所述多項式乘法實現方案為基于NTT的多項式乘法，且使用條件為：且或

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

7.如權利要求1所述的方法，其特征在于，步驟D中，舍入計算實現方案選自移位運算、傳統預計算算法和新型舍入算法；其中，若q/p是2的方冪，則舍入計算實現方案采用移位算法；若是2的方冪，則舍入計算實現方案采用新型舍入算法；否則，舍入計算實現方案采用傳統預計算算法。