[發明專利]一種基于格的公鑰加密方法

有效

• 申請號: 201910340234.3
• 申請日: 2019-04-25
• 公開（公告）號: CN110138752B
• 公開（公告）日: 2021-08-13
• 發明（設計）人: 張江;郁昱;范淑琴;張振峰;楊糠
• 申請（專利權）人: 北京信息科學技術研究院
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L9/08
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 司立彬

本發明公開了一種基于格的公鑰加密方法。本發明首先提出一類非對稱模帶錯誤學習(AMLWE)數學困難問題，也提供了該類數學困難問題的變種和一般化定義。通過基于AMLWE數學困難問題，本發明提出了一種格上選擇明文安全的公鑰加密方法。基于該加密方法，本發明也提供了選擇密文安全的密鑰封裝機制以及選擇密文安全的公鑰加密方法。本發明設計的公鑰加密方法和密鑰封裝機制具有可證明安全、抵抗量子計算機攻擊、公鑰和密文長度短、計算效率高、參數選取靈活等特點和優勢。利用通用的轉換方法，本發明也提供了(認證)密鑰交換協議。

技術領域

本發明屬于密碼學中的公鑰加密領域，涉及使用格密碼學中的相關技術，具體表現為一種基于格的公鑰加密方法，能抵抗量子計算機攻擊。

背景技術

公鑰加密已在許多實際應用中得到廣泛部署。根據Shor算法，當量子計算機出現時，已部署的基于RSA或橢圓曲線的公鑰加密方法將不再安全。量子計算機的快速發展促使我們設計抗量子安全的公鑰加密方法。當前，主流的抗量子安全公鑰加密方法是基于格或者編碼上的數學困難問題。從效率和安全性綜合來看，基于格的公鑰加密方法是相當有前途的候選方法之一，并得到了國內外學者的廣泛研究。在數學中，格是一種離散的加法子群。由于特殊的代數結構，格上有很多難以求解的困難問題，例如最短向量問題。基于格的公鑰加密方法是指基于格上數學困難問題設計的公鑰加密方法，具有抵抗量子計算機攻擊的能力。

公鑰加密方法的設計和安全性是建立在數學困難問題之上的。當前，格上公鑰加密方法的安全性大多是建立在Regev提出的帶錯誤學習問題(Learning with Errors，LWE)的困難性之上。簡單來說，帶錯誤的學習問題與求解模整數方程有關系。令為正整數，為正實數，是以α為參數的噪音分布(通常為高斯分布，或與其相近的二項分布)。計算性帶錯誤的學習問題LWE_n,m,q,α目標是對于隨機選擇的矩陣向量以及噪音向量給定樣本求解秘密向量判定性LWE問題是區分(A,b＝As+e)和上均勻隨機的元組。在一定參數下，判定性LWE問題和計算性LWE問題在多項式時間意義下是等價的。

在特定參數下，求解LWE問題在平均情況下的復雜度比求解格上某些問題(例如，最短向量問題)在最壞情況下的復雜度還高。這種平均困難性到最壞困難性的聯系特性實際上是基于格上困難問題的密碼方法相對于基于其他困難問題的密碼方法獨有的優勢之一。由于目前已知的格上困難問題的量子求解算法與傳統經典求解算法相比在計算復雜度上并沒有本質的降低，以至于大多數國內外研究學者都傾向于相信格上問題是困難的，以及基于格上困難問題設計的密碼方法能夠抵抗量子計算機攻擊。此外，當秘密向量s并不是隨機均勻地選自于時，相應LWE的變種問題(稱之為正規形LWE問題)也是困難的。特別地，當秘密向量與噪音向量e選自于相同的分布時，正規形LWE問題和標準的LWE問題在多項式時間的意義上是等價的。由于正規形LWE問題能夠更好地控制噪音增長，因此在文獻中被廣泛用于設計公鑰加密方法。

為了獲得更好的效率，環上的LWE(RLWE)困難問題也被提出。RLWE問題定義在n-1次多項式環R_q上。給定正實數以及定義RLWE分布為計算性RLWE數學困難問題RLWE_n,q,l,α是指隨機選取在有l個樣本的條件下計算出秘密值判定性RLWE數學困難問題的目標是區分分布B_s,α和上的均勻分布。然而，RLWE問題使用了特殊的環結構，而這種環結構可能被敵手利用來求解相應的數學困難問題。從而，為了安全性和效率的折中，模LWE(MLWE)數學困難問題被密碼研究者提出。給定正整數以及正實數對于隨機選取的矩陣和向量計算性MLWE問題MLWE_n,q,k,l,α的目標是給定樣本輸出秘密向量判定性MLWE問題的目標是區分樣本(A,b＝As+e)和選自于上均勻分布的元組。

發明內容

針對當前公鑰加密技術中存在的不足，本發明的目的在于提供一種基于格的公鑰加密方法。

本發明包括以下四個方面的內容：

1)定義非對稱MLWE(即AMLWE)數學困難問題；