[發明專利]一種基于理想格的新型增量簽名方法

在審

• 申請號: 202011319580.2
• 申請日: 2020-11-23
• 公開（公告）號: CN112383394A
• 公開（公告）日: 2021-02-19
• 發明（設計）人: 朱錦德;吳開貴
• 申請（專利權）人: 重慶大學
• 主分類號: H04L9/08
• 分類號: H04L9/08;H04L9/32
• 代理公司: 重慶市信立達專利代理事務所(普通合伙) 50230
• 代理人: 陳炳萍

本發明專利公開了一種基于理想格的新型增量簽名方法，具體涉及格密碼學的技術領域。一種基于理想格的新型增量簽名方法，包括如下的步驟：系統參數初始化、并生成公私鑰；是否存在標準簽名方案生成的簽名；獲取標準簽名下的原簽名σ及對應的消息，對新消息μ通過增量方案生成對應的新簽名σ′，對消息和生成的簽名執行驗證算法Verify(PK，μ，σ)，判斷輸出是否為1。采用本發明技術方案解決了傳統計算機無法抵抗量子計算機攻擊的問題，可用于在現有計算機中高效的加密簽名。

技術領域

本發明涉及格密碼學的技術領域，特別涉及一種基于理想格的新型增量簽名方法。

背景技術

隨著當下量子計算機的研制的迅速進展，量子算法亦是相應得以巨大突破。在量子計算模型下，經典數論假設的密碼體系(如大整數分解，計算有限域/橢圓曲線上的離散對數問題等)，存在多項式時間(PPT)的量子算法，換而言之，經典數論密碼體系受到了極大的沖擊，將有可能成為舊時代的眼淚。因此，能夠抵抗量子計算機攻擊的密碼——“后量子”或“抗量子”密碼便應運而生，而格密碼則是一類備受關注的抗量子計算攻擊的公鑰密碼體制。

由于使用具有代數結構的格可以使密碼學方案獲得顯著的效率提高，而且格上經典困難問題-誤差學習問題(LWE)和小整數解問題(SIS)的強大和多樣性，格密碼學在過去幾十年中得到了顯著的發展，格上數字簽名也成為近年來學術界關注的熱點之一。從理論上講，任何一個單向函數都可以用來構造數字簽名，因此直接在Ajtai的開創性工作的基礎上，衍生出了大量基于格上困難問題的數字簽名方案。但是通用結構帶來了嚴重的效率低下問題，格密碼方案的參數通常包含幾個維向量。如果使用一般的數字簽名構造，它需要許多單向函數，這導致了在使用代數格時生成了需要存儲空間的巨大數字簽名。因此，在格困難問題的基礎上尋找“短”的簽名的實用構造，如由單個格向量構成的格簽名，自格密碼學出現以來就成為一個非常關鍵的問題。

理想格則是由格的理想構成的一類格。為了方便介紹理想格，我們從兩個常見的格上困難問題，即LWE問題和SIS問題切入。LWE問題的一個實例是由一個隨機n×m的整數矩陣A和一個向量b定義的，滿足b＝A^Ts+e mod q，其中s為一個秘密向量，e為一個小噪聲向量，困難問題是尋找這個向量s。作為LWE的一個“對偶”問題，SIS問題的一個實例是由相同的隨機矩陣A定義的，其要求尋找一個短向量x使得Ax＝0 mod q。Ring-LWE和Ring-SIS分別是LWE和SIS的“環”上版本，分別是針對某些結構化矩陣A定義的LWE和SIS的具體實例，矩陣A詳細的介紹如下所述：

在理想格或所謂的“環設置”中，上面的矩陣A需要有一些額外的代數結構。一個常用的例子是將A的每一列解釋為(n-1)次多項式p(x)的系數，并且要求在A的某些列中也包含xp(x)mod(xⁿ+1))。在這種情況下，A的矩陣乘法等價于多項式乘法。因此，我們可以把每個向量v看作環中的一個元素v，以及A的每個n×n的子矩陣視為上的一個環元素a_i。

由于理想格的代數結構，基于理想格的密碼體制(安全性基于Ring-LWE或Ring-SIS困難性假設)比一般格中的密碼體制更有效，表現在：

1.由于每個n×n子矩陣現在被表示為一個環元素，因此一些原本是矩陣的參數的大小被減小了一個因子n；

2.中環元素的乘法可以通過FFT(快速傅立葉變換)在硬件上實現。

因此，理想格的使用是構建格上高效密碼學方案的重要途徑。