[發明專利]用以驗證數字簽名的系統和方法

有效

• 申請號: 201980091523.2
• 申請日: 2019-08-01
• 公開（公告）號: CN113424492B
• 公開（公告）日: 2023-01-24
• 發明（設計）人: P·穆克赫吉;Y·陳;N·杰尼塞
• 申請（專利權）人: 維薩國際服務協會
• 主分類號: H04L9/32
• 分類號: H04L9/32;H04L9/08;H04L9/30
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 徐倩;錢慰民

公開了生成基于格的驗證矩陣和簽名向量的技術。方法使得生成裝置能夠對小工具矩陣進行采樣，然后生成縮減的小工具矩陣。所述生成裝置然后可以對陷門矩陣進行采樣，并且使用所述陷門矩陣和所述縮減的小工具矩陣來生成驗證矩陣。除接收消息之外，發送裝置還可以從所述生成裝置接收所述陷門矩陣和所述驗證矩陣。所述發送裝置然后可以使用所述陷門矩陣和所述驗證矩陣來生成用于所述消息的簽名向量。驗證裝置可以接收所述驗證矩陣、所述消息和所述簽名向量。所述驗證裝置可以使用所述驗證矩陣和所述簽名向量來驗證所述消息。

相關申請交叉引用

本申請是2019年2月8日提交的第62/803,325號美國臨時申請的國際申請并且要求其申請日的權益，所述美國臨時申請以全文引用的方式并入本文中。

背景技術

當今許多密碼體制——例如RSA加密——基于質數分解或模冪運算等問題。這些問題對于常規計算機來說是難以解決的，但對于量子計算機來說可能不是難以解決的。因此，量子計算的新進展可能會使基于這些問題的密碼體制不安全。需要基于傳統計算機和量子計算機均難以解決的問題的新密碼體制。

基于格的問題可以用作密碼體制的基礎。格問題的一個實例可以是短整數解問題，其涉及在點的n維格中尋找最短向量。格問題對于常規計算機和量子計算機兩者可能均是難以解決的。然而，針對基于格的密碼體制計算密碼密鑰可能是計算昂貴的，并且可能會產生大的密鑰，所述大的密鑰還會使得難以對消息進行簽名和驗證消息。因此，需要使基于格的密碼更高效。

本公開的實施例單獨地和共同地解決了這些和其它問題。

發明內容

本公開的一些實施例涉及生成基于格的密碼驗證密鑰和相關聯陷門矩陣的方法。生成裝置可以生成小工具矩陣所述生成裝置然后可以刪除所述小工具矩陣的第一l列以生成縮減的小工具矩陣然后，所述生成裝置可以對分布進行采樣以形成陷門矩陣所述陷門矩陣可以充當秘密密鑰以用于生成數字簽名，并且可以是近似陷門。所述生成裝置然后可以使用所述縮減的小工具矩陣和所述陷門矩陣來生成驗證矩陣所述生成裝置可以將所述驗證矩陣發送給一個或多個驗證裝置。如果數字簽名是使用所述陷門矩陣生成的，則所述一個或多個驗證裝置可以使用所述驗證矩陣來驗證發送裝置生成的所述數字簽名以對消息m進行簽名。

本公開的其它實施例涉及生成基于格的簽名的方法。發送裝置可以接收消息m。所述消息可以是散列h(m)，或所述發送裝置可以對所述消息m進行散列以生成所述散列h(m)。所述發送裝置還可以存儲驗證矩陣和陷門矩陣所述發送裝置可以使用所述驗證矩陣和所述陷門矩陣來生成簽名向量可以生成所述簽名向量使得對于一些模數q和誤差向量滿足關系可以選擇所述模數q以給出所期望水平的數據安全型(例如，選擇q＝2²⁴可以給出100位的安全性)。簽名裝置可以將所述消息m和所述簽名向量發送給驗證裝置。所述驗證裝置可以預先接收到所述驗證矩陣或可以從所述發送裝置接收所述驗證矩陣并且可以使用所述驗證矩陣來驗證所述簽名向量是由所述發送裝置生成的。這可以允許所述驗證裝置驗證所述消息m也來自所述發送裝置。

本公開的其它實施例涉及驗證基于格的簽名的方法。驗證裝置可以存儲驗證矩陣所述驗證裝置還可以從發送裝置接收消息m和簽名向量所述消息可以是散列h(m)，或所述驗證裝置可以對所述消息m進行散列以生成所述散列h(m)。所述驗證裝置可以通過對于一些模數q求解來計算誤差向量并且量化所述誤差向量的大小。所述驗證裝置可以將所述誤差向量與閾值進行比較，并且在所述誤差向量小于所述閾值的情況下驗證所述簽名向量例如，如果誤差向量的長度小于所述散列h(m)的維度。

本公開的其它實施例涉及系統以及與上文所描述的方法相關聯的計算機可讀介質。

在下文參考附圖和具體實施方式進一步詳細描述本發明的這些和其它實施例。

附圖說明

圖1示出了根據一些實施例的系統的框圖。

圖2示出了根據一些實施例的用于基于格的驗證矩陣和陷門生成的一般流程圖。