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

有效

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

本發明公開了一種后量子密碼構造中環上舍入學習的通用軟件實現方法，其步驟包括：A、設定RLWR參數N、f、p、q、S，以及實際運行平臺的CPU位數B；B、根據參數N、f、q、S、B，選取一多項式乘法實現算法，記為PMA，生成該多項式乘法實現方案中可預計算的參數；C、根據參數q和已選取的多項式乘法的實現方案PMA，選取一可用模約化方法作為模約化的實現方案，記為MRA；D、根據參數p、q選取一舍入計算實現方法，記為RA，生成該舍入計算實現方案中可預計算的參數；E、對于輸入的多項式a(x)和s(x)，計算并輸出RLWR分布中的對應值b(x)。

技術領域

本發明屬于后量子格密碼領域，特別是涉及一種后量子密碼構造中環上舍入學習的通用軟件實現方法。

背景技術

隨著量子計算機的深入研究和快速發展，互聯網中廣泛部署的傳統公鑰密碼體制面臨被徹底攻破的風險，發展能抵抗量子攻擊的后量子公鑰密碼體制是當前密碼學界的研究及應用熱點之一。現有構造后量子密碼體制的底層數學資源包括：格、多變量方程、超奇異橢圓曲線同源問題、糾錯碼、哈希函數等，目前公開的幾類后量子密碼體制中，格密碼憑借適用性廣泛、可并行實現以及存在最壞情形下底層困難問題的安全性歸約等優勢，被認為是最有前景的后量子公鑰密碼候選方案之一。

舍入學習(Learning with Rounding，LWR)和環上舍入學習(Ring Learning withRounding，RLWR)作為具有確定誤差的底層函數，是基于格的后量子密碼原語的重要構造單元，目前已廣泛應用于低深度偽隨機函數、有損陷門函數、確定性公鑰加密和密鑰交換協議等基礎后量子密碼構造。由于去除了帶錯學習(Learning with Error，LWE)中的隨機誤差采樣模塊，相同安全等級下基于LWR的密碼體制實現效率相對較高，此外還具有對計算資源需求較少、受側信道攻擊風險較低等優勢。在此基礎上，RLWR密碼體制能夠在減小密文長度、提升實現效率的情況下達到與LWR密碼體制基本相當的安全性，因此，已有的格密碼方案設計大部分采用了環結構，例如NIST后量子密碼標準算法征集中的Lizard、Round2、Round5和SABER都是采用環結構的LWR方案。

RLWR分布定義為()，其中a和s是多項式環上的多項式，f(x)為N次首一多項式，正整數q≥p≥2，舍入計算即映射假設多項式a的系數多項式s的系數RLWR分布中b(x)的計算可大致分為三步：首先計算整數域上的多項式乘法，即計算b₁(x)＝a(x)·s(x)；然后對b₁(x)執行模多項式和模整數操作，即計算b₂(x)＝((b₁(x)mod f(x))mod q)；最后計算b₂(x)的舍入值，即因此，RLWR實現通常涉及多項式乘法、模約化和舍入計算三項基礎操作。

整數域上常用多項式乘法快速實現算法有Karatsuba、Toom-Cook、稀疏乘法、快速傅里葉變換(Fast Fourier Transform，FFT)以及數論變換(Number TheoreticTransform，NTT)，其中NTT乘法算法和FFT乘法算法的理論時間復雜度最低，稀疏乘法算法的效率取決于多項式系數的稀疏程度。實際中稀疏乘法算法和NTT乘法算法的效率可以達到較優水平，但二者均存在一定的限制條件：稀疏乘法算法只適用于其中一個輸入多項式的系數取自0-1分布的RLWR；NTT算法需要在上進行運算，其中間值(特別是中的兩個整數在整數域上的乘積)不能超過計算機能直接處理的整數上界，即NTT模數M存在上界，因此NTT乘法算法只適用于參數N、q、S較小的RLWR。

模約化操作包括模多項式和模整數。注意，采用特殊多項式乘法實現方案時，可省略模約化操作：若采用了基于NTT負折疊卷積的多項式乘法算法，則可省略模多項式操作；若多項式乘法采用了模數M＝q的NTT或NTT負折疊卷積，則可省略模整數操作。模首一多項式通常可采用減法迭代算法實現。模整數快速實現方法有Montgomery算法、Barrett算法、按位與運算和無優化的模運算，其中按位與運算的效率最高，但只適用于q為2的方冪的RLWR。