格上計算問題的算法與複雜性研究

《格上計算問題的算法與複雜性研究》是依託杭州電子科技大學，由胡耿然擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：格上計算問題的算法與複雜性研究
• 項目類別：青年科學基金項目
• 項目負責人：胡耿然
• 依託單位：杭州電子科技大學

項目摘要

基於格的公鑰密碼體制是後量子時代最重要的公鑰密碼體制，也在如今的雲計算時代下有廣泛的套用，可是對其安全性的研究還不充分。為了更好地評估基於格的公鑰密碼體制的理論安全性，本項目擬研究格上計算問題的算法與複雜性。在算法方面，我們擬研究如何更合理地定義、刻畫及生成隨機滿秩整格，用於評測及預測LLL等一般格算法的實際輸出質量，為基於格的公鑰密碼體制的參數選取提供參考；我們還研究如何利用理想格的特殊結構設計其上SVP/CVP的特定求解算法，用於分析基於理想格上格問題的公鑰密碼體制；而在複雜性方面，我們擬研究如何改進Micciancio給出的證明SVP是NP難問題的隨機歸約，用於更有效地評估基於格的公鑰密碼體制的安全性。因此，本項目具有重要的科學意義和套用價值。

結題摘要

本項目主要研究了格上計算問題SVP, CVP的算法與複雜性。通過反向採樣，提出了一種更為高效的隨機整格生成算法，用作格算法的輸入，可用於測評格算法的平均輸出質量；對於低維數的主理想格，證明其SVP解的格基表示係數範圍較小，其SVP解可直接給出，CVP也有類似結果；對於n維格L與n維整向量s，研究了L+s所包含的短向量個數的分布，該分布與L與s均有很強的相關性。