電子署名は, 任意のメッセージに対する署名を入手することのできる攻撃者でも, 新たなメッセージに対する署名を生成することができないとき, 選択平文攻撃のもとで存在的偽造不可能であると言われる. しかし, 存在的偽造不可能性は電子署名に関する完璧な安全性ではない. 2002 年には, 強存在的偽造不可能性と呼ばれる, より強い安全性の概念が提案された. 任意のメッセージに対する署名を入手することのできる攻撃者でも, 新たなメッセージだけでなく, 過去に入手したメッセージに対しても, 新たに署名を生成することができないとき, 選択平文攻撃のもとで強存在的偽造不可能であると言われる. つまり過去に署名したメッセージに対する署名の偽造を防ぐために, 電子署名は強存在的偽造不可能性をみたしていることが望ましい. しかし, これまで提案されている多くの電子署名は存在的偽造不可能ではあるが, 強存在的偽造不可能ではない.
現在, 多くの研究者によって存在的偽造不可能な署名から強存在的偽造不可能な署名を構成する方法が研究されている. また, 存在的偽造不可能性, 強存在的偽造不可能性の概念はID ベース署名(IBS) にも適用される. IBS とは, メールアドレスなどの個人に特有のID を公開鍵(検証鍵) として利用できる電子署名である. 例えば, Paterson らによって, 強存在的偽造不可能ではないが, 存在的偽造不可能が証明されるIBS が提案されている.
本研究の研究対象は通常の電子署名だけでなく, IBS に関しても強存在的偽造不可能な署名を構成することができる効率的な構成法である. 近年, Bonehらによって強存在的偽造不可能な署名の構成法が提案された. この構成法の安全性は標準モデルによって証明される. この構成法は衝突困難ハッシュ関数と離散対数問題を利用して構成される. しかし, Boneh らの方法はpartitioned と呼ばれるタイプの署名方式にしか適用できない. 多くの離散対数問題ベースの署名方式はpartitioned であるが, すべてがpartitionedではない. 例えばDSS 署名はpartitioned ではない. Boneh らの方法において, 衝突困難ハッシュ関数の代わりに汎用一方向性ハッシュ関数(これは衝突困難ハッシュ関数よりも現実的なプリミティブである) を利用する方式を松田らが提案した. しかし, 彼らの構成法はsimulatable partitioned な存在的偽造不可能な署名方式しか利用できない. 彼らの構成法では基にしている署名方式の鍵ペア(公開鍵と秘密鍵)に, 何らかのパラメータを加えて新たな鍵ペアとするため, 存在的偽造不可能なIBS から強存在的偽造不可能なIBS を構成できない. 一方, 寺西らによって提案された構成法はrandomized トラップドアハッシュ関数(カメレオンコミットメントとも呼ばれる) を利用して存在的偽造不可能な署名から強存在的偽造不可能な署名を構成する. 同様の構成法を同時期にSteinfeld らも提案している. どちらの構成法もpartitioned署名だけでなく, 任意の署名に対して強存在的偽造不可能な署名を構成することができる. しかし, 彼らの構成法も基にしている署名方式の鍵ペアに, 何らかのパラメータを加えているため, 強存在的偽造不可能なIBS を構成できない. 実際, 彼らの構成法によって強存在的偽造不可能なIBS を構成しようとすると, ID ベースパラダイムのもとでのrandomized トラップドアハッシュ関数が必要であるが, そのようなrandomized トラップドアハッシュ関数は提案されていない. 基にしている存在的偽造不可能な署名の鍵ペアに何らかのパラメータを追加しない構成法がHuang らによって初めて提案された. 彼らの構成法は強存在的偽造不可能なone-time 署名( 公開鍵, 秘密鍵を1 回しか利用しない署名方式) を利用することによって存在的偽造不可能な署名から強存在的偽造不可能な署名を構成する. 彼らの構成法は, 強存在的偽造不可能なIBS も構成することが可能である. しかし, 彼らの構成法によって生成される署名は, 基にしている存在的偽造不可能な署名方式によって生成される署名に対して, 利用している強存在的偽造不可能なone-time 署名によって生成される署名と公開鍵(特に, one-time 署名の公開鍵は多くのパラメータを含むため, 公開鍵サイズは大きい) が加えられるため, この構成法によって生成される署名のサイズは非常に大きくなる. つまり, Boneh, 松田, 寺西, Steinfeld, Huang による構成法は, (simulatable) partitioned property, randomized トラップドアハッシュ関数, 強存在的偽造不可能なone-time 署名などの特別な特性や関数を必要とする. また, Boneh, 松田, 寺西, Steinfeld による構成法は通常の電子署名にしか利用できず, 強存在的偽造不可能なIBS を構成することはできない. 一方, Huangらによる構成法は強存在的偽造不可能なIBS を構成するが可能であるが,署名サイズが大きくなってしまう.
本稿では, 汎用性があり, つまり通常の署名方式だけでなくIBS に関しても強存在的偽造不可能な署名を構成でき, 構成要素に関しても特別な性質や関数を必要としないシンプルな構成法を提案する.

Top