[發明專利]統一驗證裝置、程序以及統一驗證方法

有效

• 申請號: 200810082825.7
• 申請日: 2008-02-28
• 公開（公告）號: CN101335625A
• 公開（公告）日: 2008-12-31
• 發明（設計）人: 伯田惠輔;佐藤尚宜
• 申請（專利權）人: 株式會社日立制作所
• 主分類號: H04L9/32
• 分類號: H04L9/32
• 代理公司: 北京銀龍知識產權代理有限公司
• 代理人: 許靜

技術領域

本發明涉及一種統一驗證多個數字簽名的技術。?

背景技術

在數字簽名中，簽名者對于簽名對象的電子數據，使用簽名者保密的簽名生成密鑰生成簽名數據，簽名驗證者使用公開的簽名驗證密鑰對簽名數據進行解密，通過與成為簽名對象的電子數據進行比較，可以檢測簽名者的真偽以及是否存在對電子數據的竄改等。?

在這樣的數字簽名中，在進行驗證時必須反復進行復雜的處理(數學計算)，例如在M.Bellare，J.Garay，and?T.Rabin，“Fast?Batch?Verification?forModular?Exponentiation?and?Digital?Signatures”，Advances?inCryptology-EUROCRYPT?1998，LNCS?1403，pp.236-250，1998.(稱為文獻1)記載的技術中，通過統一驗證多個數字簽名，提高數字簽名的驗證處理的效率。?

下面，對文獻1中記載的統一驗證方法進行說明。?

此外，下面將G作為把位數設為q(q為大的素數)的有限循環群，將g作為群G的生成源。并且設(x_i，y_i)(i為表示順序的腳標，是滿足1≤i≤n的自然數)為用于驗證是否滿足下式(1)的組(批量實例(batch?instance))。?

gxi=yi···(1)]]>

其中，對于各i(i＝1，...，n)，x_i、y_i分別滿足下式(2)以及式(3)。?

0≤x_i≤q-1...(2)?

y_i∈G...(3)?

批量實例(x_i，y_i)(i＝1，...，n)在對于各i(i＝1，...，n)滿足式(1)時稱為“有效”，否則稱為“無效”。此外，在批量實例有效時，判定簽名數據也“有效”，在批量實例無效時，判斷簽名數據也無效。?

此外，在統一驗證中，始終將有效的批量實例作為“有效”來接受，但有時也以非常小的概率將無效的批量實例作為“有效”來接受。而且，在將無效? 的批量實例作為“有效”來接受的概率的上限最高為1/2^m(m為正整數)時，m被稱為安全級別。根據近年的計算機能力，已知希望將m最好設定為80左右。此外，我們知道安全級別m越大，數字簽名的安全性越高。?

這里，在通常的簽名驗證中，對于與各i(i＝1，...，n)對應的數字簽名，分別驗證是否滿足式(1)，相對于此，在文獻1記載的Random?Subset?Test中，驗證是否滿足如下式(4)以及(5)。?

gΣsixi=Πyisi···(4)]]>

s_i＝0或者1(i＝1，...，n)...(5)?

這里，如式(5)所示，對于各i(i＝1，...，n)，假設s_i為隨機選擇0或者1。?

另外，文獻1中記載的Small?Exponents?Test驗證是否滿足下式(6)以及(7)。?