(57)【要約】【課題】  従来の落とし戸付一方向性置換ｆを用いた多重署名に対し、乱数成分の使用により帰着効率を向上させ鍵長を短縮させ、更に乱数成分を可能な限り短く抑えても安全性証明が与えられるような簡素な処理構造の方式を提供する。【解決手段】各署名者Ｐｉは、ハッシュ関数Ｈの入力値として用いた乱数成分ｒｉを、次の署名者Ｐｉ＋１に何の処理もせず多重署名成分の一部分としてｒ１，…，ｒｉをそのまま送信する。受け取った次の署名者Ｐｉ＋１は、乱数成分ｒ１，…，ｒｉ＋１を直接ハッシュ関数Ｈの入力値として使用する事が可能となるので、多重署名生成時の処理構造及び多重署名検証時の処理構造が簡易な構造となり、その結果、乱数成分の長さが最大限抑えられた最適な安全性証明を与えた。【特許請求の範囲】
【請求項１】
署名者装置Ｐは秘密の署名鍵ｆ−１＝ｓｋ  を保持し、それに対応する公開情報ｆ＝ｐｋを公開し、ここでｆは落とし戸付一方向性置換とし、メッセージｍに対し、乱数ｒを生成し、その乱数ｒとメッセージｍに対しハッシュ演算Ｈを施してｙ＝Ｈ（ｍ，ｒ，ｐｋ）を計算し、上記ｙ＝Ｈ（ｍ，ｒ，ｐｋ）と署名鍵ｆ−１＝ｓｋ  とを用いた演算によりσ＝ｆ−１（ｙ）を計算し、そのσと乱数ｒをｍに対する署名として、ｍと共に検証者装置へ送り、検証者装置は受信した（σ，ｒ）、ｍ中のｍとｒに対しハッシュ演算Ｈを施してｙ＝Ｈ（ｍ，ｒ，ｐｋ）を計算し、受信したσを上記関数ｆの変数に代入して演算ｆ（σ）を行い、その演算結果とｙ＝Ｈ（ｍ，ｒ，ｐｋ）とが等しい値かどうかから、その（σ，ｒ）がそのｍに対する正当な署名か否かを検証するランダムオラクルモデルの仮定のもと、安全性証明が可能な電子署名方法において、上記処理を複数Ｌ’人で実行し、各署名者装置Ｐｉ（１＜ｉ≦Ｌ’）は秘密の署名鍵ｆｉ−１＝ｓｋｉを保持し、それに対応する公開情報ｆｉ＝ｐｋｉを公開し、全署名者間で共通のメッセージｍに対し、乱数ｒｉを生成し、その乱数ｒｉ、メッセージｍに対し各ハッシュ演算Ｈを施してｙｉ＝Ｈ（ｍ，ｒ１，…，ｒｉ，ｐｋ１，…，ｐｋｉ）、更に各ハッシュ値と各前署名者の署名値からρｉ＝ｙｉ◎σｉ−１を計算し、上記ρｉと署名鍵ｆｉ−１＝ｓｋｉとを用いた演算によりσｉ＝ｆｉ−１（ρｉ）を計算し、そのσｉと乱数ｒ１，…，ｒｉをｍに対する多重署名として、ｍと共に次の署名者装置に送り、以上の処理を最終署名者ＰＬ’まで繰り返し実行し、最終的には検証者装置へ送り、検証者装置は受信した（σＬ’，ｒ１，…，ｒＬ’）、ｍ中のｍとｒ１，…，ｒｉに対し各ハッシュ演算Ｈを施してｙｉ＝Ｈ（ｍ，ｒ１，…，ｒｉ，ｐｋ１，…，ｐｋｉ）を計算し、更に受信したσｉを上記関数の変数に代入して演算ρｉ＝ｆｉ＝（σｉ）を行い、更に前署名者の署名値をσｉ−１＝ｙｉ◎ρｉから計算し、以上の処理をＰｉ（Ｌ≧ｉ＞１）に対して繰り返し実行し、最終的にはｙ１＝Ｈ（ｍ，ｒ１，ｐｋ１）＝ｆｉ（σｉ）とから、最終署名者ＰＬ’から受け取った（σＬ’，ｒ１，…，ｒＬ’）がそのｍに対する正当な多重署名か否かを検証するランダムオラクルモデルの仮定のもと、安全性証明が可能な電子多重署名方法。
【請求項２】
上記処理において各署名者は各人が選択した任意の文書に多重署名を実行し、各署名者装置Ｐｉ（１＜ｉ≦Ｌ’）は秘密の署名鍵ｆｉ−１＝ｓｋｉを保持し、それに対応する公開情報ｆｉ＝ｐｋｉを公開し、各署名者が任意に選択したメッセージｍｉに対し、乱数ｒｉを生成し、その乱数ｒｉ、メッセージｍｉに対し各ハッシュ演算Ｈを施してｙｉ＝Ｈ（ｍ１，…，ｍｉ，ｒ１，…，ｒｉ，ｐｋ１，…，ｐｋｉ）、更に各ハッシュ値と各前署名者の署名値からρｉ＝ｙｉ◎σｉ−１を計算し、上記ρｉと署名鍵ｆｉ−１＝ｓｋｉとを用いた演算によりσｉ＝ｆｉ−１（ρｉ）を計算し、そのσｉと乱数ｒ１，…，ｒｉをｍ１，…，ｍｉに対する多重署名として、ｍ１，…，ｍｉと共に次の署名者装置に送り、以上の処理を最終署名者ＰＬ’まで繰り返し実行し、最終的には検証者装置へ送り、検証者装置は受信した（σＬ’，ｒ，…，ｒＬ’）、ｍ１，…，ｍＬ”中のｍ１，…，ｍｉとｒ１，…，ｒｉに対し各ハッシュ演算Ｈを施してｙｉ＝Ｈ（ｍ１，…，ｍｉ，ｒ１，…，ｒｉ，ｐｋ１，…，ｐｋｉ）を計算し、更に受信したσｉを上記関数の変数に代入して演算ρｉ＝ｆｉ（σｉ）を行い、更に前署名者の署名値をσｉ−１＝ｙｉ◎ρｉから計算し、以上の処理をＰｉ（Ｌ≧ｉ＞１）に対して繰り返し実行し、最終的にはｙ１＝Ｈ（ｍ１，ｒ１，ｐｋ１）＝ｆ１（σ１）とから、最終署名者ＰＬ’から受け取った（σＬ’ｒ１，…，ｒＬ’）がそのｍ１，…，ｍｉ対する正当な多重署名か否かを検証するランダムオラクルモデルの仮定のもと、安全性証明が可能な可変文書電子多重署名方法。
【請求項３】
上記処理において各署名者装置Ｐ１，…，ＰＬ’＝Ｇ’と限定するのではなく、Ｇ⊇Ｇ’と拡張して処理を実行し、各署名者装置が予め決められた署名順序に従うことなく、各署名者装置により任意の署名者順序を決定する事が可能なランダムオラクルモデルの仮定のもと安全性証明が可能な可変文書可変順序電子多重署名方法。
【請求項４】
秘密の署名鍵ｆｉ−１＝ｓｋｉを保持し、それに対応する公開情報ｆｉ−１＝ｐｋｉを公開する手段と、署名作成時に乱数ｒｉｊを生成する手段と、メッセージｍｉｊと乱数ｒｉｊに対しハッシュ演算Ｈを施してｙｉｊ＝Ｈ（ｍｉｊ，…，ｍｉｊ，ｒｉｊ，…，ｒｉｊ，ｐｋ１，…ｐｋｉ）（ｙｉｊ∈Ｄ）を計算する手段と、ハッシュ値ｙｉｊと前署名者の署名値σｉｊ−１からρｉｊ＝ｙｉｊ◎σｉｊ−１を計算する手段と、上記ρｉｊと署名鍵ｆｉ−１＝ｓｋｉとを用いた演算によりσｉｊ＝ｆｉ（ρｉｊ）を計算する手段と、そのσｉｊと乱数ｒｉｊ，…，ｒｉｊをｍｉｊ，…，ｍｉｊに対する署名として、ｍ１，…，ｍｉと共に次の署名者装置に送信する手段とを具備するランダムオラクルモデルの仮定のもと安全性証明が可能な可変文書可変順序電子多重署名の各署名者装置Ｐｉｊ。
【請求項５】
請求項４記載の多重署名者装置では、落とし戸付一方向性置換ｆを用いたが、具体的な関数としてＲＳＡ関数を用いることで、各署名者装置が予め決められた署名順序に従うことなく、各署名者装置により任意の署名者順序を決定する事が可能なランダムオラクルモデルの仮定のもと安全性証明が可能な可変文書可変順序電子多重署名方法。
【請求項６】
請求項５記載の多重署名者装置としてコンピューターを機能させるための電子多重署名プログラム。
【請求項７】
請求項６記載の電子多重署名プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】本発明は、従来の落とし戸付一方向性置換ｆを用いた多重署名に対し、乱数成分の使用により帰着効率を向上させ鍵長を短縮させ、更に乱数成分を可能な限り短く抑えても安全性証明が与えられるような方式において、複数人による電子化された文書の稟議／決済、電子カルテシステム等で、署名対象に多重な電子的署名／捺印を付与する電子多重署名方法、その装置及びプログラム、その記録媒体に関するものである。
【背景技術】
【０００２】従来技術として多数の多重電子署名方式が知られているが、落とし戸付一方向性置換ｆを用いた多重署名は、落とし戸付一方向置換ｆの逆変換ｆ−１の困難性に基づく電子署名であり、具体的な落とし戸付一方向置換としてはＲＳＡ関数が挙げられ、本方法は複数人によるＲＳＡ関数を用いた電子署名を署名サイズ及び検証の計算量という観点で効率的に装置上に適用可能であり、以下に従来方式の１つとして挙げられるｆ−ＦＤＨ多重署名（Ｓｈａｃｈａｍらの方法）を述べる。（文献１参照）また図１にＳｈａｃｈａｍらの方法を示す。
各署名者装置Ｐ１，…ＰＬ’＝Ｇは、各署名者装置の任意の署名順序に署名を実行する。多重署名に参加する署名者集合をＧ’としＧ’⊆Ｇである。またＰｉがｊ番目に多重署名する際はＰｉｊと表記する。各署名者Ｐｉｊは秘密の署名鍵ｆｉ−１＝ｓｋｉを保持し、それに対応する公開情報ｆｉ＝ｐｋｉを公開し、各署名者が選択したメッセージｍｉｊに対しハッシュ演算Ｈを施してｙｉｊ＝Ｈ（ｍｉｊ，…，ｍｉｊ，ｐｋ１，…，ｐｋｉ）（ｙｉｊ∈Ｄ）を生成する。ここでＤとはハッシュ関数の値域である。以下の演算を行う。ハッシュ値ｙｉｊと前署名者の署名値σｉｊ−１からρｉｊ＝ｙｉｊ◎σｉｊ−１を計算する。ここで◎は群上での演算を意味する。上記ρｉｊと署名鍵ｆｉ−１＝ｓｋｉとを用いた演算によりσｉｊ＝ｆｉ−１（ρｉｊ）を計算し、そのσｉｊをｍｉｊ，…，ｍｉｊに対する署名として、ｍ１，…，ｍｉと共に次の署名者装置に送り、以上の処理をＰＬ’まで実行する。最終的に検証者装置へ送り、検証者装置は受信したσＬ’、ｍ１，…，ｍＬ”中のｍ１，…，ｍｉに対しハッシュ演算Ｈを施してｙｉ＝Ｈ（ｍ１，…，ｍｉ，ｐｋ１，…，ｐｋｉ）を計算し、更に受信したσｉを上記関数の変数に代入して演算ρｉ＝ｆｉ（σｉ）を行い、更に前署名者の署名値をσｉ−１＝ｙｉ◎ρｉから計算し、以上の処理をＰｉ（Ｌ≧ｉ≧１）に対して実行し、最終的にはｙ１＝Ｈ（ｍ１，ｐｋ１）＝ｆｉ（σｉ）とから、そのσＬ’がそのｍ１，…，ｍｉに対する正当な多重署名か否かを検証する安全性証明可能可変文書可変順序電子多重署名をハッシュの入力値に乱数成分を用いることなく行っていた。【０００３】以下に、もう１つの従来方式として挙げられるｆ−ＰＳＳ多重署名（駒野らの方法）を述べる。（文献２参照）また図２に駒野らの方法を示す。
各署名者装置Ｐ１，…ＰＬ’＝Ｇは、各署名者装置の任意の署名順序に署名を実行する。多重署名に参加する署名者集合をＧ’としＧ’⊆Ｇである。またＰｉがｊ番目に多重署名する際はＰｉｊと表記する。各署名者Ｐｉｊは秘密の署名鍵ｆｉ−１＝ｓｋｉを保持し、それに対応する公開情報ｆｉ＝ｐｋｉを公開する。まず前署名者の署名値σｉｊ−１を受け取り前署名者の署名値σｉｊ−１＝σＬｉｊ−１｜｜σＭｉｊ｜｜σＲｉｊ−１と分割する。ここで｜｜はビット値の連結を表す。以下の演算を行う。次に乱数ｒｉｊを選択し全署名者共通のメッセージｍに対しハッシュ演算Ｈ’を施してω＝Ｈ’（ｍ，ｐｋ１，…，ｐｋｉ，σＭｉｊ−１，σＲｉｊ−１，  ｒｉｊ），ω’＝ω◎σＬｉｊ−１，そしてｓ＝（σＲｉｊ−１，ｒｉｊ）◎Ｇ’（ω’）を計算する。さらに署名鍵ｆｉ−１＝ｓｋｉを用いた演算により  ｚ＝ｆｉ−１（Ｓ，ω’）を計算し、そのσｉｊ＝σＭｉｊ｜｜ｚをｍに対する多重署名として、ｍ共に次の署名者装置に送り、以上の処理をＰＬ’まで実行する。最終的に検証者装置へ送り、検証者装置は受信したσｉＬ’、ｍの正当性を検査するために以下を各σｉｊ（Ｌ’≧ｊ≧１）に実行する：σｉｊと文書ｍに対してσｉｊをσｉｊ＝σＭｉｊ−１｜｜ｚと分割し、ｓ｜｜ω’＝ｆｉｊ−１（ｚ）、σＲｉｊ−１｜｜ｒｉｊ＝ｓ◎Ｇ’（ω’）、そしてσＬｉｊ−１＝ω’◎Ｈ’（ｍ，ｐｋ１，…，ｐｋｉ，σＭｉｊ−１，σＲｉｊ−１，ｒｉｊ）を計算し、ｍ、σｉｊ−１＝σＬｉｊ−１｜｜σＭｉｊ−１｜｜σＲｉｊ−１の検査に移る。全てのσｉｊ’（Ｌ’≧ｊ≧１）に実行しσｏを求め、σｏ＝Ｏ２ｋ１＋ｋ２となる場合にσｉＬ’をｍに対する正当な多重署名か否かを検証する安全性証明可能可変順序電子多重署名を、次の各署名者に乱数成分を送ることなく、セキュリティパラメータ内に収まらなかった多重署名成分送ることで行っていた。【０００４】
【文献１】
Ａ．Ｌｙｓｙａｎｓｋａｙａ，Ｓ．Ｍｉｃａｌｉ，Ｌ．Ｒｅｙｚｉｎ，ａｎｄ  Ｈ．Ｓｈａｃｈａｍ：  Ｓｅｑｕｅｎｔｉａｌ  Ａｇｇｒｅｇａｔｅ  Ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  Ｔｒａｐｄｏｏｒ  Ｐｅｒｍｕｔａｔｉｏｎ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｅｕｒｏｃｒｙｐｔ’０４，ＬＮＣＳ  ｖｏｌ．３０２７，ｐｐ．７４−９０，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００４
【文献２】
Ｙ．Ｋｏｍａｎｏ，Ｋ．Ｏｈｔａ，Ｓ．Ｋａｗａｍｕｒａ  ａｎｄ  Ａ．Ｓｈｉｍｂｏ：  Ｍｕｌｔｉｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ  ｗｉｔｈ  Ｌｅｓｓ  Ｌｅｎｇｔｈｅｎｉｎｇ  ｔｈｅ  Ｓｉｇｎａｔｕｒｅ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｔｈｅ  ２００４  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｒｙｐｔｏｇｒａｐｈｙａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ，ｐｐ．７５５−７６０，２００４  ｉｎ  Ｊａｐａｎｅｓｅ
【発明の開示】
【発明が解決しようとする課題】
【０００５】  しかしながら、Ｓｈａｃｈａｍらの方法では乱数成分を用いていないため、ハッシュ値が確定的に定まってしまい帰着効率を向上させることが困難である。従って長い鍵長を必要とする。一方、駒野らの方法では乱数成分を用いるため、ハッシュ値が確率的となるため帰着効率を向上させることはできたが、乱数成分の付加により、署名者の増加に従って乱数成分の大きさ分だけ署名サイズが増加するという問題点がある。【０００６】  本発明は、このような従来の問題を解決しようとするもので、従来の落とし戸付一方向性置換ｆを用いた多重署名に対し、乱数成分の使用により帰着効率を向上させ鍵長を短縮させ、更に乱数成分を可能な限り短く抑えても安全性証明が与えられるような簡素な処理構造の方式を提供することを目的とするものである。【０００７】  本発明は、秘密の署名鍵ｆｉ−１＝ｓｋｉを保持し、それに対応する公開情報ｆｉ−１＝ｐｋｉを公開する手段と、署名作成時に乱数ｒｉｊを生成する手段と、メッセージｍｉｊと乱数ｒｉｊに対しハッシュ演算Ｈを施してｙｉｊ＝Ｈ（ｍｉｊ，…，ｍｉｊ，ｒｉｊ，…，ｒｉｊ，ｐｋ１，…，ｐｋｉ）（ｙｉｊ∈Ｄ）を計算する手段と、ハッシュ値ｙｉｊと前署名者の署名値σｉｊ−１からρｉｊ＝ｙｉｊ◎σｉｊ−１を計算する手段と、上記ρｉｊと署名鍵ｆｉ−１＝ｓｋｉとを用いた演算によりσｉｊ＝ｆｉ（ρｉｊ）を計算する手段と、そのσｉｊと乱数ｒｉ１，…，ｒｉｊをｍｉｊ，…，ｍｉｊに対する署名として、ｍ１，…，ｍｉと共に次の署名者装置に送信する手段とを具備する安全性証明可能可変文書可変順序電子多重署名の各署名者装置Ｐｉｊ提供することにより上記課題を解決したものである。【０００８】  本発明によれば、Ｓｈａｃｈａｍらの方法と比較し、同等の安全性を、帰着効率の向上からより短い鍵長にて保証できるととともに、署名サイズ及び署名生成時・署名検証時の計算量の軽減へとつながる。表１に推奨鍵長を示す。
【表１】
2005333600.tif 000002
また、駒野らの方法と比較しても、同等の帰着効率をより簡易な構造によって実現でき、更に駒野らの方法に用いる乱数１５１よりもより短い乱数３０を用いたとしても安全性証明を与えることが可能となる。従って本発明は、よりＳｈａｃｈａｍらの方法及び駒野らの方法と同等の安全性をより効率的に実現することが出来る。
以上述べたようにこの発明は、高速で安全性を保証した電子多重署名方法を構成する。安全性の保証については既に述べた通りである。この発明の電子署名方法の高速性を既存方式と比較する。表２に署名サイズの比較を示す。
【表２】
2005333600.tif 000003
その結果，本方法はＳｈａｃｈａｍらの方法らの方法と比較しても署名者数が４１人未満ならば署名サイズを小さく保つ事ができる．また本発明は，階層化されたＣＡによる公開鍵への承認などに実用化されると予想されており、階層化されたＣＡが３０階層以上になることは考えにくいので，本発明は非常に実用的である。
【実施例】
【０００９】  本発明の安全性証明が可能な可変文書可変順序電子多重署名の各署名者装置Ｐｉｊの実施形態を、以下、この発明図を参照して説明する。図３にこの発明方法が適用されるシステムの構成例を示す。Ｌ’組の多重署名者装置１００と検証者装置２００は安全でない通信路３００を介して結合することができる。多重署名者装置１００は登録センタ装置４００に署名者装置の公開鍵を登録することができ、検証者装置２００は登録センタ装置４００から多重署名者装置１００の公開鍵を取得することができる。
（１）鍵の登録図４にこの発明による署名者装置１００の機能構成例を示す。多重署名者装置１００がシステムに加入するとき、鍵生成部１０１の秘密鍵
生成部１０１ａで秘密鍵ｆｉ−１＝ｓｋｉを生成し、それを秘密鍵記憶部１０２に秘密に保持し、また公開鍵生成部１０１ｂで公開鍵ｆｉ−１＝ｐｋｉを生成し、これを記憶部１０３に格納すると共に登録センタ装置４００の公開鍵簿４００ａに登録する。【００１０】（２）多重署名の作成以降では、各多重署名者装置１００がメッセージｍｉｊに多重署名する場合について説明する。多重署名者装置１００は、まず、乱数生成部１０４を用いて、３０ビットの乱数ｒｉｊを生成し、乱数ｒｉｊ，…，ｒｉｊとメッセージｍｉ１，…，ｍｉｊをハッシュ関数演算部１０５に入力してｙｉｊ＝Ｈ（ｍｉ１，…，ｍｉｊ，ｒｉ１，…，ｒｉｊ，ｐｋ１，…，ｐｋｉ）（ｙｉｊ∈Ｄ）を演算する。【００１０】ここで演算部１０６を用いてハッシュ値ｙｉｊと前署名者の署名値σｉｊ−１からρｉｊ＝ｙｉｊ◎σｉｊ−１を計算する。ここで演算部１０７を用いて上記ρｉｊと署名鍵ｆｉ−１＝ｓｋｉとを用いた演算によりσｉｊ＝ｆｉ（ρｉｊ）を計算する。【００１１】以上の処理を繰り返しＰｉ（１＜ｉ≦Ｌ’）まで実行し、最終的に検証者装置へと送信する。【００１２】ｍ１，…，ｍＬ”と（σＬ’，ｒ１，…，ｒＬ’）を検証者装置２００へ通信部１０８より送信する。なお多重署名者装置１００はメッセージｍ１，…，ｍＬ”を入力する入力部１０９を備え、入力されたメッセージｍ１，…，ｍＬ”は必要に応じて一旦、記憶部１０３に格納されるようにすることもできる。【００１３】（３）多重署名の検査検証者装置２００は図５に示すように通信部２０１にｍ１，…，ｍＬ”と（σＬ’，ｒ１，…，ｒＬ’）を受信すると、これを必要に応じて記憶部２０２に一度記憶し、ｍ１，…，ｍＬ”，  ｒ１，…，ｒＬ’をハッシュ関数演算部２０３に入力して、ｙｉＬ’＝Ｈ（ｍ１，…，ｍＬ”，  ｒ１，…，ｒＬ’，ｐｋ１，…，ｐｋＬ’）を演算する。【００１４】更に受信したσＬ’を上記関数の変数に代入して演算部２０４に入力してρＬ’＝ｆ（σＬ’）を行い、更に前署名者の署名値を演算部２０５に入力してσｉ−１＝ｙｉ◎ρｉから計算し、以上の処理を繰返部２０６に入力してＰｉ（Ｌ＞ｉ≧１）に対して実行する。公開鍵は記憶部２０２に格納してあればそれを用い、なければ登録センタ装置４００から取得する。比較部２０７で演算部２０３，２０４，２０５、２０６の各演算結果が次式の関係を満すかを比較検証する。
ｙ１＝Ｈ（ｍ１，ｒ１，ｐｋ１）＝ｆｉ（σｉ）。【００１５】上記検査に合格すれば、この受信した署名（σＬ’，ｒ１，…，ｒＬ’）がメッセージｍ１，…，ｍＬ”に対する正しい多重署名としてＯＫを示す信号を、さもなければ不正なものとしてＮＧを示す信号を比較部２０７は出力する。多重署名者装置１００はコンピュータにより機能させることもできる。その場合は図２に示した多重署名者装置としてコンピュータに機能させるためのプログラムをコンピュータに、ＣＤ−ＲＯＭや可撓性磁気ディスクなどの記録媒体からコンピュータにインストールし、又は通信回線を介してダウンロードして、そのプログラムをコンピュータに実行させればよい。
【産業上の利用可能性】
【００１６】上述の発明は、階層化されたＣＡによる公開鍵への承認などに利用可能である。その他にも複数人による電子化された文書の稟議／決済、電子カルテシステム等で多重署名対象に電子的署名／捺印を付与する電子多重署名方法、その装置及びプログラム、その記憶媒体に利用可能である。
【図面の簡単な説明】
【図１】この発明方法が適用されるシステムの構成例を示す図。
【図２】多重署名者装置の機能構成例を示すブロック図。
【図３】認証者装置の機能構成例を示すブロック図。
【図１】
2005333600.tif 000004
【図２】
2005333600.tif 000005
【図３】
2005333600.tif 000006
【図４】
2005333600.tif 000007
【図５】
2005333600.tif 000008
【手続補正書】
【提出日】平成16年7月27日(2004.7.27)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、従来の落とし戸付一方向性置換ｆを用いた多重署名に対し、乱数成分の使用により帰着効率を向上させ鍵長を短縮させ、更に乱数成分を可能な限り短く抑えても安全性証明が与えられるような方式において、複数人による電子化された文書の稟議／決済、電子カルテシステム等で、署名対象に多重な電子的署名 ／捺印を付与する電子多重署名方法、その装置及びプログラム、その記録媒体に関するものである。
【背景技術】
【０００２】
従来技術として多数の多重電子署名方式が知られているが、落とし戸付一方向性置換ｆを用いた多重署名は、落とし戸付一方向置換ｆの逆変換ｆ-1の困難性に基づく電子署名であり、具体的な落とし戸付一方向置換としてはＲＳＡ関数が挙げられ、本方法は複数人によるＲＳＡ関数を用いた電子署名を署名サイズ及び検証の計算量という観点で効率的に装置上に適用可能であり、以下に従来方式の１つとして挙げられるｆ−ＦＤＨ多重署名（Shachamらの方法）を述べる。（下記非特許文献１参照）また図１にShachamらの方法を示す。
各署名者装置Ｐ１,…ＰＬ’＝Ｇは、各署名者装置の任意の署名順序に署名を実行する。多重署名に参加する署名者集合をＧ’としＧ’⊆Ｇである。またＰｉがｊ番目に多重署名する際はＰｉｊと表記する。各署名者Ｐｉｊは秘密の署名鍵ｆi-1＝ski を保持し、それに対応する公開情報ｆi＝pki を公開し、各署名者が選択したメッセージｍｉｊに対しハッシュ演算Ｈを施してｙiｊ＝Ｈ（ｍｉ１,…,ｍiｊ，ｐｋ1,…,ｐｋi）（ｙiｊ∈Ｄ ）を生成する。ここでＤとはハッシュ関数の値域である。以下の演算を行う。ハッシュ値ｙiｊと前署名者の署名値σiｊ―１からρiｊ＝ｙiｊ◎σiｊ―１を計算する。ここで◎は群上での演算を意味する。上記ρiｊと署名鍵ｆi-1＝ski とを用いた演算によりσiｊ＝ｆi-1(ρiｊ)を計算し、そのσiｊをｍｉ１,…,ｍiｊに対する署名 として、ｍ1,…,ｍiと共に次の署名者装置に送り、以上の処理をＰＬ’まで実行する。最終的に検証者装置へ送り、検証者装置は受信したσＬ’、ｍ1,…,ｍL’’中のｍ1,…,ｍiに対しハッシュ演算Ｈを施してｙi＝Ｈ（ｍ1,…,ｍi，ｐｋ1,…,ｐｋi）を計算し、更に受信したσiを上記関数の変数に代入して演算ρi＝fi (σi) を行い、更に前署名者の署名値をσi―１＝ｙi◎ρiから計算し、以上の処理をＰi(L≧i≧1)に対して実行し、最終的にはｙ１＝Ｈ（ｍ1，ｐｋ1）＝fi (σi)とから、そのσＬ’がそのｍ1,…,ｍiに対する正当な多重署名か否かを検証する安全性証明可能可変文書可変順序電子多重署名をハッシュの入力値に乱数成分を用いることなく行っていた。
【０００３】
以下に、もう1つの従来方式として挙げられるｆ−ＰＳＳ多重署名（駒野らの方法）を述べる。（下記非特許文献２参照）また図２に駒野らの方法を示す。
各署名者装置Ｐ１,…ＰＬ’＝Ｇは、各署名者装置の任意の署名順序に署名を実行する。多重署名に参加する署名者集合をＧ’としＧ’⊆Ｇである。またＰｉがｊ番目に多重署名する際はＰｉｊと表記する。各署名者Ｐｉｊは秘密の署名鍵ｆi-1＝ski を保持し、それに対応する公開情報ｆi＝pki を公開する。まず前署名者の署名値σiｊ―１を受け取り前署名者の署名値σiｊ―１＝σＬｉｊ―１||σＭｉｊ―１||σＲｉｊ―１と分割する。ここで || はビット値の連結を表す。以下の演算を行う。次に乱数ｒiｊを選択し全署名者共通のメッセージｍに対しハッシュ演算Ｈ’を施してω＝Ｈ’（ｍ，ｐｋ1,…,ｐｋi，σＭｉｊ―１，σＲｉｊ―１，ｒiｊ），ω’＝ω◎σＬｉｊ―１，そしてｓ＝（σＲｉｊ―１，ｒiｊ）◎Ｇ’（ω’）を計算する。さらに署名鍵ｆi-1＝ski を用いた演算により  ｚ＝ｆi-1 (Ｓ，ω’)を計算し、そのσiｊ＝σＭｉｊ―１||ｚをｍに対する多重署名
として、ｍ共に次の署名者装置に送り、以上の処理をＰＬ’まで実行する。最終的に検証者装置へ送り、検証者装置は受信したσｉＬ’、ｍの正当性を検査するために以下を各σｉｊ’(Ｌ’≧ｊ≧１)に実行する：σｉｊ’と文書ｍに対してσｉｊ’をσiｊ＝σＭｉｊ―１||ｚと分割し、ｓ||ω’＝ｆiｊ-1 (ｚ)、σＲｉｊ―１||ｒiｊ＝ｓ◎Ｇ’（ω’）、そしてσＬｉｊ―１＝ω’◎Ｈ’（ｍ，ｐｋ1,…,ｐｋi，σＭｉｊ―１，σＲｉｊ―１，ｒiｊ）を計算し、ｍ、σiｊ―１＝σＬｉｊ―１||σＭｉｊ―１||σＲｉｊ―１の検査に移る。全てのσｉｊ’(Ｌ’≧ｊ≧１)に実行しσ０を求め、σ０＝０２ｋ１＋ｋ２となる場合にσｉＬ’をｍに対する正当な多重署名か否かを検証する安全性証明可能可変順序電子多重署名を、次の各署名者に乱数成分を送ることなく、セキュリティパラメータ内に収まらなかった多重署名成分送ることで行っていた。
【０００４】
【非特許文献１】A. Lysyanskaya, S. Micali, L. Reyzin,and H. Shacham：Sequential Aggregate Signatures from Trapdoor Permutation，Proceedings of Eurocrypt'04, LNCS vol.3027, pp.74-90, Springer-Verlag,2004
【非特許文献２】Y. Komano, K. Ohta,S. Kawamura and A. Shimbo:  Multisignature Scheme withLess Lengthening the Signature，Proceedings of The 2004Symposium on Cryptographyand Information Security, pp.755-760, 2004 in Japanese
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、Shachamらの方法では乱数成分を用いていないため、ハッシュ値が確定的に定まってしまい帰着効率を向上させることが困難である。従って長い鍵長を必要とする。一方、駒野らの方法では乱数成分を用いるため、ハッシュ値が確率的となるため帰着効率を向上させることはできたが、乱数成分の付加により、署名者の増加に従って乱数成分の大きさ分だけ署名サイズが増加するという問題点がある。
【０００６】
本発明は、このような従来の問題を解決しようとするもので、従来の落とし戸付一方向性置換ｆを用いた多重署名に対し、乱数成分の使用により帰着効率を向上させ鍵長を短縮させ、更に乱数成分を可能な限り短く抑えても安全性証明が与えられるような簡素な処理構造の方式を提供することを目的とするものである。
【０００７】
本発明は、秘密の署名鍵ｆi-1＝ski を保持し、それに対応する公開情報ｆi-1＝pki を公開する手段と、署名作成時に乱数ｒiｊを生成する手段と、メッセージｍｉｊと乱数ｒiｊに対しハッシュ演算Ｈを施してｙiｊ＝Ｈ（ｍｉ１,…,ｍiｊ，ｒｉ１,…,ｒiｊ，ｐｋ1,…,ｐｋi）（ｙiｊ∈Ｄ ）を計算する手段と、ハッシュ値ｙiｊと前署名者の署名値σiｊ―１からρiｊ＝ｙiｊ◎σiｊ―１を計算する手段と、上記ρiｊと署名鍵ｆi-1＝ski とを用いた演算によりσiｊ＝ｆi (ρiｊ)を計算する手段と、そのσiｊと乱数ｒｉ１,…,ｒiｊをｍｉ１,…,ｍiｊに対する署名として、ｍ1,…,ｍiと共に次の署名者装置に送信する手段とを具備する安全性証明可能可変文書可変順序電子多重署名の各署名者装置Ｐｉｊ提供することにより上記課題を解決したものである。
【０００８】
本発明によれば、Shachamらの方法と比較し、同等の安全性を、帰着効率の向上からより短い鍵長にて保証できるととともに、署名サイズ及び署名生成時・署名検証時の計算量の軽減へとつながる。表１に推奨鍵長を示す。
【表１】
2005333600.tif 000009
また、駒野らの方法と比較しても、同等の帰着効率をより簡易な構造によって実現でき、更に駒野らの方法に用いる乱数１５１よりもより短い乱数３０を用いたとしても安全性証明を与えることが可能となる。従って本発明は、よりShachamらの方法及び駒野らの方法と同等の安全性をより効率的に実現することが出来る。
以上述べたようにこの発明は、高速で安全性を保証した電子多重署名方法を構成する。安全性の保証については既に述べた通りである。この発明の電子署名方法の高速性を既存方式と比較する。表２に署名サイズの比較を示す。
【表２】
2005333600.tif 000010
その結果，本方法はShachamらの方法らの方法と比較しても署名者数が４１人未満ならば署名サイズを小さく保つ事ができる．また本発明は，階層化されたＣＡによる公開鍵への承認などに実用化されると予想されており、階層化されたＣＡが３０階層以上になることは考えにくいので，本発明は非常に実用的である。
【実施例】
【０００９】
本発明の安全性証明が可能な可変文書可変順序電子多重署名の各署名者装置Ｐｉｊの実施形態を、以下、この発明図を参照して説明する。図３にこの発明方法が適用されるシステムの構成例を示す。Ｌ’組の多重署名者装置１００と検証者装置２００は安全でない通信路３００を介して結合することができる。多重署名者装置１００は登録センタ装置４００に署名者装置の公開鍵を登録することができ、検証者装置２００は登録センタ装置４００から多重署名者装置１００の公開鍵を取得することができる。
（１）鍵の登録図４にこの発明による署名者装置１００の機能構成例を示す。多重署名者装置１００がシステムに加入するとき、鍵生成部１０１の秘密鍵生成部１０１ａで秘密鍵ｆi-1＝ｓｋiを生成し、それを秘密鍵記憶部１０２に秘密に保持し、また公開鍵生成部１０１ｂで公開鍵ｆi-1＝ｐｋiを生成し、これを記憶部１０３に格納すると共に登録センタ装置４００の公開鍵簿４００ａに登録する。
【００１０】
（２）多重署名の作成以降では、各多重署名者装置１００がメッセージｍｉｊに多重署名する場合について説明する。多重署名者装置１００は、まず、乱数生成部１０４を用いて、３０ビットの乱数ｒiｊを生成し、乱数ｒｉ１,…,ｒiｊとメッセージｍｉ１,…,ｍiｊをハッシュ関数演算部１０５に入力してｙiｊ＝Ｈ（ｍｉ１,…,ｍiｊ，ｒｉ１,…,ｒiｊ，ｐｋ1,…,ｐｋi）（ｙiｊ∈Ｄ ）を演算する。
【００１１】
ここで演算部１０６を用いてハッシュ値ｙiｊと前署名者の署名値σiｊ―１からρiｊ＝ｙiｊ◎σiｊ―１を計算する。ここで演算部１０７を用いて上記ρiｊと署名鍵ｆi-1＝ｓｋi とを用いた演算によりσiｊ＝ｆi (ρiｊ)を計算する。
【００１２】
以上の処理を繰り返しＰi(１＜ｉ≦Ｌ’)’まで実行し、最終的に検証者装置へと送信する。
【００１３】
ｍ1,…,ｍL’’と（σＬ’，ｒ1,…,ｒＬ’）を検証者装置２００へ通信部１０８より送信する。なお多重署名者装置１００はメッセージｍ1,…,ｍL’’を入力する入力部１０９を備え、入力されたメッセージｍ1,…,ｍL’’は必要に応じて一旦、記憶部１０３に格納されるようにすることもできる。
【００１４】
（３）多重署名の検査検証者装置２００は図５に示すように通信部２０１にｍ1,…,ｍL’’と（σＬ’，ｒ1,…,ｒＬ’）を受信すると、これを必要に応じて記憶部２０２に一度記憶し、ｍ1,…,ｍL’’， ｒ1,…,ｒＬ’をハッシュ関数演算部２０３に入力して、ｙiL’＝Ｈ（ｍ1,…,ｍL’’，
ｒ1,…,ｒＬ’，ｐｋ1,…,ｐｋＬ’）を演算する。
【００１５】
更に受信したσＬ’を上記関数の変数に代入して演算部２０４に入力してρＬ’＝f (σＬ’) を行い、更に前署名者の署名値を演算部２０５に入力してσi―１＝ｙi◎ρiから計算し、以上の処理を繰返部２０６に入力してＰi(Ｌ＞ｉ≧１)に対して実行する。公開鍵は記憶部２０２に格納してあればそれを用い、なければ登録センタ装置４００から取得する。比較部２０７で演算部２０３，２０４，２０５、２０６の各演算結果が次式の関係を満すかを比較検証する。
ｙ１＝Ｈ（ｍ1，ｒ1，ｐｋ1）＝fi (σi)。
【００１６】
上記検査に合格すれば、この受信した署名（σＬ’，ｒ1,…,ｒＬ’）がメッセージｍ1,…,ｍL’’に対する正しい多重署名としてＯＫを示す信号を、さもなければ不正なものとしてＮＧを示す信号を比較部２０７は出力する。多重署名者装置１００はコンピュータにより機能させることもできる。その場合は図２に示した多重署名者装置としてコンピュータに機能させるためのプログラムをコンピュータに、ＣＤ−ＲＯＭや可撓性磁気ディスクなどの記録媒体からコンピュータにインストールし、又は通信回線を介してダウンロードして、そのプログラムをコンピュータに実行させればよい。
【産業上の利用可能性】
【００１７】
上述の発明は、階層化された ＣＡによる公開鍵への承認などに利用可能である。その他にも複数人による電子化された文書の稟議／決済、電子カルテシステム等で多重署名対象に電子的署名／捺印を付与する電子多重署名方法、その装置及びプログラム、その記憶媒体に利用可能である。
【図面の簡単な説明】
【００１８】
【図１】従来方式として挙げられるｆ−ＦＤＨ多重署名を示す図。
【図２】従来方式として挙げられるｆ−ＰＳＳ多重署名を示す図。
【図３】この発明方法が適用されるシステムの構成例を示す図。
【図４】多重署名者装置の機能構成例を示すブロック図。
【図５】認証者装置の機能構成例を示すブロック図。
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2005333600.tif 000011
【図２】
2005333600.tif 000012
【図３】
2005333600.tif 000013
【図４】
2005333600.tif 000014
【図５】
2005333600.tif 000015