(57)【要約】【課題】  電子署名を分散して計算を行う装置全てと通信しなくとも，電子署名を求めることが可能な分散電子署名システムを提供する。【解決手段】  上記システムで分散電子署名計算装置（１０）は，分散電子署名鍵保持部と；分散電子署名を算出するべき乗剰余計算部と；上記分散電子署名を上記代表分散電子署名計算装置に送信する送信部とを備えており，代表分散電子署名計算装置（１３）は，分散電子署名鍵保持部と；分散電子署名を算出するべき乗剰余計算部と；分散電子署名計算装置各々で計算された分散電子署名を受信する受信部と；代表分散電子署名計算装置により算出された分散電子署名と上記１又は２以上の分散電子署名計算装置により算出された分散電子署名とを掛け合わせることで上記メッセージに対する電子署名を算出する乗算部とを備えることを特徴としている。【選択図】    図１
2006352254.tif 000002
【特許請求の範囲】
【請求項１】
１又は２以上の分散電子署名計算装置と，該分散電子署名計算装置各々で分散処理した結果を基にして電子署名を算出する代表分散電子署名計算装置とを備えた分散電子署名システムにおいて：
前記分散電子署名計算装置は，前記電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名の全部又は一部として用いられる分散電子署名を算出するべき乗剰余計算部と；
前記分散電子署名を前記代表分散電子署名計算装置に送信する送信部とを備えており，
前記代表分散電子署名計算装置は，前記電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名の一部として用いられる分散電子署名を算出するべき乗剰余計算部と；
前記１又は２以上の分散電子署名計算装置各々で計算された分散電子署名を受信する受信部と；
前記代表分散電子署名計算装置により算出された分散電子署名と前記１又は２以上の分散電子署名計算装置により算出された分散電子署名とを掛け合わせることで前記メッセージに対する電子署名を算出する乗算部とを備えることを特徴とする，分散電子署名計算装置。
【請求項２】
電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる分散電子署名を算出するべき乗剰余計算部と；
前記分散電子署名を外部の装置に送信する送信部と；
を備えることを特徴とする，分散電子署名計算装置。
【請求項３】
電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名の一部として用いられる第１の分散電子署名を算出するべき乗剰余計算部と；
１又は２以上の外部の装置各々で計算された第２の分散電子署名を受信する受信部と；
前記第１の分散電子署名と前記１又は２以上の第２の分散電子署名とを掛け合わせることで前記メッセージに対する電子署名を算出する乗算部と；
を備えることを特徴とする，分散電子署名計算装置。
【請求項４】
前記分散署名計算装置は，前記乗算部で算出された電子署名を検算する署名検算部を，さらに備えることを特徴とする，請求項３に記載の分散電子署名計算装置。
【請求項５】
１又は２以上の分散電子署名計算装置と，該分散電子署名計算装置各々で分散処理した結果を基にして電子署名を算出する代表分散電子署名計算装置とを備えた分散電子署名システムにおいて：
前記分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；
１又は２以上の外部の装置で計算された第２の分散電子署名を受信する受信部と；
前記べき乗剰余計算部により算出された前記第１の分散電子署名と前記受信部により受信された前記第２の分散電子署名とを掛け合わせることで第３の分散電子署名を算出する乗算部と；
前記第３の分散電子署名を送信する送信部とを備えており，
前記代表分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名の一部として用いられる第１の分散電子署名を算出するべき乗剰余計算部と；
１又は２以上の外部の装置各々で計算された第２の分散電子署名を受信する受信部と；
前記第１の分散電子署名と前記１又は２以上の第２の分散電子署名とを掛け合わせることで前記メッセージに対する電子署名を算出する乗算部とを備え，
前記分散電子署名計算装置と前記代表分散電子署名計算装置とはツリー型マルチホップネットワークを構成することを特徴とする，分散電子署名計算システム。
【請求項６】
電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；
１又は２以上の外部の装置で計算された第２の分散電子署名を受信する受信部と；
前記べき乗剰余計算部により算出された前記第１の分散電子署名と前記受信部により受信された前記第２の分散電子署名とを掛け合わせることで第３の分散電子署名を算出する乗算部と；
前記第３の分散電子署名を送信する送信部とを備えることを特徴とする，分散電子署名計算装置。
【請求項７】
電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる分散電子署名を算出するべき乗剰余計算部と；
乱数を生成する乱数生成部と；
前記乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部と；
前記分散電子署名及び／又は前記乱数を送信する送信部とを備えることを特徴とする，分散電子署名計算装置。
【請求項８】
電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；
１又は２以上の外部の装置で計算された第２の分散電子署名及び／又は１又は２以上の外部の装置で生成された乱数を受信する受信部と；
前記べき乗剰余計算部で算出された第１の分散電子署名と上記受信部から得られた第２の分散電子署名とを掛け合わせることで電子署名を算出する乗算部と；
前記受信部から得られた乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部とを備えることを特徴とする，分散電子署名計算装置。
【請求項９】
前記分散署名計算装置は，前記乗算部で算出された電子署名を検算する署名検算部を，さらに備えることを特徴とする，請求項８に記載の分散電子署名計算装置。
【請求項１０】
１又は２以上の分散電子署名計算装置と，該分散電子署名計算装置各々で分散処理した結果を基にして電子署名を算出する代表分散電子署名計算装置とを備えた分散電子署名システムにおいて：
前記分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる分散電子署名を算出するべき乗剰余計算部と；
乱数を生成する乱数生成部と；
前記乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部と；
前記分散電子署名及び／又は前記乱数を送信する送信部とを備えており，
前記代表分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；
１又は２以上の前記分散電子署名計算装置で計算された第２の分散電子署名及び／又は該分散電子署名計算装置で生成された乱数を受信する受信部と；
前記べき乗剰余計算部で算出された第１の分散電子署名と，前記受信部から得られた第２の分散電子署名とを掛け合わせることで電子署名を算出する乗算部と；
前記受信部から得られた乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部とを備えることを特徴とする，分散電子署名システム。
【請求項１１】
電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；
第１の乱数を生成する乱数生成部と；
前記第１の乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部と；
１又は２以上の外部の装置で計算された第２の分散電子署名及び／又は該外部の装置で生成された第２の乱数を受信する受信部と；
前記べき乗剰余計算部で算出された前記第１の分散電子署名と，前記受信部から得られた前記第２の分散電子署名とを掛け合わせることで第３の分散電子署名を算出する乗算部と；
前記第１の乱数と前記受信部から得られた前記第２の乱数とを足し合わせることで第３の乱数を生成する加算部と；
前記第３の分散電子署名及び／又は前記第３の乱数を送信する送信部と；
を備えることを特徴とする，分散電子署名計算装置。
【請求項１２】
１又は２以上の分散電子署名計算装置と，該分散電子署名計算装置各々で分散処理した結果を基にして電子署名を算出する代表分散電子署名計算装置とを備えた分散電子署名システムにおいて：
前記分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；
第１の乱数を生成する乱数生成部と；
前記第１の乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部と；
１又は２以上の外部の装置で計算された第２の分散電子署名及び／又は該外部の装置で生成された第２の乱数を受信する受信部と；
前記べき乗剰余計算部で算出された前記第１の分散電子署名と，前記受信部から得られた前記第２の分散電子署名とを掛け合わせることで第３の分散電子署名を算出する乗算部と；
前記第１の乱数と前記受信部から得られた前記第２の乱数とを足し合わせることで第３の乱数を生成する加算部と；
前記第３の分散電子署名及び／又は前記第３の乱数を送信する送信部とを備えており，
前記代表分散電子署名計算装置は，前記電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；
前記電子署名の対象とするメッセージと，前記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；
１又は２以上の外部の装置で計算された第２の分散電子署名及び／又は１又は２以上の外部の装置で生成された乱数を受信する受信部と；
前記べき乗剰余計算部で算出された第１の分散電子署名と上記受信部から得られた第２の分散電子署名とを掛け合わせることで電子署名を算出する乗算部と；
前記受信部から得られた乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部とを備えており，
前記分散電子署名システムは，ツリー型マルチホップネットワークで構成されることを特徴とする，分散電子署名計算システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，通信路を介して接続された複数の装置で電子署名を分散して処理する分散電子署名装置および分散電子署名システムに関する。
【背景技術】
【０００２】
現在，公開鍵暗号を用いて電子署名を，お互いを通信路で接続した複数の装置により分散し算出する分散電子署名システムが知られている（例えば，特許文献１，参照）。
【０００３】
上記分散電子署名システムには，複数の装置が備わり，当該複数の装置各々は，元の署名鍵を秘密裏に分散した分散電子署名鍵を各々所持し，他の全部の装置と交信しながら自身の持つ分散電子署名鍵を用いて分散電子署名を計算する。
【０００４】
電子署名を求める際には，しきい値秘密分散法，放送型の通信路，システム内に備わる各装置と交信可能な秘密通信路等を用いることにより，所定のしきい値以下の不正を行う装置が存在する場合でも，電子署名を生成可能であるか，もしくは，電子署名を生成できなくても不正を行った装置を特定することできる方式である。
【０００５】
【特許文献１】特開平８−２０４６９７号公報
【非特許文献１】岡本龍明，山本博資  著，「現代暗号」，産業図書，ｐ．１７５−１７６
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら，電子署名を求めるためには，分散して計算を行う装置全てと秘密通信を行う必要があるため，通信が煩雑になり，通信コストが膨大になるという問題があった。特に，通信路が無線通信路で，分散して計算する装置が電池駆動の場合には，無線通信の送受信に多くの電力がとられるため，電池の寿命が短くしてしまうといった問題があった。
【０００７】
本発明は，上記問題点に鑑みてなされたものであり，本発明の目的は，電子署名を分散して計算を行う装置全てと通信しなくとも，電子署名を求めることが可能な，新規かつ改良された分散電子署名システムを提供することである。
【課題を解決するための手段】
【０００８】
上記課題を解決するため，本発明の第１の観点によれば，１又は２以上の分散電子署名計算装置と，該分散電子署名計算装置各々で分散処理した結果を基にして電子署名を算出する代表分散電子署名計算装置とを備えた分散電子署名システムが提供される。上記分散電子署名システムにおける分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名の全部又は一部として用いられる分散電子署名を算出するべき乗剰余計算部と；上記分散電子署名を上記代表分散電子署名計算装置に送信する送信部とを備えており，上記代表分散電子署名計算装置は，上記電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名の一部として用いられる分散電子署名を算出するべき乗剰余計算部と；１又は２以上の分散電子署名計算装置各々で計算された分散電子署名を受信する受信部と；代表分散電子署名計算装置により算出された分散電子署名と上記１又は２以上の分散電子署名計算装置により算出された分散電子署名とを掛け合わせることで上記メッセージに対する電子署名を算出する乗算部とを備えることを特徴としている。なお，上記分散電子署名鍵は，例えば，上記電子署名鍵が複数に分割されたものである場合等でもよい。
【０００９】
上記課題を解決するために，本発明の別の観点によれば，分散電子署名計算装置が提供される。上記分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる分散電子署名を算出するべき乗剰余計算部と；上記分散電子署名を外部の装置に送信する送信部とを備えることを特徴としている。なお，上記分散電子署名計算装置は，例えばノード等に該当する。
【００１０】
上記課題を解決するために，本発明の別の観点によれば，分散電子署名計算装置が提供される。上記分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名の一部として用いられる第１の分散電子署名を算出するべき乗剰余計算部と；１又は２以上の外部の装置各々で計算された第２の分散電子署名を受信する受信部と；上記第１の分散電子署名と上記１又は２以上の第２の分散電子署名とを掛け合わせることで上記メッセージに対する電子署名を算出する乗算部とを備えることを特徴としている。なお，上記分散電子署名計算装置は，例えば，代表ノードに該当する。
【００１１】
上記分散署名計算装置は，上記乗算部で算出された電子署名を検算する署名検算部を，さらに備えるように構成しても良い。
【００１２】
上記課題を解決するために，本発明の別の観点によれば，１又は２以上の分散電子署名計算装置と，該分散電子署名計算装置各々で分散処理した結果を基にして電子署名を算出する代表分散電子署名計算装置とを備えた分散電子署名システムが提供される。上記分散電子署名システムにおいて，上記分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；１又は２以上の外部の装置で計算された第２の分散電子署名を受信する受信部と；べき乗剰余計算部により算出された上記第１の分散電子署名と上記受信部により受信された上記第２の分散電子署名とを掛け合わせることで第３の分散電子署名を算出する乗算部と；上記第３の分散電子署名を送信する送信部とを備えており，上記代表分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵のうちいずれか一つを保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名の一部として用いられる第１の分散電子署名を算出するべき乗剰余計算部と；１又は２以上の外部の装置各々で計算された第２の分散電子署名を受信する受信部と；上記第１の分散電子署名と上記１又は２以上の第２の分散電子署名とを掛け合わせることで上記メッセージに対する電子署名を算出する乗算部とを備え，上記分散電子署名計算装置と上記代表分散電子署名計算装置とはツリー型マルチホップネットワークを構成することを特徴としている。
【００１３】
上記分散電子署名システムにおいて，上記代表分散電子署名計算装置は，上記ツリー型マルチホップネットワークにおけるルートに少なくとも存在するように構成されても良い。
【００１４】
上記課題を解決するために，本発明の別の観点によれば，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；１又は２以上の外部の装置で計算された第２の分散電子署名を受信する受信部と；上記べき乗剰余計算部により算出された上記第１の分散電子署名と上記受信部により受信された上記第２の分散電子署名とを掛け合わせることで第３の分散電子署名を算出する乗算部と；上記第３の分散電子署名を送信する送信部とを備えることを特徴とした分散電子署名計算装置が提供される。当該分散電子署名計算装置は，例えば，ノードに該当する。
【００１５】
電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる分散電子署名を算出するべき乗剰余計算部と；乱数を生成する乱数生成部と；上記乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部と；上記分散電子署名及び／又は上記乱数を送信する送信部とを備えることを特徴とした分散電子署名計算装置が提供される。当該分散電子署名計算装置は，例えば，ノードに該当する。
【００１６】
上記課題を解決するために，本発明の別の観点によれば，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；１又は２以上の外部の装置で計算された第２の分散電子署名及び／又は１又は２以上の外部の装置で生成された乱数を受信する受信部と；上記べき乗剰余計算部で算出された第１の分散電子署名と上記受信部から得られた第２の分散電子署名とを掛け合わせることで電子署名を算出する乗算部と；上記受信部から得られた乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部とを備えることを特徴とし分散電子署名計算装置が提供される。なお，当該分散電子署名計算装置は，例えば，代表ノード等に該当する。
【００１７】
上記分散署名計算装置は，上記乗算部で算出された電子署名を検算する署名検算部を，さらに備えるように構成しても良い。
【００１８】
上記課題を解決するために，本発明の別の観点によれば，１又は２以上の分散電子署名計算装置と，該分散電子署名計算装置各々で分散処理した結果を基にして電子署名を算出する代表分散電子署名計算装置とを備えた分散電子署名システムが提供される。上記分散電子署名システムにおいて，上記分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる分散電子署名を算出するべき乗剰余計算部と；乱数を生成する乱数生成部と；上記乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部と；上記分散電子署名及び／又は上記乱数を送信する送信部とを備え，上記代表分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；１又は２以上の上記分散電子署名計算装置で計算された第２の分散電子署名及び／又は該分散電子署名計算装置で生成された乱数を受信する受信部と；べき乗剰余計算部で算出された第１の分散電子署名と，上記受信部から得られた第２の分散電子署名とを掛け合わせることで電子署名を算出する乗算部と；上記受信部から得られた乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部とを備えることを特徴としている。
【００１９】
上記課題を解決するために，本発明の別の観点によれば，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；第１の乱数を生成する乱数生成部と；上記第１の乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部と；１又は２以上の外部の装置で計算された第２の分散電子署名及び／又は該外部の装置で生成された第２の乱数を受信する受信部と；上記べき乗剰余計算部で算出された上記第１の分散電子署名と，上記受信部から得られた上記第２の分散電子署名とを掛け合わせることで第３の分散電子署名を算出する乗算部と；上記第１の乱数と上記受信部から得られた上記第２の乱数とを足し合わせることで第３の乱数を生成する加算部と；上記第３の分散電子署名及び／又は上記第３の乱数を送信する送信部とを備えたことを特徴とした分散電子署名計算装置が提供される。当該分散電子署名計算装置は，例えば，ノード等に相当する。
【００２０】
上記課題を解決するために，本発明の別の観点によれば，１又は２以上の分散電子署名計算装置と，該分散電子署名計算装置各々で分散処理した結果を基にして電子署名を算出する代表分散電子署名計算装置とを備えた分散電子署名システムが提供される。上記分散電子署名システムにおいて，上記分散電子署名計算装置は，電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；第１の乱数を生成する乱数生成部と；上記第１の乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部と；１又は２以上の外部の装置で計算された第２の分散電子署名及び／又は該外部の装置で生成された第２の乱数を受信する受信部と；上記べき乗剰余計算部で算出された上記第１の分散電子署名と，上記受信部から得られた上記第２の分散電子署名とを掛け合わせることで第３の分散電子署名を算出する乗算部と；上記第１の乱数と上記受信部から得られた上記第２の乱数とを足し合わせることで第３の乱数を生成する加算部と；上記第３の分散電子署名及び／又は上記第３の乱数を送信する送信部とを備えており，上記代表分散電子署名計算装置は，上記電子署名を計算するための電子署名鍵が複数に秘密分散された分散電子署名鍵を保持する分散電子署名鍵保持部と；上記電子署名の対象とするメッセージと，上記分散電子署名鍵保持部に記憶された分散電子署名鍵とを基にして，該電子署名を算出するために全部又は一部として用いる第１の分散電子署名を算出するべき乗剰余計算部と；１又は２以上の外部の装置で計算された第２の分散電子署名及び／又は１又は２以上の外部の装置で生成された乱数を受信する受信部と；上記べき乗剰余計算部で算出された第１の分散電子署名と上記受信部から得られた第２の分散電子署名とを掛け合わせることで署名を算出する乗算部と；上記受信部から得られた乱数を用いて分散電子署名鍵を算出し，該算出された分散電子署名鍵に更新する分散電子署名鍵更新部とを備えており，上記分散電子署名システムは，ツリー型マルチホップネットワークで構成されることを特徴としている。
【００２１】
上記分散電子署名システムにおいて，上記代表分散電子署名計算装置は，上記ツリー型マルチホップネットワークにおけるルートに少なくとも存在するように構成されても良い。
【発明の効果】
【００２２】
以上説明したように，本発明によれば，システム内に存在する各装置と通信を行わなくても各装置で計算した分散電子署名を基にして，代表する装置が一括して計算すれば電子署名を求めることができるため，通信トラフィックを大幅に低減し，装置に対する消費電力を抑えることができる。
【発明を実施するための最良の形態】
【００２３】
以下，本発明の好適な実施の形態について，添付図面を参照しながら詳細に説明する。なお，以下の説明及び添付図面において，略同一の機能及び構成を有する構成要素については，同一符号を付することにより，重複説明を省略する。
【００２４】
まず，本実施形態で使用するＲＳＡ署名について説明する。署名鍵（又は，秘密鍵）をｄ，検証鍵（又は，公開鍵）をｅおよびｎ，署名したいメッセージをｍとすると，ＲＳＡ署名ｓ（又は，電子署名ｓ）は，以下，式１に示すような計算を行う。なお，上記ｅとｎとの関係は，ｅｄ＝１（ｍｏｄ  λ（ｎ））となっている。また，以下，説明する実施の形態では，上記署名鍵が秘密鍵，検証鍵が公開鍵である場合を例に挙げて説明するが，かかる例に限定されない。
【００２５】
ｓ＝ｈ（ｍ）ｄ  （ｍｏｄ  ｎ）    …（式１）
【００２６】
ここで，上記ｈ（）は，一方向性ハッシュ関数と呼ばれる関数であり，このハッシュ関数によって計算されたハッシュ値から，元の値を求めることが事実上不可能であって，異なる値からは同じハッシュ値とならない。つまり，ハッシュ関数は，ｈ（ｘ）＝ｈ（ｙ），（ｘ≠ｙ）となるようなｘ，ｙを求めることが困難な関数である。
【００２７】
また，λ（ｎ）は，ｎのＣａｒｍｉｃｈａｅｌ関数（カーマイケル関数）である。当該Ｃａｒｍｉｃｈａｅｌ関数は，以下，式２〜式４に示すように定義される。
【００２８】
上記Ｃａｒｍｉｃｈａｅｌ関数は，ｎ＝２ｅ０ｐ１ｅ１ｐ２ｅ２…ｐｒｅｒ（ｐ１，ｐ２，…，ｐｒは異なる奇素数）のとき，
λ（ｎ）＝ＬＣＭ（λ（２ｅ０），φ（ｐ１ｅ１），…，φ（ｐｒｅｒ））    …（式２）
φ（ｐｉｅｉ）＝ｐｉ（ｅｉ−１）（ｐｉ−１）  （ｉ＝１，…，ｒ）          …（式３）
λ（２ｔ）＝２（ｔ−１）  （ｔ＜３），λ（２ｔ）＝２（ｔ−２）  （ｔ≧３）…（式４）
と定義されている。
【００２９】
なお，ＲＳＡ署名では，ｎが２の素数ｐと２の素数ｑの積である場合を例に挙げて説明するため，以下の式５に示すようになる。
【００３０】
λ（ｎ）＝ＬＣＭ（ｐ−１，ｑ−１）  …（式５）
【００３１】
メッセージｍと電子署名ｓを受け取った場合，当該電子署名ｓとメッセージｍとを基にして，電子署名の検証を行うことができる。以下，当該電子署名を基礎とし，本実施の形態にかかる分散的な電子署名について詳細に説明する。
【００３２】
（第１の実施形態について）
第１の実施形態にかかる分散電子署名システムでは，まず，複数の装置（以下，ノードと呼ぶ）が秘密鍵ｄを分散的に保持し，分散的に電子署名を計算する。ノード自身を除く他のノード全てと通信することなく，各ノードは，まずバラバラに分散する電子署名（又は，分散電子署名）を生成する。
【００３３】
上記各ノードで生成された分散電子署名を基に，最終的な電子署名を算出するノード（以下，代表ノードと呼ぶ）に，それらの分散電子署名を送信することで，電子署名を得ることができる。
【００３４】
ここで，図１を参照しながら，第１の実施の形態にかかる分散電子署名システムについて説明する。図１は，第１の実施形態に係る分散電子署名システムの概略を示す説明図である。
【００３５】
図１に示すように，第１の実施の形態に係る分散電子署名システム８００には，ノードＵ１〜ノードＵ５のように，１又は２台以上のノード１０（１０−１〜１０−５）と，最終的な電子署名を算出する代表装置である代表ノード１３とが備わる。
【００３６】
分散電子署名システム８００には，図１では５台のノード１０−１〜ノード１０−５が備わる場合を示しているが，ノード１０がＮ台（Ｎ≧１）備わる場合でも可能である。なお，ノード１０−１〜ノード１０−５のノードを各々ノートＵ１，ノードＵ２，…，ノードＵＮで表すとする。
【００３７】
また，代表ノード１３をノードＵ０で表すとするが，ノードＵ０は，ノードＵ１，ノードＵ２，…，ノードＵＮよりも代表ノードＵ０のほうが計算資源（計算能力，メモリ量，電源等）が優れている，例えば，サーバ装置等を例示することができるが，かかる例に限定されない。
【００３８】
上記ノード１０は，少なくとも他のノード１０または代表ノード１３とデータを送受信することが可能な通信機能，分散電子署名等を計算する計算機能を備えたデバイスであれば，如何なる装置でも実施可能であるが，ノード１０は，消費電力が低く，装置のサイズを極力小さくすることができる，例えば，電池駆動可能な装置がより好ましい。
【００３９】
また，上記代表ノード１３は，ノード１０と同様に，各ノード１０とデータ通信可能な通信機能を備え，ノード１０からの分散電子署名を基に電子署名を求める計算機能などを備えた，例えば，サーバ装置などを例に挙げることができる。
【００４０】
上記ノード１０又は代表ノード１３を相互にデータ通信するための通信網は，例えば，Ｅｔｈｅｒｎｅｔ（登録商標）による同軸ケーブル又はツイストペアケーブル，もしくはＩＥＥＥ８０２．１１ｂなどによる無線など，有線無線を問わない。
【００４１】
なお，上記説明したように，第１の実施の形態にかかる分散電子署名システムでは，電子署名（又は，ＲＳＡ署名）の秘密鍵をｄ，公開鍵をｅ及びｎ（ｅｄ＝１（ｍｏｄ  λ（ｎ）））と表すことにする。
【００４２】
また，ノードＵ１，ノードＵ２，…，ノードＵＮ，および，代表ノードＵ０は，元の秘密鍵ｄを秘密裏に分散（又は，秘密分散）した分散秘密鍵ｄ１，分散秘密鍵ｄ２，…，分散秘密鍵ｄＮ，および，分散秘密鍵ｄ０を保持している。なお，本実施形態において秘密分散とは，例えば，秘密情報を複数の分散情報に符号化する手法，または，秘密鍵を分散して管理する手法などのことである。また，上記分散秘密鍵ｄｉ（ｉ＝０，１，２，３，…）は，秘密鍵ｄが秘密分散されたものであるが，単に秘密鍵ｄが分割されたものであってもよい。
【００４３】
さらに，上記各分散秘密鍵ｄ１，分散秘密鍵ｄ２，…，分散秘密鍵ｄＮと元の秘密鍵ｄとの関係は，以下，式６に示すようになる。
【００４４】
ｄ＝ｄ０＋ｄ１＋ｄ２＋…＋ｄＮ  （ｍｏｄ  λ（ｎ））  …（式６）
【００４５】
なお，ノードＵ１，ノードＵ２，…，ノードＵＮ，および代表ノードＵ０の性能（計算能力等）に応じて，分散秘密鍵のビット長など，分散秘密鍵の値の大きさを調節することが可能である。
【００４６】
電子署名の対象とするメッセージをｍとすると，ノードＵ１，ノードＵ２，…，ノードＵＮは，以下の式７に示す計算を実行することで求められる分散電子署名ｓｉ（ｉ＝１，…，Ｎ）を代表ノードＵ０に送信する。
【００４７】
ｓｉ＝ｈ（ｍ）ｄｉ  （ｍｏｄ  ｎ）  （ｉ＝１，…，Ｎ）  …（式７）
【００４８】
代表ノードＵ０は，まず，下記式８に示す計算を実行し，自己（代表ノードＵ０）の分散電子署名ｓ０を求める。
【００４９】
ｓ０＝ｈ（ｍ）ｄ０  （ｍｏｄ  ｎ）  …（式８）
【００５０】
分散電子署名ｓ０が求まると，代表ノードＵ０は，さらにノード１０から受信済みの分散電子署名ｓ１，分散電子署名ｓ２，…，分散電子署名ｓＮを掛け合わせ，さらに代表ノードＵ０自身が生成した分散電子署名ｓ０を式９に示すように，掛け合わせることにより，代表ノードＵ０は最終的な電子署名ｓを求めることができる。
【００５１】
ｓ＝ｓ０ｓ１ｓ２…ｓＮ  （ｍｏｄ  ｎ）  …（式９）
【００５２】
（ノード１０について）
次に，図２を参照しながら，第１の実施の形態にかかるノード１０（ノードＵｉ（ｉ＝１，２，…，Ｎ））に備わる分散電子署名に係る計算を実行する分散電子署名計算部１００について説明する。なお，図２は，第１の実施の形態にかかるノード１０に備わる分散電子署名計算部１００の概略的な構成を示すブロック図である。
【００５３】
図２に示すように，ノード１０に設けられた分散電子署名計算部１００には，分散秘密鍵を記憶する分散秘密鍵保持部１０１と，べき乗剰余計算部１０２と，分散電子署名を外部のノード１０又は代表ノード１３に送信する送信部１０３とが備わっている。
【００５４】
上記分散秘密鍵保持部１０１は，ノードＵｉの分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）を記憶する記憶装置である。例えば，ノードＵ１の場合，分散秘密鍵保持部１０１は，分散秘密鍵ｄ１を記憶している。
【００５５】
べき乗剰余計算部１０２は，電子署名したいメッセージｍおよび分散秘密鍵保持部１０１に格納された分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）を入力し，上記式７に示す分散電子署名ｓｉを計算し，送信部１０３に出力する。
【００５６】
なお，本実施形態に係るメッセージｍは，例えば，インターネット等の通信路を介して受信したものであってもよいし，予めノード１０に備わる分散秘密鍵保持部１０１等の記憶デバイスに記憶されたものであってもよい。ただし，メッセージｍは，予め分散電子署名システム８００で合意の取れた方式でメッセージｍを各ノードＵｉ（ｉ＝１，２，…，Ｎ）および代表ノードＵ０が取得できるものとする。
【００５７】
上記送信部１０３は，べき乗剰余計算部１０２から計算結果である分散電子署名ｓｉを受け取り，それを代表ノードＵ０に送信する。このときの通信路は，直接代表ノードへ送信するような形態（図１に示す（１）の矢印）でも可能であり，マルチホップ通信路のように，他のノード１０を経由しデータを送信するような形態の場合でも可能である。
【００５８】
なお，上記マルチホップ通信路とは，例えば，図１の場合，ノードＵ１から代表ノードＵ０に分散電子署名ｓ１を送信するとした場合，まずノードＵ４に送信し，さらにノードＵ４が代表ノードＵ０に転送するような形態である（図１に示す（２）の２つの矢印）。
【００５９】
次に，図３を参照しながら，第１の実施形態にかかる代表ノード１３に備わる分散電子署名に係る計算を実行する分散電子署名計算部２００について説明する。図３は，第１の実施の形態にかかる代表ノード１３に備わる分散電子署名計算部２００の概略的な構成を示すブロック図である。
【００６０】
図２に示すように，代表ノード１３に設けられた分散電子署名計算部２００には，分散秘密鍵保持部２０１と，べき乗剰余計算部２０２と，乗算部２０３と，受信部２０４とが備わっている。
【００６１】
上記分散秘密鍵保持部２０１は，代表ノード１０３（ノードＵ０）の分散秘密鍵ｄ０を記憶する記憶装置である。例えば，分散秘密鍵保持部２０１は，ＥＥＰＲＯＭ，ＲＡＭ等のメモリを例示することができるが，かかる例に限定されない。
【００６２】
上記べき乗剰余計算部２０２は，電子署名したいメッセージｍと分散秘密鍵保持部２０１に格納された分散秘密鍵ｄ０とを入力し，上記式８に示す分散電子署名ｓ０を計算して，乗算部２０３に出力する。
【００６３】
なお，上記記載のように，メッセージｍは，ノードＵ１，ノードＵ２，…，ノードＵＮの場合と同様，通信路を通して受信したものであってもよいし，予め代表ノード１０３に備わる分散秘密鍵保持部２０１などの記憶装置に格納されているもの等の場合でもよいが，予め分散電子署名システム８００で合意の取れた方式でメッセージｍを各ノードＵｉ（ｉ＝１，２，…，Ｎ）および代表ノードＵ０が取得できるものとする。
【００６４】
上記乗算部２０３は，べき乗剰余計算部２０２より計算結果である分散電子署名ｓ０を受け取り，さらに受信部２０４が受信したノード１０からの分散電子署名ｓｉ（ｉ＝１，２，…，Ｎ）を受け取り，上記式９に示す乗算を実行し，その結果である電子署名ｓを出力する。
【００６５】
上記受信部２０４は，各ノードＵｉから分散電子署名ｓｉ（ｉ＝１，２，…，Ｎ）を受信し，その受信した分散電子署名ｓｉ（ｉ＝１，２，…，Ｎ）を乗算部２０３に出力する。なお，乗算部２０３から出力された電子署名ｓは，メッセージを認証する認証部（図示せず。）等に伝送される。
【００６６】
（分散電子署名の動作について）
次に，図４を参照しながら，第１の実施の形態にかかる分散電子署名に関する計算を実行するノード１０の動作について説明する。なお，図４は，第１の実施の形態にかかる分散電子署名に関する計算を実行するノード１０の動作の概略を示すフローチャートである。
【００６７】
図４に示すように，まず，各ノードＵｉ（ｉ＝１，２，…，Ｎ）は，電子署名したいメッセージｍに対し，各ノード１０自身が保持する分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）を用いて分散電子署名ｓｉを，上記式７に示すように生成する（Ｓ３０１）。
【００６８】
なお，図４に示す上記分散電子署名ｓｉを生成する（Ｓ３０１）のは，図２に示すように，べき乗剰余計算部１０２による動作である。
【００６９】
次に，ノード１０に備わる送信部１０３は，上記べき乗剰余計算部１０２により生成された分散電子署名ｓｉを代表ノードＵ０に送信する（Ｓ３０２）。
【００７０】
次に，図５を参照しながら，第１の実施形態の分散電子署名を実行する代表ノードＵ０の動作について説明する。なお，図５は，第１の実施の形態にかかる分散電子署名に関する計算を実行する代表ノード１３の動作の概略を示すフローチャートである。
【００７１】
図５に示すように，まず代表ノードＵ０は，電子署名するメッセージｍに対し，代表ノードＵ０自身が保持している分散秘密鍵ｄ０を用いて分散電子署名ｓ０を上記式８に示すように求める（Ｓ４０１）。
【００７２】
なお，図５に示す分散秘密鍵ｄ０を用いて分散電子署名ｓ０を生成する処理（Ｓ４０１）は，上記説明したように，図３に示す代表ノード１３に備わるべき乗剰余計算部２０２による動作である。
【００７３】
また，図５に示すように，分散電子署名ｓ０を生成する処理（Ｓ４０１）と平行して，各ノードＵｉ（ｉ＝１，２，…，Ｎ）から分散電子署名ｓｉを受信する（Ｓ４０２）。
【００７４】
なお，各ノード１０から分散電子署名ｓｉを受信する処理（Ｓ４０２）は，図３に示す受信部２０４による動作である。
【００７５】
図５に示すように，ステップＳ４０１とステップＳ４０２の処理は，略同時並行して実行されるように図示されているが，必ずしも同時進行の場合に限定されない。例えば，ステップＳ４０１の終了後にステップＳ４０２を実行する，あるいは，ステップＳ４０２の終了後にステップＳ４０１を実行する場合でも実施可能である。
【００７６】
上記ステップＳ４０１とステップＳ４０２とが終了すると，次に，ステップＳ４０１で得られた分散電子署名ｓ０と，上記ステップＳ４０２で受信した分散電子署名ｓｉ（ｉ＝１，２，…，Ｎ）とを掛け合わせ，上記式９に示すように電子署名ｓを生成する（Ｓ４０３）。
【００７７】
なお，上記電子署名ｓを生成する処理（Ｓ４０３）は，図３に示す代表ノード１０３に備わる乗算部２０３による動作である。
【００７８】
以上，第１の実施の形態にかかる分散電子署名システム８００の説明を終了するが，かかる分散電子署名システム８００によって，以下に示すような優れた効果が存在する。
（１）分散電子署名鍵ｄ１〜分散電子署名鍵ｄＮ等のように，秘密鍵を各ノード１０で秘密裏に分散して保持することで，分散計算する各々のノード１０が他のノード１０と互いに通信せずに，分散電子署名を生成し，代表ノード１３にそれらの分散電子署名を送信することにより，悪意のある不正ノードが仮に存在し虚偽の分散電子署名を代表ノード１３に送信したとしても，代表ノード１３は真正なる署名を生成することできず，その結果，不正な電子署名である判断することができる。すなわち，セキュリティ上不可欠な不正者によって虚偽の電子署名が作成されてしまうおそれを防止することができる。
（２）不正ノードがどこに存在するのかを判断することはできないが，最低限のセキュリティを確保した上，さらに全ノード１０相互間で少なくとも通信する必要がないため，ノード１０相互又はノード１０とノード１３との通信量を格段に削減することができる。
（３）また，上記式６のように分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）と元の秘密鍵ｄとの関係を保ちながら，例えば，下記式１０に示すようにノードＵｉ（ｉ＝１，２，…，Ｎ）が保有する分散秘密鍵ｄｉの値（又は，ビット長）をノードＵ０の分散秘密鍵ｄ０よりも小さくすれば，計算能力の低いノード１０でも分散電子署名を迅速かつ的確に生成することが可能となる。したがって，ノード１０の能力に応じた大きさの分散秘密鍵を保有させることにより，処理パフォーマンスが低能力なノード１０でも迅速な分散電子署名生成が可能となる。
（４）また，秘密鍵ｄを各ノードが分散して保持しているため，少数のノードが分解・解析されて保持してある秘密鍵（分散秘密鍵）を盗まれても，盗難者が正しい署名を生成することが不可能である。
【００７９】
ｄ１，ｄ２，…，ｄＮ  ＜＜  ｄ０  …（式１０）
【００８０】
（第２の実施形態について）
第１の実施形態では，分散電子署名する各ノードがそれぞれ代表ノードへ分散電子署名を送信していたが，第２の実施形態では，ネットワークがツリー構造のマルチホップ通信路であると仮定した場合に，ルーティングするノードが分散電子署名の途中処理を受け持つことで，ネットワーク全体の通信量の削減を可能とする。
【００８１】
なお，以下に示す説明では，第１の実施の形態にかかる分散電子署名システム８００と第２の実施の形態にかかる分散電子署名システム８０１とを比較し，特に異なる点について詳細に説明するが，その他の点については，特段の明示がない場合，ほぼ同様な構成であるため詳細な説明は省略する。
【００８２】
まず，図６を参照しながら，第１の実施の形態にかかる分散電子署名システムについて説明する。図６は，第２の実施形態に係る分散電子署名システムの概略を示す説明図である。
【００８３】
第１の実施形態に係る分散電子署名システム８００では，各ノード１１から代表ノード１４への分散電子署名の送信は，どのような経路をたどってもかまわないこととしていたが，第２の実施形態に係る分散電子署名システム８０１では，マルチホップ通信形態の一つであるツリー構造のマルチホップネットワークにおいて分散電子署名の送信が行われる。
【００８４】
図６に示すように，第２の実施の形態にかかる分散電子署名システム８０１は，第１の実施形態と同様に，電子署名（又は，ＲＳＡ署名）を分散計算するシステムであって，１台以上のノード１１と，最終的な電子署名を算出する代表ノード１４とを備える。
【００８５】
上記ノード１１は，分散電子署名システム８０１にＮ台（Ｎ≧１）存在することが可能であって，第１の実施の形態と同様，各ノード１１（１０−１，１０−２，…，１０−Ｎ）をノードＵ１，ノードＵ２，…，ノードＵＮで表すとする。
【００８６】
また，代表ノード１４をノードＵ０で表す。なお，ツリー構造のマルチホップネットワークは，図６のように，ツリー構造のグラフの各節が各ノード１１に，その枝が通信路に相当するようなネットワークである。第２の実施形態の場合，ツリーのルートが代表ノード１４に相当し，その他のノード１１が各節に相当する。
【００８７】
また，ノード１１又は代表ノード１４が親子関係にあるとき，親ノード，子ノードと記載する場合もある。例えば，図６のノードＵ１およびノードＵ２は，ノードＵ４の子ノードであり，逆に，ノードＵ４は，ノードＵ１およびノードＵ２の親ノードである。各ノード１１又は代表ノード１４は，ノード自身の子ノードと親ノードをともに把握しているものとする。
【００８８】
また，第１の実施形態と同様に，電子署名の秘密鍵をｄ，公開鍵をｅおよびｎ（ｅｄ＝１（ｍｏｄ  λ（ｎ）））と表す。
【００８９】
各々のノードＵ１，ノードＵ２，…，ノードＵＮ，および代表ノードＵ０は，元の秘密鍵ｄを秘密裏に分散秘密鍵ｄ１，分散秘密鍵ｄ２，…，分散秘密鍵ｄＮ，および分散秘密鍵ｄ０を分散して保持しており，それらの分散秘密鍵ｄ１，ｄ２，…，ｄＮと元の秘密鍵ｄとの関係は，上記式６に示すものとする。
【００９０】
（ノード１１について）
次に，図７を参照しながら，第２の実施の形態にかかるノード１１（ノードＵｉ（ｉ＝１，２，…，Ｎ））に備わる分散電子署名に係る計算を実行する分散電子署名計算部５００について説明する。なお，図７は，第２の実施の形態にかかるノード１１に備わる分散電子署名計算部１００の概略的な構成を示すブロック図である。
【００９１】
また，ツリー構造のグラフの葉に相当するノード１１は，第１の実施形態の各ノードＵｉ（ｉ＝１，２，…，Ｎ）における分散電子署名計算部１００（図２）と同じ構成の場合でもよい。例えば，図７に示すように，ノード１１−１，ノード１１−２，およびノード１１−３に備わる分散電子署名計算部５００は，上記図２に示す分散電子署名計算部１００と実質的に同一であってもよい。
【００９２】
図７に示すように，ノード１１に備わる分散電子署名計算部５００は，分散秘密鍵保持部５０１と，べき乗剰余計算部５０２と，乗算部５０３と，受信部５０４と，送信部５０５とから少なくとも構成される。
【００９３】
上記分散秘密鍵保持部５０１は，ノードＵｉの分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）を記憶する記憶装置である。
【００９４】
また，上記べき乗剰余計算部５０２は，電子署名したいメッセージｍおよび分散秘密鍵保持部５０１に記憶された分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）を入力し，下記式１１に示す分散電子署名ｓ’ｉを計算する。
【００９５】
ｓ’ｉ＝ｈ（ｍ）ｄｉ  （ｍｏｄ  ｎ）  （ｉ＝１，…，Ｎ）  …（式１１）
【００９６】
上記算出された分散電子署名ｓ’ｉは，乗算部５０３に出力される。なお，第１の実施形態と同様に，メッセージｍは，例えば，インターネット等の通信路を介して受信するものであってもよいし，予めノード１０内の記憶装置に保持されたものでもよいが，予め分散電子署名システム８０１で合意の取れた方式でメッセージｍを各ノードＵｉ（ｉ＝１，２，…，Ｎ）および代表ノードＵ０が取得できるものとする。
【００９７】
上記乗算部５０３は，べき乗剰余計算部５０２から算出された分散電子署名ｓ’ｉを受け取るとともに，受信部５０４を介して子ノードからの分散電子署名ｓｊ（ただし，ＵｊはＵｉのすべての子ノードとする）を受け取り，それらを下記式１２のように掛け合わせる。なお，乗算部５０３は，ノード１０自身に子ノードが存在しない場合，受信部５０４からの分散電子署名ｓｊを受け取る処理を行わない。
【００９８】
ｓｉ＝ｓ’ｉ  ×  Π  ｓｊ  （ｍｏｄ  ｎ）  …（式１２）
ＵｊはＵｉのすべての子ノードとする。
【００９９】
上記乗算部５０３により算出された分散電子署名ｓｉは，送信部５０５に出力される。
【０１００】
上記受信部５０４は，ノード１０自身に係る子ノード全てから，分散電子署名ｓｊ（ＵｊはＵｉのすべての子ノード）を受信し，乗算部５０３に出力する。
【０１０１】
上記送信部５０５は，乗算部５０３から計算結果である分散電子署名ｓｉを受け取り，それをノード１０自身に係る親ノードに送信する。例えば，図６に示すように，ノード１１−５に備わる送信部５０５は，ノード１１−５自身の親ノードである代表ノード１４に自己が算出した分散電子署名を送信する。
【０１０２】
次に，図８を参照しながら，第２の実施形態にかかる代表ノード１４に備わる分散電子署名に係る計算を実行する分散電子署名計算部６００について説明する。図８は，第２の実施の形態にかかる代表ノード１４に備わる分散電子署名計算部６００の概略的な構成を示すブロック図である。
【０１０３】
図８に示すように，代表ノード１４に備わる分散電子署名計算部６００は，分散秘密鍵保持部６０１と，べき乗剰余計算部６０２と，乗算部６０３と，受信部６０４とから少なくとも構成される。
【０１０４】
上記分散秘密鍵保持部６０１は，代表ノード１０３（ノードＵ０）の分散秘密鍵ｄ０を記憶する記憶装置である。例えば，分散秘密鍵保持部２０１は，ＥＥＰＲＯＭ，ＲＡＭ等のメモリを例示することができるが，かかる例に限定されない。
【０１０５】
上記べき乗剰余計算部６０２は，電子署名したいメッセージｍと分散秘密鍵保持部６０１に格納された分散秘密鍵ｄ０とを入力し，上記式８に示す分散電子署名ｓ０を計算して乗算部６０３に出力する。
【０１０６】
上記乗算部６０３は，べき乗剰余計算部６０２より計算結果である分散電子署名ｓ０を受け取り，さらに受信部６０４が受信した代表ノード１０３自身の子ノードからの分散電子署名ｓｊ（ＵｊはＵ０のすべての子ノード）を受け取り，下記式１３に示す乗算を実行し，その結果の電子署名ｓを出力する。
【０１０７】
ｓ＝ｓ０  ×    Π  ｓｊ  （ｍｏｄ  ｎ）  …（式１３）
ＵｊはＵ０のすべての子ノードとする。
【０１０８】
上記受信部６０４は，自身の各子ノードＵｊより分散電子署名ｓｊ（ＵｊはＵ０のすべての子ノード）を受信して，乗算部６０３に出力する。
【０１０９】
（分散電子署名の動作について）
次に，図９のフローチャートを参照しながら，第２の実施の形態にかかる分散電子署名に関する計算を実行するノード１１の動作について説明する。なお，図９は，第２の実施の形態にかかる分散電子署名に関する計算を実行するノード１１の動作の概略を示すフローチャートである。ただし，ツリー構造のグラフの葉に相当するノード１１は，第１の実施形態におけるノード１０の分散電子署名計算部１００の動作（図４参照）と同様なものであるが，ステップＳ３０２で，代表ノードＵ０へ分散電子署名ｓｉを送信するところをノード１１自身の親ノードに送信するように変更する。
【０１１０】
図９に示すように，まず，子ノードを持つ各ノードＵｉは，署名したいメッセージｍに対して，各自のノード１１が保持する分散秘密鍵ｄｉを用いて上記式１１に示すように分散電子署名ｓ’ｉを計算する（ステップＳ７０１）。
【０１１１】
なお，図９に示す分散電子署名ｓ’ｉを生成する処理（Ｓ７０１）は，図７に示すべき乗剰余計算部５０２による動作である。
【０１１２】
また，ステップＳ７０１と平行して，全ての子ノードＵｊ（ＵｊはＵｉのすべての子ノード）から分散電子署名ｓｊを受信する（ステップＳ７０２）。当該処理は，図７に示す受信部５０４による動作である。
【０１１３】
なお，本実施の形態ではステップＳ７０１とステップＳ７０２は略同時並行して実行されるように図示されているが，必ずしも同時進行の場合に限定されない。例えば，ステップＳ７０１の終了後にステップＳ７０２を実行する，あるいは，ステップＳ７０２の終了後にステップＳ７０１を実行する場合でも実施可能である。
【０１１４】
上記ステップＳ７０１と，上記ステップＳ７０２とが終了すると，次に，ステップＳ７０１で得られた分散電子署名ｓ’ｉと，上記ステップＳ７０２で受信した子ノードからの分散電子署名ｓｊ（ＵｊはＵｉのすべての子ノード）とを掛け合わせ，上記式１２に示すように分散電子署名ｓｉを生成して親ノードに送信する（ステップＳ７０３）。
【０１１５】
次に，図１０を参照しながら，第２の実施形態の分散電子署名を実行する代表ノードＵ０の動作について説明する。なお，図１０は，第２の実施の形態にかかる分散電子署名に関する計算を実行する代表ノード１４の動作の概略を示すフローチャートである。
【０１１６】
図１０に示すように，代表ノードＵ０は，署名したいメッセージｍに対して，代表ノードＵ０自身が保持する分散秘密鍵ｄ０を用いて分散電子署名ｓ０を上記式８に示すように生成する（ステップＳ８０１）。
【０１１７】
なお，図１０に示す分散秘密鍵ｄ０を用いて分散電子署名ｓ０を生成する処理（Ｓ４０１）は，上記説明したように，図８に示す代表ノード１４に備わるべき乗剰余計算部６０２による動作である。
【０１１８】
また，ステップＳ８０１と平行して，全ての子ノードＵｊ（ＵｊはＵ０のすべての子ノード）から分散電子署名ｓｊを受信する（ステップＳ８０２）。
【０１１９】
なお，各ノード１１から分散電子署名ｓｉを受信する処理は（Ｓ８０１），図８に示す受信部６０４による動作である。
【０１２０】
図１０に示すように，ステップＳ８０１とステップＳ８０２は，略同時並行して実行されるように図示されているが，必ずしも同時進行の場合に限定されない。例えば，ステップＳ８０１の終了後にステップＳ８０２を実行する，あるいは，ステップＳ８０２の終了後にステップＳ８０１を実行する場合でも実施可能である。
【０１２１】
上記ステップＳ８０１と上記ステップＳ８０２とが終了すると，次に，ステップＳ８０１で得られた分散電子署名ｓ０と，上記ステップＳ８０２で子ノードから受信した分散電子署名ｓｊ（ＵｊはＵ０のすべての子ノード）とを掛け合わせ，上記式１３に示すように電子署名ｓを生成する（Ｓ８０３）。
【０１２２】
なお，上記電子署名ｓを生成する処理（Ｓ４０３）は，図８に示す乗算部６０３による動作である。
【０１２３】
以上，第２の実施の形態にかかる分散電子署名システム８０１の説明を終了するが，かかる分散電子署名システム８０１によって，以下に示すような優れた効果が存在する。
（１）第１の実施形態と同様に，秘密鍵を各ノード１１でセキュアに分散して保持することで，各ノード１１が分散電子署名を生成し，代表ノード１４にそれらの分散電子署名を送信することにより，セキュリティ上不可欠な不正者によって虚偽の電子署名が作成されてしまうおそれを防止することができる。
（２）不正ノードの存在を把握することができないが，ノード１１相互の通信量を格段に削減することができる。特に，第２の実施形態では，ネットワークがツリー構造のマルチホップ通信路であると仮定し，ルーティングするノード１１が，分散電子署名を上記式１２の形で途中で所定処理を施して親ノードに送信することにより，ネットワーク全体の通信量を削減することが可能となる。
（３）また，第１の実施形態と同様に，分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）と元の秘密鍵ｄとの関係を保ちながら（式６），例えば，上記式１０に示すように，分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）と元の秘密鍵ｄとの関係を保ちながら，例えば，下記式１０に示すようにノードＵｉ（ｉ＝１，２，…，Ｎ）が保有する分散秘密鍵ｄｉの値（又は，ビット長）をノードＵ０の分散秘密鍵ｄ０よりも小さくすれば，計算能力の低いノード１０でも分散電子署名を迅速かつ的確に生成することが可能となる。
（４）また，秘密鍵ｄを各ノードが分散して保持しているため，少数のノードが分解・解析されて保持してある秘密鍵（分散秘密鍵）を盗まれても，盗難者が正しい署名を生成することが不可能である。
【０１２４】
（第３の実施形態について）
第３の実施形態では，第１の実施形態に，各ノードが持つ分散秘密鍵を更新する機能を追加する。なお，以下に示す説明では，第１の実施の形態にかかる分散電子署名システム８００と第３の実施の形態にかかる分散電子署名システム８０２とを比較し，特に異なる点について詳細に説明するが，その他の点については，特段の明示がない場合，ほぼ同様な構成であるため詳細な説明は省略する。
【０１２５】
まず，第１の実施形態，および，第２の実施形態と同様，電子署名であるＲＳＡ署名を分散計算する第３の実施形態のシステムは，１以上の個数のノードと，最終的な署名を算出する代表ノードと呼ばれる装置から成る。
【０１２６】
ノード１０はＮ個（Ｎ≧１）あるとし，それぞれのノード１０をＵ１，Ｕ２，…，ＵＮで表すとする。また，代表ノード１３をＵ０で表す。第１の実施形態，および，第２の実施形態と同様に，電子署名であるＲＳＡ署名の秘密鍵をｄ，公開鍵をｅ，ｎ（ｅｄ＝１（ｍｏｄ  λ（ｎ）））と表すことにする。
【０１２７】
各々のノードＵ１，ノードＵ２，…，ノードＵＮ，および，代表ノードＵ０は，元の秘密鍵ｄを秘密分散した分散秘密鍵ｄ１，分散秘密鍵ｄ２，…，分散秘密鍵ｄＮ，および分散秘密鍵ｄ０を保持しており，それらの分散秘密鍵ｄ１，分散秘密鍵ｄ２，…，分散秘密鍵ｄＮと元の秘密鍵ｄとの関係は，式６で示すものとする。
【０１２８】
ここで，第１の実施形態と同様に分散電子署名について簡単に説明すると，署名したいメッセージをｍとすると，ノードＵ１，Ｕ２，…，ＵＮは，以下の式７に示す計算を実行することで求められる分散電子署名ｓｉ（ｉ＝１，…，Ｎ）を代表ノードＵ０に送信する。
【０１２９】
ｓｉ＝ｈ（ｍ）ｄｉ  （ｍｏｄ  ｎ）  （ｉ＝１，…，Ｎ）  …（式７）
代表ノードＵ０は，まず，下記式８に示す計算を実行し，自己（代表ノードＵ０）の分散電子署名ｓ０を求める。
【０１３０】
ｓ０＝ｈ（ｍ）ｄ０  （ｍｏｄ  ｎ）  …（式８）
分散電子署名ｓ０が求まると，代表ノードＵ０は，さらにノード１０から受信済みの分散電子署名ｓ１，分散電子署名ｓ２，…，分散電子署名ｓＮを掛け合わせ，さらに代表ノードＵ０自身が生成した分散電子署名ｓ０を式９に示すように，掛け合わせることにより，代表ノードＵ０は最終的な電子署名ｓを求めることができる。
【０１３１】
ｓ＝ｓ０ｓ１ｓ２…ｓＮ  （ｍｏｄ  ｎ）  …（式９）
【０１３２】
ここで，第３の実施形態では，上記にて示すような分散電子署名計算を行うと同時に，各ノード１０が保有する分散秘密鍵ｄｉ（ｉ＝１，…，Ｎ），および，代表ノード１３が保有する分散秘密鍵ｄ０の更新を行う。
【０１３３】
かかるノード１０及び代表ノード１３が保有する分散秘密鍵を更新する理由は，所定時間ずっと同一の分散秘密鍵の場合，悪意あるノードによって分散秘密鍵が見破られる危険性が高まるためである。
【０１３４】
各ノード１０が持つ分散秘密鍵ｄｉ（ｉ＝１，…，Ｎ）と，その更新後の分散秘密鍵ｄ’ｉ（ｉ＝１，…，Ｎ）との変化量を分散秘密鍵Δｄｉ（ｉ＝１，…，Ｎ）と表すと，代表ノード１３が持つ分散秘密鍵ｄ０は，下記式１４及び式１５に示すような分散秘密鍵ｄ’０に更新される。
【０１３５】
ｄ’０＝ｄ０−（Δｄ１＋Δｄ２＋…＋ΔｄＮ）  …（式１４）
ｄ’ｉ＝ｄｉ＋Δｄｉ  （ｉ＝１，…，Ｎ）    …（式１５）
【０１３６】
次に，図１１を参照しながら，第３の実施形態に係るノードＵｉ（ｉ＝１，２，…，Ｎ）に備わる分散電子署名計算を行う分散電子署名計算部９００について説明する。なお，図１１は，第３の実施の形態にかかるノード１０に備わる分散電子署名計算部９００の概略的な構成を示すブロック図である。
【０１３７】
図１１に示す分散電子署名計算部９００は，図２に示す分散電子署名計算部１００に，さらに分散秘密鍵更新部９０４と，乱数生成部９０５とが追加されたような構成であって，分散電子署名計算部９００は，分散秘密鍵保持部９０１と，べき乗剰余計算部１０２と，送信部９０３と，分散秘密鍵更新部９０４と，乱数生成部９０５とを備えている。
【０１３８】
上記分散秘密鍵保持部９０１は，図２に示す分散電子署名計算部１００の分散秘密鍵保持部１０１と同様に，ノードＵｉの分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）を保持する記憶装置であるが，分散秘密鍵更新部９０４から出力されてくる更新後の分散秘密鍵ｄ’ｉを受け取り，それを更新前の分散秘密鍵ｄｉと置き換える動作をする。
【０１３９】
なお，上記分散秘密鍵ｄ’ｉは，上記分散秘密鍵ｄｉと置き換えるが，置き換えられた分散秘密鍵ｄｉは，例えば，破棄される他にも，他の秘密鍵によって暗号化され厳重に保管される場合等でも実施可能である。
【０１４０】
上記べき乗剰余計算部１０２は，図２に示す分散電子署名計算部１００のべき乗剰余計算部１０２と同様であるため詳細な説明は省略する。
【０１４１】
上記送信部９０３は，図２に示す分散電子署名計算部１００の送信部１０３と同様に，べき乗剰余計算部１０２による計算結果である分散電子署名ｓｉを受け取り，それを代表ノードＵ０に送信する。さらに，送信部９０３は，乱数生成部９０５から出力された上記分散秘密鍵ｄｉと分散秘密鍵ｄ’ｉとの変化量である分散秘密鍵Δｄｉを受け取り，それも代表ノードＵ０に送信する。なお，本実施の形態では，生成された乱数を分散秘密鍵Δｄとして記載するが，上記乱数と分散秘密鍵Δｄとは，ほぼ同義である。
【０１４２】
上記分散秘密鍵更新部９０４は，乱数生成部９０５からの分散秘密鍵Δｄｉを受け取り，上記式１５で示されるような分散秘密鍵ｄｉの更新を行い，更新された分散秘密鍵ｄ’ｉを分散秘密鍵保持部９０１に出力する。
【０１４３】
乱数生成部９０５は，乱数を生成し，その生成された乱数を分散秘密鍵Δｄｉとして，分散秘密鍵更新部９０４と送信部９０３に各々出力する。なお，乱数生成部９０５が生成する乱数は，容易に推測されない方式であれば，いかなる方式で乱数が生成される場合でも実施可能である。
【０１４４】
次に，図１２を参照しながら，第３の実施形態にかかる代表ノードＵ０に備わる分散電子署名計算を実行する分散電子署名計算部１０００について説明する。なお，図１２は，第３の実施の形態にかかる代表ノード１３に備わる分散電子署名計算部１０００の概略的な構成を示すブロック図である。
【０１４５】
図１２に示すように，分散電子署名計算部１０００は，図３に示す分散電子署名計算部２００に，さらに分散秘密鍵更新部１００５が追加される構成となっており，分散電子署名計算部１０００は，分散秘密鍵保持部１００１と，べき乗剰余計算部２０２と，乗算部２０３と，受信部１００４と，分散電子署名更新部１００５とを備えている。
【０１４６】
上記分散秘密鍵保持部１００１は，図３に示す分散電子署名計算部２００の分散秘密鍵保持部２０１と同様に，代表ノードＵ０の分散秘密鍵ｄ０を保持する記憶装置であるが，分散秘密鍵更新部１００５から出力される分散秘密鍵ｄ’０を受け取り，それを既に保有済みの分散秘密鍵ｄ０と置き換える動作もする。
【０１４７】
なお，べき乗剰余計算部２０２および乗算部２０３は，図３に示す分散電子署名計算部２００のべき乗剰余計算部２０２および乗算部２０３と同様なものであるため詳細な説明は省略する。
【０１４８】
上記受信部１００４は，各ノードＵｉより分散電子署名ｓｉ，および，分散秘密鍵の更新前後の変化量を示す分散秘密鍵Δｄｉ（ｉ＝１，２，…，Ｎ）を受信し，分散電子署名ｓｉは乗算部２０３へ，分散秘密鍵Δｄｉは分散秘密鍵更新部１００５に各々出力する。
【０１４９】
上記分散秘密鍵更新部１００５は，受信部１００４から分散秘密鍵Δｄｉを受け取り，上記式１４に示すような分散秘密鍵ｄ０の更新を行い，更新された分散秘密鍵ｄ’０を分散秘密鍵保持部１００１に出力する。
【０１５０】
（分散秘密鍵の更新動作について）
次に，図１３を参照しながら，第３の実施形態にかかる分散秘密鍵を更新する各ノードＵｉ（ｉ＝１，２，…，Ｎ）の動作について説明する。なお，図１３は，第３の実施の形態にかかる分散秘密鍵を更新するノード１０の動作の概略を示すフローチャートである。
【０１５１】
図１３に示すように，まず各ノードＵｉ（ｉ＝１，２，…，Ｎ）は，署名したいメッセージｍに対して，各自が保持する分散秘密鍵ｄｉを用いて分散電子署名ｓｉを，上記式７に示すように生成する（Ｓ１１０１）。
【０１５２】
なお，図１３に示す分散電子署名ｓｉを生成する処理（Ｓ１１０１）は，図１１に示すべき乗剰余計算部１０２による動作である。それと平行し，乱数を生成することで，分散秘密鍵Δｄｉを求める（Ｓ１１０２）。
【０１５３】
なお，図１３に示す分散秘密鍵Δｄｉを求める処理（Ｓ１１０２）は，乱数生成部９０５による動作である。
【０１５４】
また，上記ステップＳ１１０１とステップＳ１１０２は，図１３に示すように，略同時並行するように図示しているが，必ずしも同時進行の場合に限定されず，例えば，ステップＳ１１０１の終了後にステップＳ１１０２を実行する，あるいは，ステップＳ１１０２の終了後にステップＳ１１０１を実行する場合でも実施可能である。
【０１５５】
上記ステップＳ１１０１とステップＳ１１０２とが終了すると，次に，ステップＳ１１０１で生成した分散電子署名ｓｉ，および，分散秘密鍵Δｄｉを代表ノードＵ０に送信する（ステップＳ１１０３）。
【０１５６】
また，上記ステップＳ１１０３と平行して，自己（ノード１０）が保持する分散秘密鍵ｄｉを，分散秘密鍵Δｄｉを用いて上記式１５に示すように更新する（Ｓ１１０４）。
【０１５７】
なお，図１３に示す分散秘密鍵Δｄｉを用いて分散秘密鍵ｄｉを更新する処理（Ｓ１１０４）は，図１１に示す分散秘密鍵更新部９０４による動作である。
【０１５８】
なお，図１３に示すステップＳ１１０３とステップＳ１１０４とは，略同時並行するように図示されているが，必ずしも同時進行に限定されない。例えば，ステップＳ１１０３の終了後，ステップＳ１１０４を実行し，あるいは，ステップＳ１１０４の終了後，ステップＳ１１０３を実行する場合でも実施可能である。
【０１５９】
次に，図１４を参照しながら，第３の実施形態にかかる分散秘密鍵を更新する代表ノードＵ０の動作について説明する。なお，図１４は，第３の実施の形態にかかる分散秘密鍵を更新する代表ノード１３の動作の概略を示すフローチャートである。
【０１６０】
図１４に示すように，まず，代表ノードＵ０は，署名したいメッセージｍに対して，代表ノード１３自身が保持している分散秘密鍵ｄ０を用いて分散電子署名ｓ０を上記式８に示すように生成する（Ｓ１２０１）。
【０１６１】
なお，図１４に示す分散電子署名ｓ０を生成する処理（Ｓ１２０１）は，図１２に示すべき乗剰余計算部２０２による動作である。
【０１６２】
また，上記ステップＳ１２０１と平行して，各ノードＵｉ（ｉ＝１，２，…，Ｎ）から分散電子署名ｓｉ，および，分散秘密鍵Δｄｉを受信する（Ｓ１２０２）。
【０１６３】
なお，図１４に示す分散電子署名と分散秘密鍵Δｄｉを受信する処理（Ｓ１２０２）は，図１２に示す受信部１００４による動作である。
【０１６４】
また，ステップＳ１２０１とステップＳ１２０２とは，略同時進行するように図示されているが，必ずしも同時進行の場合に限定されず，例えば，ステップＳ１２０１の終了後，次にステップＳ１２０２を実行し，あるいは，ステップＳ１２０２の終了後，次にステップＳ１２０１を実行する場合でも実施可能である。
【０１６５】
ステップＳ１２０１，および，ステップＳ１２０２の終了後，次にステップＳ１２０１で得られた分散電子署名ｓ０と，ステップＳ１２０２で受信した分散電子署名ｓｉ（ｉ＝１，２，…，Ｎ）とを掛け合わせ，上記式９に示すように電子署名ｓを生成する（Ｓ１２０３）。
【０１６６】
なお，上記電子署名ｓを生成する処理（Ｓ１２０３）は，図１２に示す乗算部２０３による動作である。
【０１６７】
また，ステップＳ１２０３と平行して，分散秘密鍵ｄ０を，受信した分散秘密鍵Δｄｉ（ｉ＝１，２，…，Ｎ）を用いて上記式１４に示すように更新する（Ｓ１２０４）。
【０１６８】
なお，上記分散秘密鍵を更新する処理（Ｓ１２０４）は，図１２に示す分散秘密鍵更新部１００５による動作である。
【０１６９】
また，ステップＳ１２０３とステップＳ１２０４は，略同時進行するように図示されているが，必ずしも同時進行する場合に限定されず，例えば，ステップＳ１２０３の終了後，次にステップＳ１２０４を実行する，あるいは，ステップＳ１２０４の終了後，次にステップＳ１２０３を実行する場合でも実施可能である。
【０１７０】
なお，第３の実施の形態にかかる分散電子署名システム８０２で行われる分散秘密鍵の更新は，各ノード１０により分散秘密鍵Δｄｉ（ｉ＝１，…，Ｎ）各々が求められ，それらが代表ノード１３に送信されることにより，代表ノード１３にて分散秘密鍵ｄ’０に更新する場合を例に挙げて説明したが，かかる例に限定されない。例えば，まず代表ノード１３により乱数を生成することで，代表ノード１３が分散秘密鍵Δｄ０を生成し，その分散秘密鍵Δｄ０を基にして分散秘密鍵ｄ０を分散秘密鍵ｄ’０に更新する。さらに，上記分散秘密鍵Δｄ０を，各ノード１０に代表ノード１３が送信することにより，各ノード１０は，上記分散秘密鍵Δｄ０を基にして，自己の分散秘密鍵Δｄｉ（ｉ＝１，…，Ｎ）を求め，各ノード１０は，分散秘密鍵ｄｉ（ｉ＝１，…，Ｎ）を鍵ｄ’ｉ（ｉ＝１，…，Ｎ）に更新することができる。なお，各ノード１０が分散秘密鍵Δｄ０を基にして自己の分散秘密鍵Δｄｉ（ｉ＝１，…，Ｎ）を求めるために，例えば，各ノード１０間で自己の分散秘密鍵Δｄｉ（ｉ＝１，…，Ｎ）が予め定められることにより実施可能となるが，かかる例に限定されない。
【０１７１】
以上，第３の実施の形態にかかる分散電子署名システム８０２の説明を終了するが，かかる分散電子署名システム８０２によって，以下に示すような優れた効果が存在する。
（１）各ノード１０又は代表ノード１３が保有する分散秘密鍵を容易に更新することができる。かかる更新により，長期間同じ分散秘密鍵で分散電子署名を生成し続けるよりも，格段もセキュリティレベルを向上させることができ，外部から攻撃され分散秘密鍵が漏洩又は見破られてしまう危険性を減少させることができる。
【０１７２】
（第４の実施形態について）
第４の実施形態では，第２の実施形態に，各ノード１１又は代表ノード１４が持つ分散秘密鍵を更新する。なお，以下に示す説明では，第２の実施の形態にかかる分散電子署名システム８０１と第４の実施の形態にかかる分散電子署名システム８０３とを比較し，特に異なる点について詳細に説明するが，その他の点については，特段の明示がない場合，ほぼ同様な構成であるため詳細な説明は省略する。
【０１７３】
第２の実施形態と同様に，第４の実施形態では，ツリー構造のマルチホップネットワークが用いられている。
【０１７４】
また，第２の実施形態と同様に，電子署名（又は，ＲＳＡ署名）を分散的に計算するこの分散電子署名システム８０３は，１以上のノード１１と，最終的な署名を算出する代表ノード１４とを備えている。
【０１７５】
ノード１１はＮ個（Ｎ≧１）あるとし，それぞれのノードをＵ１，ノードＵ２，…，ノードＵＮで表す。また，代表ノードをＵ０で表す。
【０１７６】
ツリー構造のマルチホップネットワークは，図６に示すように，ツリー構造のグラフの各節が各ノードに，その枝が通信路に相当するようなネットワークである。ツリーのルートが代表ノードに相当し，そのほかのノードが各節に相当する。
【０１７７】
また，第２の実施形態と同様に，電子署名（又は，ＲＳＡ署名）の秘密鍵をｄ，公開鍵をｅ，ｎ（ｅｄ＝１（ｍｏｄ  λ（ｎ）））と表す。
【０１７８】
また，各々のノードＵ１，ノードＵ２，…，ノードＵＮ，および，代表ノードＵ０は，元の秘密鍵ｄを秘密分散した分散秘密鍵ｄ１，分散秘密鍵ｄ２，…，分散秘密鍵ｄＮ，および，分散秘密鍵ｄ０を保持しており，それらの分散秘密鍵ｄ１，分散秘密鍵ｄ２，…，分散秘密鍵ｄＮと元の秘密鍵ｄとの関係は，上記式６で表される。
【０１７９】
さらに，第４の実施形態では，第２の実施形態のような分散電子署名計算を行うと同時に，各ノード１１が保有する分散秘密鍵ｄｉ（ｉ＝１，…，Ｎ），および，代表ノードが保有する分散秘密鍵ｄ０の更新を行う。
【０１８０】
各ノード１１が保有する分散秘密鍵ｄｉ（ｉ＝１，…，Ｎ）から更新後の分散秘密鍵ｄ’ｉ（ｉ＝１，…，Ｎ）の変化量をΔｄ’ｉ（ｉ＝１，…，Ｎ）と表すと，代表ノードが保有する分散秘密鍵ｄ０は，下記式１６に示すような分散秘密鍵ｄ’０に更新する。
【０１８１】
ｄ’０＝ｄ０−Σ  Δｄｊ                                …（式１６）
ＵｊはＵ０のすべての子ノード
ｄ’ｉ＝ｄｉ＋Δｄ’ｉ  （ｉ＝１，…，Ｎ）              …（式１７）
Δｄｉ＝Δｄ’ｉ＋ΣΔｄｊ  （ｉ＝１，…，Ｎ）          …（式１８）
ＵｊはＵｉのすべての子ノード
【０１８２】
次に，図１５を参照しながら，第４の実施形態にかかるノードＵｉ（ｉ＝１，２，…，Ｎ）に備わる分散電子署名計算を行う分散電子署名計算部１３００について説明する。なお，図１５は，第４の実施の形態にかかるノード１１に備わる分散電子署名計算部１３００の概略的な構成を示すブロック図である。ただし，ツリー構造のグラフの葉に相当するノードは，第３の実施形態に係るノード１０に備わる分散電子署名計算部９００（図１１参照）と同じ構成でも実施可能である。
【０１８３】
上記分散電子署名計算部１３００は，図７に示す分散電子署名計算部５００に，さらに分散秘密鍵更新部１３０６と，乱数生成部１３０７と，加算部１３０８とが追加されるような構成になり，分散電子署名計算部１３００は，分散秘密鍵保持部１３０１，べき乗剰余計算部５０２，乗算部５０３，受信部１３０４，送信部１３０５，分散秘密鍵更新部１３０６，乱数生成部１３０７，および加算部１３０８を少なくとも備える。
【０１８４】
上記分散秘密鍵保持部１３０１は，ノードＵｉの分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）を保持する記憶装置であるが，分散秘密鍵更新部１３０６から出力された分散秘密鍵ｄ’ｉを受け取り，それを既に保有済みの分散秘密鍵ｄｉと置き換える動作もする。
【０１８５】
上記べき乗剰余計算部５０２は，図７に示す分散電子署名計算部５００のべき乗剰余計算部５０２と同様なものである。
【０１８６】
べき乗剰余計算部５０２は，署名したいメッセージｍおよび分散秘密鍵保持部５０１にある分散秘密鍵ｄｉ（ｉ＝１，２，…，Ｎ）を入力し，上記式１１に示す分散電子署名ｓ’ｉを計算する。
【０１８７】
上記算出した分散電子署名ｓ’ｉは，乗算部５０３に出力される。第１〜第３の実施形態と同様に，メッセージｍは，通信路を通して受信したものであってもよいし，予めノード内の記憶装置に保持しているものであってもよいが，予め分散電子署名システムで合意の取れた方式でメッセージｍを各ノードＵｉ（ｉ＝１，２，…，Ｎ）および代表ノードＵ０が取得できるものとする。
【０１８８】
上記乗算部５０３は，べき乗剰余算部５０２から算出された分散電子署名ｓ’ｉを受け取り，また，受信部１３０４から，子ノードから受信した分散電子署名ｓｊ（ただし，ＵｊはＵｉのすべての子ノードとする）を受け取り，それらを上記式１２に示すように掛け合わせる。なお，算出した分散電子署名ｓｉは，送信部１３０５に出力される。
【０１８９】
上記受信部１３０４は，ノード１１自身の子ノードすべてから，分散電子署名ｓｊ，および，分散秘密鍵Δｄｊ（ＵｊはＵｉのすべての子ノード）を受信し，分散電子署名は乗算部５０３へ，分散秘密鍵Δｄｊは加算部１３０８に出力する。
【０１９０】
上記送信部１３０５は，乗算部５０３による計算結果である分散電子署名ｓｉを，加算部１３０８による計算結果である分散秘密鍵Δｄｉを受け取り，それを親ノードに送信する。
【０１９１】
上記分散秘密鍵更新部１３０６は，乱数生成部１３０７から出力され，乱数から求められる分散秘密鍵Δｄ’ｉを受け取り，上記式１７に示すような分散秘密鍵ｄｉの更新を行い，更新された分散秘密鍵ｄ’ｉを分散秘密鍵保持部１３０１に出力する。
【０１９２】
上記乱数生成部１３０７は，生成した乱数を分散秘密鍵の変化量である分散秘密鍵Δｄ’ｉとして決定し，分散秘密鍵更新部１３０６，および，加算部１３０８に出力する。
【０１９３】
上記加算部１３０８は，受信部１３０４から分散秘密鍵Δｄｊ（ＵｊはＵｉのすべての子ノード）を，乱数生成部１３０７から分散秘密鍵Δｄ’ｉを受け取り，上記式１８のように加算を行って，その計算結果である分散秘密鍵Δｄｉを送信部１３０５に出力する。
【０１９４】
次に，図１６を参照しながら，第４の実施形態にかかる代表ノードＵ０に備わる分散電子署名計算を実行する分散電子署名計算部１４００について説明する。なお，図１６は，第４の実施の形態にかかる代表ノードに備わる分散電子署名計算部１４００の概略的な構成を示すブロック図である。
【０１９５】
図１６に示すように，分散電子署名計算部１４００は，図８に示す分散電子署名計算部６００に，さらに分散秘密鍵更新部１４０５が追加されるような構成であって，上記分散電子署名計算部１４００は，分散秘密鍵保持部１４０１と，べき乗剰余計算部６０２と，乗算部６０３と，受信部１４０４と，分散秘密鍵更新部１４０５とを備えている。
【０１９６】
上記分散秘密鍵保持部１４０１は，図８に示す分散電子署名計算部６００の分散秘密鍵保持部６０１と同様に，代表ノードＵ０の分散秘密鍵ｄ０を保持する記憶装置であるが，分散秘密鍵更新部１４０５から出力された分散秘密鍵ｄ’０を受け取り，それを既に格納済みの分散秘密鍵ｄ０と置き換える動作等も実行する。
【０１９７】
上記べき乗剰余計算部６０２と，乗算部６０３とは，図８に示す分散電子署名計算部６００のべき乗剰余計算部６０２と，乗算部６０３と実質的に同様なものであるため詳細な説明は省略する。
【０１９８】
上記受信部１４０４は，各子ノードＵｊより分散電子署名ｓｊと，生成された乱数により定められる分散秘密鍵の変化量である分散秘密鍵Δｄｊ（ＵｊはＵ０のすべての子ノード）を受信して，分散電子署名ｓｊは乗算部６０３に，分散秘密鍵Δｄｊは分散秘密鍵更新部１４０５に出力する。
【０１９９】
分散秘密鍵更新部１００５は，上記受信部１００４から分散秘密鍵Δｄｊを受け取り，上記式１６で表されるような分散秘密鍵ｄ０の更新を行い，更新された分散秘密鍵ｄ’０を分散秘密鍵保持部１４０１に出力する。
【０２００】
（分散秘密鍵の更新動作について）
次に，図１７を参照しながら，第４の実施形態にかかる分散秘密鍵を更新する各ノードＵｉ（ｉ＝１，２，…，Ｎ）の動作について説明する。なお，図１７は，第４の実施の形態にかかる分散秘密鍵を更新するノード１０の動作の概略を示すフローチャートである。ただし，ツリー構造のグラフの葉に相当するノードは，第３の実施形態のノードの分散電子署名計算部９００の動作（図１３）と同様なものであるが，ステップＳ１１０３で，代表ノードＵ０へ分散電子署名ｓｉを送信するところを自分の親ノードへ送信するように変更する。
【０２０１】
図１７に示すように，子ノードを持つ各ノードＵｉは，まず，署名したいメッセージｍに対して，各自のノード１１が保持する分散秘密鍵ｄｉを用いて上記式１１に示すように分散電子署名ｓ’ｉを計算する（Ｓ１５０１）。
【０２０２】
なお，分散電子署名ｓ’ｉを計算する処理（Ｓ１５０１）は，図１５に示すべき乗剰余計算部５０２による動作である。
【０２０３】
また，ステップＳ１５０１と平行して，分散秘密鍵の更新する際の変化量を示す分散秘密鍵Δｄ’ｉを生成する（Ｓ１５０２）。
【０２０４】
なお，分散秘密鍵Δｄ’ｉを生成する処理（Ｓ１５０２）は，図１５に示す乱数生成部１３０７による動作である。
【０２０５】
また，ステップＳ１５０１，および，ステップＳ１５０２と平行して，全ての子ノードＵｊ（ＵｊはＵｉのすべての子ノード）から分散電子署名ｓｊ，および，分散秘密鍵Δｄｊを受信する（Ｓ１５０３）。
【０２０６】
上記分散電子署名ｓｊ，および，分散秘密鍵Δｄｊを受信する処理（Ｓ１５０３）は，図１５に示す受信部１３０４による動作である。
【０２０７】
上記ステップＳ１５０１と，ステップＳ１５０２と，ステップＳ１５０３とは，図１７に示すように，略同時進行するように描かれているが，必ずしも同時進行に限られず，例えば，ステップＳ１５０１の終了後，次にステップＳ１５０２とステップＳ１５０３を実行し，あるいは，上記ステップＳ１５０２の終了後，次にステップＳ１５０１およびステップＳ１５０３を実行する場合等でも実施可能である。
【０２０８】
次に，ステップＳ１５０１，ステップＳ１５０２，および，ステップＳ１５０３の終了後，保持する分散秘密鍵ｄｉを，ステップＳ１５０２で得られた分散秘密鍵Δｄ’ｉを用いて上記式１７に示すように更新する（Ｓ１５０４）。
【０２０９】
なお，分散秘密鍵Δｄ’ｉを用いて上記式１７に示すように更新する処理（Ｓ１５０４）は，図１５に示す分散秘密鍵更新部１３０６による動作である。
【０２１０】
また，上記ステップＳ１５０４と平行して，ステップＳ１５０２で得られた分散秘密鍵Δｄ’ｉと，上記ステップＳ１５０３で受信した子ノードからの分散秘密鍵Δｄｊ（ＵｊはＵｉのすべての子ノード）とを足し合わせ，上記式１８に示すように分散秘密鍵Δｄｉを生成する（Ｓ１５０５）。
【０２１１】
上記分散秘密鍵Δｄｉを生成する処理（Ｓ１５０５）は，図１５に示す加算部１３０８による動作である。
【０２１２】
また，上記ステップＳ１５０４およびステップＳ１５０５と平行して，ステップＳ１５０１で得られた分散電子署名ｓ’ｉと，ステップＳ１５０３で受信した子ノードからの分散電子署名ｓｊ（ＵｊはＵｉのすべての子ノード）とを掛け合わせ，上記式１２に示すように分散電子署名ｓｉを生成する（Ｓ１５０６）。
【０２１３】
これは，上記図１５に示す乗算部５０３の動作である。ステップＳ１５０４，ステップＳ１５０５，およびステップＳ１５０６は，略同時進行するように描かれているが，必ずしも同時進行でなくてもよく，例えば，ステップＳ１５０４の終了後，次にステップＳ１５０５とステップＳ１５０６とを実行する場合，あるいは，上記ステップＳ１５０５の終了後，次にステップＳ１５０４とステップＳ１５０６とを実行する場合などでも実施可能である。
【０２１４】
次に，上記ステップＳ１５０４，ステップＳ１５０５，およびステップＳ１５０６の終了後，ステップＳ１５０５で得られた分散秘密鍵Δｄｉと上記ステップＳ１５０６で得られた分散電子署名ｓｉを親ノードに送信する（Ｓ１５０７）。
【０２１５】
次に，図１８を参照しながら，第４の実施形態に係る分散電子署名を実行する代表ノードＵ０の動作について説明する。なお，図１８は，第４の実施の形態にかかる分散秘密鍵を更新する代表ノード１４の動作の概略を示すフローチャートである。
【０２１６】
図１８に示すように，代表ノードＵ０は，署名したいメッセージｍに対して，自身が保持する分散秘密鍵ｄ０を用いて分散電子署名ｓ０を上記式８に示すように生成する（Ｓ１６０１）。
【０２１７】
なお，上記分散秘密鍵ｄ０を用いて分散電子署名ｓ０を生成する処理（Ｓ１６０１）は，図１６に示すべき乗剰余計算部６０２による動作である。
【０２１８】
また，ステップＳ１６０１と平行して，全ての子ノードＵｊ（ＵｊはＵ０のすべての子ノード）から分散電子署名ｓｊ，および，全ての子ノードからの分散秘密鍵の変化量である分散秘密鍵Δｄｊを受信する（ステップＳ１６０２）。
【０２１９】
これは，図１６の受信部１４０４による動作である。上記ステップＳ１６０１とステップＳ１６０２は略同時進行するように図示されているが，必ずしも同時進行でなくてもよく，例えば，ステップＳ１６０１の終了後，次にステップＳ１６０２を実行する場合，あるいは，ステップＳ１６０２の終了後，次にステップＳ１６０１を実行する場合などでも実施可能である。
【０２２０】
次に，ステップＳ１６０１およびステップＳ１６０２の終了後，ステップＳ１６０１で得られた分散電子署名ｓ０と，ステップＳ１６０２で子ノードから受信した分散電子署名ｓｊ（ＵｊはＵ０のすべての子ノード）とを掛け合わせ，上記式１３に示すように電子署名ｓを生成する（Ｓ１６０３）。これは，図１６に示す乗算部６０３の動作である。
【０２２１】
また，ステップＳ１６０３と平行して，分散秘密鍵ｄ０を，受信した分散秘密鍵Δｄｊ（ＵｊはＵ０のすべての子ノード）を用いて上記式１６に示すように更新する（Ｓ１６０４）。これは，図１６に示す分散秘密鍵更新部１４０５の動作である。
【０２２２】
なお，上記ステップＳ１６０３とステップＳ１６０４は略同時進行するように図示されているが，必ずしも同時進行の場合に限定されず，例えば，ステップＳ１６０３の終了後，次にステップＳ１６０４を実行する場合，あるいは，ステップＳ１６０４の終了後，次にステップＳ１６０３を実行する場合などでも実施可能である。
【０２２３】
以上，第４の実施の形態にかかる分散電子署名システム８０３の説明を終了するが，かかる分散電子署名システム８０３によって，以下に示すような優れた効果が存在する。
（１）第４の実施形態では，第２の実施形態と同様な効果を得ることができるが，さらに，各ノードの持つ分散秘密鍵を容易に更新することができる。したがって，長期間同じ分散秘密鍵で署名し続けるよりは，攻撃されて秘密鍵が推測され漏洩する等の危険性を減少させることができる。
【０２２４】
なお，第１〜第４の実施形態において，最終的に代表ノードが電子署名ｓを算出するのであるが，図１９〜図２２に示すのように，その電子署名が正しいか否かを検算する署名検算部１７０６をさらに備えた代表ノードの構成も考えられる（図１９〜図２２に示す分散電子署名計算部１７００から分散電子署名計算部２０００）。
【０２２５】
上記分散電子署名計算部１７００〜分散電子署名計算部２０００が上記署名検算部１７０６を備えることにより，ノードの故障や盗難などにより分散電子署名を計算することが実行できないノードがある場合には，それを検出することができる（ただし，どのノードであるかまでは特定することができない）。
【０２２６】
上記署名検算部１７０６は，算出された電子署名ｓ，電子署名公開鍵ｅ，および電子署名したメッセージｍを受け取り，下記式１９に示すような計算を行い算出したメッセージｍ’とメッセージｍに一方向性ハッシュ関数を施したｈ（ｍ）とを比較して，等しいと判断した場合，電子署名が正しく算出されたという検算結果を出力する。
【０２２７】
ｍ’＝ｓｅ  （ｍｏｄ  ｎ）    …（式１９）
【０２２８】
また一方で，上記署名検算部１７０６は，メッセージｍ’とｈ（ｍ）との算出値が異なると判断した場合，電子署名が正しく算出されていないという検算結果を出力する。
【０２２９】
なお，上述した一連の処理は，専用の回路素子等からなるハードウェアにより行うこともできるし，ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には，そのソフトウェアを構成するプログラムが，汎用のコンピュータやマイクロコンピュータ等の情報処理装置にインストールされ，上記情報処理装置をノード１０（又は，ノード１１）／代表ノード１３（又は，代表ノード１４）として機能させる。
【０２３０】
プログラムは，コンピュータに内蔵されている記録媒体としてのハードディスクやＥＥＰＲＯＭ，ＲＯＭなどに予め記録しておくことができる。
【０２３１】
あるいはまた，プログラムは，ハードディスクドライブに限らず，フレキシブルディスク，ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ  Ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ），磁気ディスク，半導体メモリなどのリムーバブル記録媒体に，一時的あるいは永続的に格納（記録）しておくことができる。
【０２３２】
なお，プログラムは，上述したようなリムーバブル記録媒体からコンピュータにインストールする他，ダウンロードサイトから，ディジタル衛星放送用の人工衛星を介して，コンピュータに無線で転送したり，ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ），インターネットといったネットワークを介して，コンピュータに有線で転送し，コンピュータでは，そのようにして転送されてくるプログラムを受信し，内蔵するハードディスク等にインストールすることができる。
【０２３３】
ここで，本明細書において，コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは，必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく，並列的あるいは個別に実行される処理（例えば，並列処理あるいはオブジェクトによる処理）も含むものである。
【０２３４】
また，プログラムは，１のコンピュータにより処理されるものであっても良いし，複数のコンピュータによって分散処理されるものであっても良い。
【０２３５】
なお，本実施の形態では，不正を行う装置（ノード）が存在する場合にでも電子署名を生成できる機能や，不正を行う装置（ノード）を特定する機能を省くことにより，分散して計算する全部のノードとお互いに必ずしも通信する必要がなく，またノードの性能に応じた分散計算ができるように，適切な大きさの分散秘密鍵を各々のノードが保持することができる。
【０２３６】
以上，添付図面を参照しながら本発明の好適な実施形態について説明したが，本発明はかかる例に限定されない。当業者であれば，特許請求の範囲に記載された技術的思想の範疇内において各種の変更例または修正例を想定し得ることは明らかであり，それらについても当然に本発明の技術的範囲に属するものと了解される。
【図面の簡単な説明】
【０２３７】
【図１】第１の実施形態に係る分散電子署名システムの概略を示す説明図である。
【図２】第１の実施の形態にかかるノードに備わる分散電子署名計算部の概略的な構成を示すブロック図である。
【図３】第１の実施の形態にかかる代表ノードに備わる分散電子署名計算部の概略的な構成を示すブロック図である。
【図４】第１の実施の形態にかかる分散電子署名に関する計算を実行するノードの動作の概略を示すフローチャートである。
【図５】第１の実施の形態にかかる分散電子署名に関する計算を実行する代表ノードの動作の概略を示すフローチャートである。
【図６】第２の実施形態に係る分散電子署名システムの概略を示す説明図である。
【図７】第２の実施の形態にかかるノードに備わる分散電子署名計算部の概略的な構成を示すブロック図である。
【図８】第２の実施の形態にかかる代表ノードに備わる分散電子署名計算部の概略的な構成を示すブロック図である。
【図９】第２の実施の形態にかかる分散電子署名に関する計算を実行するノードの動作の概略を示すフローチャートである。
【図１０】第２の実施の形態にかかる分散電子署名に関する計算を実行する代表ノードの動作の概略を示すフローチャートである。
【図１１】第３の実施の形態にかかるノードに備わる分散電子署名計算部の概略的な構成を示すブロック図である。
【図１２】第３の実施の形態にかかる代表ノードに備わる分散電子署名計算部の概略的な構成を示すブロック図である。
【図１３】第３の実施の形態にかかる分散秘密鍵を更新するノードの動作の概略を示すフローチャートである。
【図１４】第３の実施の形態にかかる分散秘密鍵を更新する代表ノードの動作の概略を示すフローチャートである。
【図１５】第４の実施の形態にかかるノードに備わる分散電子署名計算部の概略的な構成を示すブロック図である。
【図１６】第４の実施の形態にかかる代表ノードに備わる分散電子署名計算部の概略的な構成を示すブロック図である。
【図１７】第４の実施の形態にかかる分散秘密鍵を更新するノードの動作の概略を示すフローチャートである。
【図１８】第４の実施の形態にかかる分散秘密鍵を更新する代表ノードの動作の概略を示すフローチャートである。
【図１９】第１の実施の形態にかかる代表ノードの概略的な構成を示すブロック図である。
【図２０】第２の実施の形態にかかる代表ノードの概略的な構成を示すブロック図である。
【図２１】第３の実施の形態にかかる代表ノードの概略的な構成を示すブロック図である。
【図２２】第４の実施の形態にかかる代表ノードの概略的な構成を示すブロック図である。
【符号の説明】
【０２３８】
１０，１１  ノード
１３，１４  代表ノード
１００      分散電子署名計算部
１０１      分散秘密鍵保持部
１０２      べき乗剰余計算部
１０３      送信部
【図１】
2006352254.tif 000003
【図２】
2006352254.tif 000004
【図３】
2006352254.tif 000005
【図４】
2006352254.tif 000006
【図５】
2006352254.tif 000007
【図６】
2006352254.tif 000008
【図７】
2006352254.tif 000009
【図８】
2006352254.tif 000010
【図９】
2006352254.tif 000011
【図１０】
2006352254.tif 000012
【図１１】
2006352254.tif 000013
【図１２】
2006352254.tif 000014
【図１３】
2006352254.tif 000015
【図１４】
2006352254.tif 000016
【図１５】
2006352254.tif 000017
【図１６】
2006352254.tif 000018
【図１７】
2006352254.tif 000019
【図１８】
2006352254.tif 000020
【図１９】
2006352254.tif 000021
【図２０】
2006352254.tif 000022
【図２１】
2006352254.tif 000023
【図２２】
2006352254.tif 000024