《實用後量子線性公鑰加密的錯誤嵌入與通用構造》是依託西安電子科技大學，由王保倉擔任項目負責人的面上項目。
基本介紹
- 中文名：實用後量子線性公鑰加密的錯誤嵌入與通用構造
- 項目類別：面上項目
- 項目負責人：王保倉
- 依託單位：西安電子科技大學
中文摘要,結題摘要,
中文摘要
傳統公鑰密碼不能抗量子攻擊且大多速度慢難以套用於資源受限的計算環境，本項目研究抗量子攻擊的線性公鑰加密算法的新型設計理論與分析技術。內容包括：提出此類公鑰密碼的線性性安全度量工具，為線性公鑰加密函式的設計提供更強的安全支撐，提出新的陷門單向函式，構造新的基於線性丟番圖方程的公鑰密碼，證明該密碼的抗格攻擊安全性；定義新的困難問題，證明新問題與已有問題的規約關係，研究線性公鑰加密的錯誤嵌入模式，構造新的實用公鑰密碼；研究具有錯誤嵌入的線性公鑰加密函式特點，定義新的安全模型，提出通用安全構造方案，完成NTRU的可證明安全性；提出格上的子集最短向量問題，把子集和問題規約到該問題上，對STOC 2009上的基於稀疏子集和問題的Gentry同態加密算法進行攻擊。該項目注重研究的可持續性和可移植性、理論和技術上的前瞻性及套用的有效性。研究成果將為具有線性結構的後量子公鑰密碼提供系統的設計理論和分析技術。
結題摘要
傳統公鑰密碼不能抗量子攻擊且大多速度慢難以套用於資源受限的計算環境，本項目研究抗量子攻擊的線性公鑰加密算法的新型設計理論與分析技術。內容包括：提出線性公鑰加密的線性性安全度量工具，構造新的基於線性丟番圖方程的公鑰密碼；定義新的困難問題，證明新問題與已有問題的規約關係，構造新的實用公鑰密碼；研究公鑰密碼底層數學問題的困難性，提出針對底層數學困難問題的攻擊算法；構造基於格公鑰密碼的套用方案，完成方案的安全性和效率分析與比較。主要結果包括：提出一個新的線性公鑰加密的密碼原語：原像可選擇陷門函式，並給出一個具體的構造，安全性分析指出，即使底層的緊湊背包問題是易解的，多項式時間的攻擊者也不能攻破該算法的安全性；對Wang, Wu和Hu在2007年提出的一個機率公鑰加密算法進行了改進，改進後的加密算法能夠抵抗Youssef的和Lee的攻擊；提出了具有雙陷門解密機制的抗適應性選擇密文攻擊安全的公鑰加密算法。引入了兩個新問題，廣義RSA問題和計算廣義GSA問題，證明了標準RSA問題和廣義RSA問題之間的等價性。基於計算廣義RSA問題，提出了一個具有雙陷門解密機制的公鑰加密算法GenRSA。在隨機預言機模型下，證明了GenRSA的抗適應性選擇密文攻擊的安全性；定義了模RSA數構成的四元數環上的求根問題並提出了一個數字簽名算法，證明了該數字簽名算法的安全性；提出了對背包公鑰密碼0/255的兩種攻擊，證明了使用連分式算法在多項式時間內恢復出背包公鑰密碼0/255在密鑰生成過程中所使用的模乘數。證明了背包公鑰密碼0/255可以徹底攻破；通過背包公鑰密碼0/255的公鑰可以構造一個格，而背包公鑰密碼0/255對應的私鑰可以通過使用格規約算法尋找我們所構造出來的格上的最短向量重構出來；考慮了多變數公鑰密碼中的多項式線性等價問題(PLE)並討論了PLE的相關密碼學特性，給出了一個求解PLE問題的新算法：篩法，算法說明不能由PLE問題設計安全的多變數公鑰加密算法；我們給出了F5算法的一個推廣F5GEN，然後證明了F5GEN算法在有限步內終止，進而解決了F5算法的終止問題；構造了一系列基於格公鑰密碼的套用方案，包括線性同態簽名算法、群組密鑰協商協定、強指定驗證者的格基簽名算法、代理（重）簽名算法、無證書加密算法等。研究成果豐富了線性公鑰加密的設計理論，為後量子公鑰密碼提供系統的設計理論和分析技術。
