公鑰密碼體制的格分析方法研究

《公鑰密碼體制的格分析方法研究》是依託清華大學，由畢經國擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：公鑰密碼體制的格分析方法研究
• 依託單位：清華大學
• 項目負責人：畢經國
• 項目類別：青年科學基金項目

項目摘要

隨著 LLL 格基約化算法的提出，在過去的三十多年裡格分析方法成功對背包型密碼體制、特殊情形下的 RSA、DSA 等多個公鑰密碼體制的安全性進行了評估。格分析方法的基本思想是將影響公鑰密碼體制的安全性的核心數學問題轉化成格基約化算法可求解的短向量等問題來解決。格基約化算法是格分析方法的基本工具，本項目將從與密碼體制安全性緊密相關的密碼格的特殊性質入手，著重研究求解密碼格的短向量等問題的格基約化算法，進而達到更精確評估現有公鑰密碼體制安全性的研究目標。除了對現有算法最佳化和改進，並探索新的格基約化算法外，本項目還將利用理想格、循環格等密碼格的特殊結構、格不變數間的固有性質等，給出更有針對性、更有效的格基約化算法。通過研究公鑰密碼體制在廣播攻擊、重放攻擊等分析模型下的格分析方法的安全性，旨在給出從格分析的角度更精確的公鑰密碼體制的安全性評估，為將來公鑰密碼體制的設計及安全參數的選取積累經驗。

結題摘要

在過去的三十多年裡，格分析方法成功對多個著名的公鑰密碼體制的安全性進行了評估。格基約化算法是格分析方法的基本工具，本項目從與密碼體制安全性緊密相關的密碼格的特殊性質入手，著重研究求解密碼格的短向量等問題的格基約化算法，進而達到更精確評估現有公鑰密碼體制安全性的研究目標。首先，本項目利用格分析方法對基於近似公因子問題的全同態加密算法、基於 Ring-LWE 問題的輕量級公鑰加密算法等多個密碼體制的安全性進行評估；其次，本項目對現有的經典格基約化算法的性質及典型困難問題的計算複雜度進行了估計；最後，利用特殊格的性質，給出了利用這些性質分析解決相應的困難問題的各種套用。 本項目通過著重對求解密碼格的短向量問題的格基約化算法進行研究，從格分析方法的角度對公鑰密碼體制特別是格公鑰密碼體制的安全性進行分析，為將來公鑰密碼體制的設計及安全參數的選取積累經驗。