技術(shù)領(lǐng)域

本發(fā)明涉及一種統(tǒng)一驗(yàn)證多個(gè)數(shù)字簽名的技術(shù)。?

背景技術(shù)

在數(shù)字簽名中，簽名者對于簽名對象的電子數(shù)據(jù)，使用簽名者保密的簽名生成密鑰生成簽名數(shù)據(jù)，簽名驗(yàn)證者使用公開的簽名驗(yàn)證密鑰對簽名數(shù)據(jù)進(jìn)行解密，通過與成為簽名對象的電子數(shù)據(jù)進(jìn)行比較，可以檢測簽名者的真?zhèn)我约笆欠翊嬖趯﹄娮訑?shù)據(jù)的竄改等。?

在這樣的數(shù)字簽名中，在進(jìn)行驗(yàn)證時(shí)必須反復(fù)進(jìn)行復(fù)雜的處理(數(shù)學(xué)計(jì)算)，例如在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.(稱為文獻(xiàn)1)記載的技術(shù)中，通過統(tǒng)一驗(yàn)證多個(gè)數(shù)字簽名，提高數(shù)字簽名的驗(yàn)證處理的效率。?

下面，對文獻(xiàn)1中記載的統(tǒng)一驗(yàn)證方法進(jìn)行說明。?

此外，下面將G作為把位數(shù)設(shè)為q(q為大的素?cái)?shù))的有限循環(huán)群，將g作為群G的生成源。并且設(shè)(x_i，y_i)(i為表示順序的腳標(biāo)，是滿足1≤i≤n的自然數(shù))為用于驗(yàn)證是否滿足下式(1)的組(批量實(shí)例(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)?

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

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

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

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

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

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

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