[發明專利]一種應用在格密碼加密的多項式乘法計算方法

在審

• 申請號: 202211238942.4
• 申請日: 2022-10-14
• 公開（公告）號: CN115454380A
• 公開（公告）日: 2022-12-09
• 發明（設計）人: 黃海;陳洋;于斌;劉志偉;趙石磊
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: G06F7/523
• 分類號: G06F7/523;G06F7/544;G06F17/14;G06F17/15
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種應用在格密碼加密的多項式乘法計算方法，其特征在于，所述方法包括步驟：

將預處理操作及模乘因子與NTT變換合并，得到調和NTT變換，然后分別對輸入的多項式a(x)和b(x)進行調和NTT變換，得到NTT域中的多項式A(x)和B(x)；

對得到的A(x)和B(x)進行逐點相乘得到C(x)，C(x)是多項式環Z_q/xⁿ+1的多項式，q是多項式環的模數；

對得到的C(x)進行調和INTT得到多項式a(x)和b(x)相乘的結果c(x)。

2.根據權利要求1所述的基于NTT和INTT多項式乘法計算方法，分別對輸入的多項式a(x)和b(x)進行調和NTT變換，得到NTT域中的多項式A(x)和B(x)，包括：

步驟1：輸入a(x)經過位反轉的系數變量a，調和NTT變換的傳輸級數L滿足1≤L≤log₂n條件時，并且m＝2^L，執行步驟2；

步驟2：執行L＝L+1，控制旋轉因子個數的J滿足0≤J≤2^L-1-1條件時執行步驟3；

步驟3：執行J＝J+1，每個旋轉因子的參與運算的蝶形單元個數為K，K滿足0≤K≤n-1條件時，執行步驟4；

步驟4：執行計算蝶形單元步驟：

K以m為步進長度參與蝶形運算，執行K＝K+m，當K＞n-1時，跳轉到步驟2；當J＞2^L-1-1時，跳轉到步驟1；當L＞log₂n時執行步驟5；

步驟5：執行a＝A，得到調和NTT變換結果；將b(x)帶入步驟1中的a(x)，最后輸出B(x)。