(57)【要約】【課題】  メッセージがグループ中の閾値以上のエンティティーにより電子署名されたかどうかを、比較的小さな公開鍵のサイズで確認できる電子署名方法を提供する。【解決手段】  センタは２組のペアをＪ個含む集合を公開し、エンティティーは２組のペアの一方をＪ回選択し、ペアの一方を暗号化鍵とし、他方を復号鍵とし、Ｊ個の暗号化鍵の積とＪ個の復号鍵の積とを求める。センタは全エンティティーに渡る暗号化鍵と復号鍵の積を求め、その逆数Γ−１を公開する。メッセージｍに電子署名する際に、エンティティー毎の暗号化鍵とΓ−１とで暗号化し、電子署名に参加したエンティティーの復号鍵を用い、電子署名に参加しなかったエンティティーの暗号化鍵と復号鍵との積を推定し、復号する。所定の試行回数内で復号に成功した場合、閾値以上のエンティティーが電子署名したものとする。【選択図】    図１
2005184134.tif 000002
【特許請求の範囲】
【請求項１】
メッセージを第１の秘密鍵で暗号化することにより電子署名し、第２の鍵で復号することにより、該電子署名を確認するようにした電子署名方法において、
センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、
各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、
センタは、エンティティーの秘密鍵(秘密鍵の数Ｎ)の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、
Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、
かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認する、ようにしたことを特徴とする電子署名方法。
【請求項２】
前記秘密鍵の候補でのＪ次元の各選択肢の各々が少なくとも一対のデータから成り、Ｊ対のデータから各対毎に一方を選択して電子署名用の秘密鍵を構成し、Ｊ対のデータの各対毎の他方から電子署名の確認用の鍵を構成し、
かつ前記関数Γを該一対のデータの交換に関して対称にすることにより、
Γを変更せずに、エンティティーはＪ対のデータからの選択を変更することにより、電子署名用の秘密鍵と確認用の鍵を変更自在にし、さらに復号時には電子署名に参加しなかったエンティティーの秘密鍵と確認用の鍵の双方を推定するようにしたことを特徴とする、請求項１の電子署名方法。
【請求項３】
複数のセンタＡ,Ｂを設けて、センタ毎に前記秘密鍵の候補ＳA，ＳBと前記逆元ΓA−１，ΓB−１をエンティティーに公開し、エンティティーはセンタ毎の秘密鍵を記憶し、
かつエンティティーは、メッセージｍに対して、センタAに対する逆元ΓA−１と、センタAに対する秘密鍵とで第１段の電子署名をすると共に、センタBに対する逆元ΓB−１と、センタAに対する秘密鍵とで第２段の電子署名をし、
電子署名されたメッセージに対して、電子署名を行わなかったエンティティーに対する、センタAに関する秘密鍵とセンタBに関する秘密鍵とを所定の制約下で推定して、メッセージｍを復号することにより電子署名を確認するようにしたことを特徴とする、請求項１または２の電子署名方法。
【請求項４】
各々エンティティーとセンタとからなる複数のグループＡ，Ｂを設けて、
グループ単位での公開鍵ＥA，ＥBを公開すると共に、各グループでの前記逆元をグループ内の各エンティティーの秘密鍵とグループ単位での公開鍵との関数の逆元とし、
グループＡでは、電子署名するメッセージｍに対して、署名に参加するエンティティーの秘密鍵と、グループＡでの前記逆元と、電子署名に参加しなかったエンティティーの秘密鍵を所定の制約下で推定した値と、グループＢでの公開鍵とで、合計２段に暗号化してグループＢに送信し、
グループＢでは、受信した暗号文の復号に参加するエンティティーの秘密鍵を用いて、所定の制約下で復号に参加しなかったエンティティーの秘密鍵を推定して１段分の復号を行うと共に、グループＡの公開鍵を用いて残る１段分の復号を行い、グループＡの閾値以上のエンティティーが電子署名したメッセージｍを、グループＢの閾値以上のエンティティーが参加して復号したメッセージである、と確認するようにしたことを特徴とする、請求項１〜３のいずれかの電子署名方法。
【請求項５】
エンティティ全体の集合を複数の小グループに分割すると共に、
原メッセージｍを秘密分散法により複数の部分メッセージに変換して、各部分メッセージが原メッセージｍの一部の情報を反映し、かつ所定個数以上の部分メッセージにより原メッセージｍを再現し得るようにして、各小グループに少なくとも１個の部分メッセージを送信し、
小グループで閾値以上のエンティティーが電子署名した部分メッセージを集めて、前記所定個数以上の部分メッセージが電子署名されたかどうかにより、所定の割合以上のエンティティーが電子署名したかどうかを確認するようにしたことを特徴とする、請求項１〜４のいずれかの電子署名方法。
【請求項６】
前記秘密分散法では中国人の剰余定理を用い、原メッセージｍをｇ項の多項式ｍ(Ｘ)として、前記部分メッセージとして該多項式ｍ(Ｘ)を小グループＧi毎の値αiで評価した評価値ｍ(αi)を用い、
電子署名された評価値ｍ(αi)がｇ以上の場合に、中国人の剰余定理を用いて原メッセージｍを復号し、所定の割合以上のエンティティーが電子署名したことを確認するようにしたことを特徴とする、請求項５の電子署名方法  
【請求項７】
センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、
各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、
センタは、エンティティーの秘密鍵(秘密鍵の数Ｎ)の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、
Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、
かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認するようにした電子署名方法用のプログラムであって、
エンティティーに対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを送信するための命令と、
各エンティティーから秘密鍵の選択に関する情報を秘密に受信するための命令と、
受信した秘密鍵に関する情報からエンティティーの秘密鍵全体の関数Γを求めて、所定の演算に関するΓの逆元Γ−１を各エンティティーに対して送信するための命令、とを設けたことを特徴とする、センタ用の電子署名プログラム。
【請求項８】
センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、
各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、
センタは、エンティティーの秘密鍵の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、
Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、
かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認するようにした電子署名方法用のプログラムであって、
秘密鍵の候補から、各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶するための命令と、
秘密鍵の選択に関する情報を前記Γ−１の演算のためにセンタに秘密送信するための命令と、
記憶した秘密鍵を用いて、メッセージに署名するための命令、とを備えたことを特徴とする、エンティティー用の電子署名プログラム。
【請求項９】
センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、
各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、
センタは、エンティティーの秘密鍵の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、
Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、
かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認するようにした電子署名方法用の装置であって、
エンティティーに対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを送信するための手段と、
各エンティティーから秘密鍵の選択に関する情報を秘密に受信するための命令と、
受信した秘密鍵に関する情報からエンティティーの秘密鍵全体の関数Γを求めて、所定の演算に関するΓの逆元Γ−１を各エンティティーに対して送信するための手段、とを設けたことを特徴とする、センタ用の電子署名装置。
【請求項１０】
センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、
各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、
センタは、エンティティーの秘密鍵の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、
Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、
かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認するようにした電子署名方法用の装置であって、
センタから公開された秘密鍵の候補から、各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶するための手段と、
秘密鍵の選択に関する情報を前記Γ−１の演算のためにセンタに秘密送信するための命令と、
記憶した秘密鍵を用いて、メッセージに署名するための手段、とを備えたことを特徴とする、エンティティー用の電子署名装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は電子署名に関する。
【背景技術】
【０００２】
非特許文献１，２は閾値暗号を開示している。この暗号は例えば秘密鍵の秘匿に用いられ、大きな秘密鍵を多数の分散鍵に分解し、これらを例えば別個に保管する。そして閾値以下の数の分散鍵では元の秘密鍵を再現できず、また元の秘密鍵に関して得られる情報量を実質的に０にでき、しかも閾値以上の分散鍵で元の秘密鍵を再現できるようにできる。
【０００３】
発明者らによってＲＳＡ暗号に対し、特別な形の法ｎ、即ち
ｎ＝１０a−ｂ(ａ，ｂは正整数)        
を用いる手法が提案されている(非特許文献３，４)。これによってＲＳＡ暗号において以下のことが実現される。
(1)  高速化が可能となる、
(2)  公開鍵サイズを小さくし得る、
(3)  署名に用いる際、相互に使用する法の大小関係を考慮することが、現実的問題として必要でなくなる。
ここではｎ，a及びｂのサイズを｜ｎ｜〜 １０００ビット、ａ＝１６０，｜ｂ｜〜 １６０ビットと仮定する。
【非特許文献１】Y.Desmet, and Y.Frankel："Theshold Cryptosystems", Crypto '89(LNCS 435)1988,pp.307-315.
【非特許文献２】T.Pedersen："A theshold cryptosystems without a trusted party", EuroCrypt'91, 1991, pp.522-526
【非特許文献３】佐竹賢治、笠原正雄；”高速べき乗剰余演算を用いた簡便なＲＳＡ暗号の一構成法”、電子情報通信学会論文誌  1996.3
【非特許文献４】筒井幸恵，笠原正雄：”ＲＳＡ暗号方式における高速べき乗剰余演算に関する考察”、情報理論とその応用シンポジウム、Dec.1997,pp.529-532
【発明の開示】
【発明が解決しようとする課題】
【０００４】
この発明の基本的課題は、閾値以上のエンティティーが署名に参加したことを確認できる、新たな電子署名方法とそのプログラム並びに電子署名装置を提供することにある。
【課題を解決するための手段】
【０００５】
この発明は、メッセージを第１の秘密鍵で暗号化することにより電子署名し、第２の鍵で復号することにより、該電子署名を確認するようにした電子署名方法において、
センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、
各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、
センタは、エンティティーの秘密鍵(秘密鍵の数Ｎ)の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、
Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、
かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認する、ようにしたことを特徴とする。
【０００６】
好ましくは、前記秘密鍵の候補でのＪ次元の各選択肢の各々が少なくとも一対のデータから成り、Ｊ対のデータから各対毎に一方を選択して電子署名用の秘密鍵を構成し、Ｊ対のデータの各対毎の他方から電子署名の確認用の鍵を構成し、かつ前記関数Γを該一対のデータの交換に関して対称にすることにより、Γを変更せずに、エンティティーはＪ対のデータからの選択を変更することにより、電子署名用の秘密鍵と確認用の鍵を変更自在にし、さらに復号時には電子署名に参加しなかったエンティティーの秘密鍵と確認用の鍵の双方を推定する。
【０００７】
また好ましくは、複数のセンタA,Bを設けて、センタ毎に前記秘密鍵の候補ＳA，ＳBと前記逆元ΓA−１，ΓB−１をエンティティーに公開し、エンティティーはセンタ毎の秘密鍵を記憶し、かつエンティティーは、メッセージｍに対して、センタAに対する逆元ΓA−１と、センタAに対する秘密鍵とで第１段の電子署名をすると共に、センタBに対する逆元ΓB−１と、センタAに対する秘密鍵とで第２段の電子署名をし、電子署名されたメッセージに対して、電子署名を行わなかったエンティティーに対する、センタAに関する秘密鍵とセンタBに関する秘密鍵とを所定の制約下で推定して、メッセージｍを復号することにより電子署名を確認する。
【０００８】
好ましくは、各々エンティティーとセンタとからなる複数のグループＡ，Ｂを設けて、グループ単位での公開鍵ＥA，ＥBを公開すると共に、各グループでの前記逆元をグループ内の各エンティティーの秘密鍵とグループ単位での公開鍵との関数の逆元とし、グループＡでは、電子署名するメッセージｍに対して、署名に参加するエンティティーの秘密鍵と、グループＡでの前記逆元と、電子署名に参加しなかったエンティティーの秘密鍵を所定の制約下で推定した値と、グループＢでの公開鍵とで、合計２段に暗号化してグループＢに送信し、グループＢでは、受信した暗号文の復号に参加するエンティティーの秘密鍵を用いて、所定の制約下で復号に参加しなかったエンティティーの秘密鍵を推定して１段分の復号を行うと共に、グループＡの公開鍵を用いて残る１段分の復号を行い、グループＡの閾値以上のエンティティーが電子署名したメッセージｍを、グループＢの閾値以上のエンティティーが参加して復号したメッセージである、と確認する。ここで例えば、グループＢでの復号で、受信した暗号文の復号に参加するエンティティーの秘密鍵と、グループＢでの前記逆元を用いても良く、あるいはグループＡでグループＢの公開鍵を用いて暗号化する際に、グループＢでの逆元Γ−１の逆元、即ちグループＢでの関数Γを用いても良い。
【０００９】
好ましくは、エンティティ全体の集合を複数の小グループに分割すると共に、原メッセージｍを秘密分散法により複数の部分メッセージに変換して、各部分メッセージが原メッセージｍの一部の情報を反映し、かつ所定個数以上の部分メッセージにより原メッセージｍを再現し得るようにして、各小グループに少なくとも１個の部分メッセージを送信し、小グループで閾値以上のエンティティーが電子署名した部分メッセージを集めて、前記所定個数以上の部分メッセージが電子署名されたかどうかにより、所定の割合以上のエンティティーが電子署名したかどうかを確認する。なお秘密分散法の種類は任意である。
【００１０】
特に好ましくは、前記秘密分散法では中国人の剰余定理を用い、原メッセージｍをｇ項の多項式ｍ(Ｘ)として、前記部分メッセージとして該多項式ｍ(Ｘ)を小グループＧi毎の値αiで評価した評価値ｍ(αi)を用い、電子署名された評価値ｍ(αi)がｇ以上の場合に、中国人の剰余定理を用いて原メッセージｍを復号し、所定の割合以上のエンティティーが電子署名したことを確認する。
【００１１】
この発明のセンタ用の電子署名プログラムは、センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、センタは、エンティティーの秘密鍵(秘密鍵の数Ｎ)の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認するようにした電子署名方法用のプログラムであって、
エンティティーに対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを送信するための命令と、
各エンティティーから秘密鍵の選択に関する情報を秘密に受信するための命令と、
受信した秘密鍵に関する情報からエンティティーの秘密鍵全体の関数Γを求めて、所定の演算に関するΓの逆元Γ−１を各エンティティーに対して送信するための命令、とを設けたことを特徴とする。
【００１２】
この発明のエンティティー用の電子署名プログラムは、センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、センタは、エンティティーの秘密鍵の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認するようにした電子署名方法用のプログラムであって、
秘密鍵の候補から、各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶するための命令と、
秘密鍵の選択に関する情報を前記Γ−１の演算のためにセンタに秘密送信するための命令と、
記憶した秘密鍵を用いて、メッセージに署名するための命令、とを備えたことを特徴とする。
【００１３】
この発明のセンタ用の電子署名装置は、センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、センタは、エンティティーの秘密鍵の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認するようにした電子署名方法用の装置であって、
エンティティーに対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを送信するための手段と、
各エンティティーから秘密鍵の選択に関する情報を秘密に受信するための命令と、
受信した秘密鍵に関する情報からエンティティーの秘密鍵全体の関数Γを求めて、所定の演算に関するΓの逆元Γ−１を各エンティティーに対して送信するための手段、とを設けたことを特徴とする。
【００１４】
この発明のエンティティー用の電子署名装置は、センタは、エンティティー(エンティティー数Ｎ)に対して、秘密鍵の候補としてＪ次元のデータで各次元毎に複数の選択肢があるものを公開し、各エンティティーは、該候補から各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶し、センタは、エンティティーの秘密鍵の関数Γを求めて、所定の演算に関するΓの逆元Γ−１をエンティティーに送信し、Ｎ中Ｋのエンティティーがメッセージｍに署名する場合、前記逆元Γ−１と、署名する各エンティティーの合計Ｋ個の秘密鍵とで、前記メッセージｍを暗号化することにより電子署名し、かつ暗号化したメッセージｍに対して、所定の制約下で残るＮ−Ｋのエンティティーの秘密鍵を推定して、暗号化したメッセージを復号することにより、閾値以上の数のエンティティーがメッセージｍに電子署名したことを確認するようにした電子署名方法用の装置であって、
センタから公開された秘密鍵の候補から、各次元毎に選択肢の１つを選択して、選択したＪ個のデータにより秘密鍵を構成して記憶するための手段と、
秘密鍵の選択に関する情報を前記Γ−１の演算のためにセンタに秘密送信するための命令と、
記憶した秘密鍵を用いて、メッセージに署名するための手段、とを備えたことを特徴とする。
【００１５】
エンティティーとセンタは物理的には同一でも良く、エンティティーはメンバに対応する情報通信機器であり、公開はＣＤ−ＲＯＭなどによる公開でも、ネットワークなどを介しての送信による公開でも良い。
【発明の効果】
【００１６】
この発明では、各エンティティーは少なくとも２J個以上の鍵選択の自由度を持ち、Ｊを増すほど、電子署名に参加しなかったエンティティーの鍵の推定が困難になり、同時に電子署名の閾値が鋭くなる。その一方でメンバの数が多い場合、Ｊの値を大きくすると、電子署名されたメッセージの復号に必要な試行回数が増す。そこでＪの値を、鍵の推定が適度の困難さを持ち、かつ閾値が所望の鋭さを持つように選択する。また電子署名に参加しなかったエンティティーの鍵を正しく推定した際に、元のメッセージが復号されるように、公開鍵Γ-1を定める。公開鍵Γ-1を定めるため、エンティティーの鍵選択に関する情報をセンタが秘密裏に受信し、エンティティーの秘密鍵全体の関数Γを求めて、所定の演算に関するΓの逆元Γ-1を求める。そして情報処理上では、エンティティーが秘密鍵により電子署名し、かつ電子署名に参加しなかったエンティティーの秘密鍵を正しく推定できた際に、これらの鍵の全体とΓ-1とが打ち消しあって、電子署名により暗号化されたメッセージが復号されるようにする。例えば演算が秘密鍵の間で積の場合、Γ-1はΓに対する適宜の法での逆元であり、秘密鍵の間の演算が加算である場合、Γ-1は例えば秘密鍵の加算の符号を反転したものである。
【００１７】
以上のようにこの発明では、電子署名に参加しなかったエンティティーの秘密鍵を所定の制約下に推定することができるかどうかにより、閾値以上のエンティティーが電子署名に参加したかどうかを確認できる。またこの時、電子署名に参加しなかったエンティティーの秘密鍵を正しく推定できれば、元のメッセージが復号される。実施例で示すように、この電子署名に必要な公開鍵のサイズは比較的小さく、この発明の電子署名は、投票やアンケート、会社や学校などの組織での、署名付の通信などに用いることができる。
【００１８】
この発明の電子署名の問題点として、センタがエンティティーの秘密鍵を推定して、電子署名されたメッセージを復号する可能性がある点がある。これに対して、秘密鍵の選択候補でのＪ次元の選択肢の各々が少なくとも一対のデータから成り、これらのデータの一方を電子署名用の秘密鍵とし、他方を電子署名の確認用の鍵として、秘密鍵と確認用の鍵の対称関数としてΓ-1を構成すると、エンティティーは電子署名用の秘密鍵と復号用の鍵を例えば毎回変更できる。例えばＪ＝２０とすると、２０通りのペアから署名用の秘密鍵と確認用の鍵を構成する自由度は２20に上り、センタがエンティティーの鍵を推定することが困難になる。このようにしてエンティティーが鍵を変更し得るようにすると、センタによる復号などを防止できる。またセンタに関する問題として、センタが適当なメッセージを作成し、これに適当な電子署名を加えて、自ら復号する可能性がある。これに対してセンタを複数設けると、センタによる復号を防止できる。
【００１９】
電子署名の用い方として、グループＡで閾値以上のエンティティーが電子署名したメッセージをグループＢに送信し、グループＢで閾値以上のエンティティーが復号に参加すると、復号するというものがある。この場合、グループＡでは前記のように電子署名を施して復号を試み、復号に成功した場合、実際に誰が電子署名したのかを秘密に保ったままで、グループＡ内の閾値以上のエンティティーが電子署名したことを確認できる。そこでグループＡでは、電子署名に参加したエンティティーの秘密鍵と、電子署名に参加しなかったエンティティーの秘密鍵の推定値と、グループＡでの前記の逆元とで１段に暗号化し、これにグループＢの公開鍵で他段の暗号化を施して、合計２段に暗号化する。なお１段目の暗号化と２段目の暗号化はいずれを先に行っても良い。グループＢでは自己の公開鍵による暗号化が施されているので、復号に参加するエンティティーの秘密鍵を用いると共に、復号に参加しなかったエンティティーの秘密鍵を推定して復号し、さらにグループＡの公開鍵で復号することにより、元のメッセージを復号する。復号に所定の制約下で成功すると、グループＡでは閾値以上のエンティティーが電子署名し、グループＢでも閾値以上のエンティティーが復号に参加していることが保証される。
【００２０】
この発明での、電子署名に参加しなかったエンティティーの鍵の総数は、署名に参加しなかったエンティティーの数をＦとし、前記のＪを用いて、(Ｆ＋１)Jで表すことができる。この値はＪが大きいほど鋭く増加し、閾値が鋭くなり、実用的にはＦを小さくし、Ｊを大きくすることが好ましい。しかしこのようにすると、大きなグループでの電子署名が困難になる。そこで全体としてのグループを多数の小グループに分割し、各小グループ内でこの発明の閾値電子署名を行うと、閾値を鋭く保つことができる。複数の小グループに対して、例えば秘密分散法を適用し、所定の割合以上の小グループで電子署名が行われた際に、元のメッセージが全体として復号されるようにすると、エンティティーの数が増すと閾値が緩やかになるとの問題を解決できる。
【００２１】
特に秘密分散法として中国人の剰余定理を用い、ｇ項の多項式でメッセージを表現し、この多項式を小グループ毎の値で評価したものに対して、各小グループでの電子署名を求める。実施例で示すように、ｇ以上の小グループで電子署名が成されると、メッセージｍを全体として復号できる。そこで小グループの数と多項式の項の数ｇとの比、並びに各小グループでの電子署名に必要な閾値の２つにより、所定の割合以上のエンティティーの参加により電子署名を行うことができる。このような手法は、１００万あるいは１億などのエンティティーを対象としても可能なため、選挙などや大規模なアンケートなどにも用いることができる。
【発明を実施するための最良の形態】
【００２２】
以下に本発明を実施するための最適実施例を示す。
【実施例１】
【００２３】
図１に、実施例の閾値電子署名システム２を示す。インターネットなどの適宜のネットワーク４に例えば一対のセンタ６を設け、その一方をセンタＡと呼び、他方をセンタＢと呼ぶ。なお１つのセンタのみを設けても良く、あるいは３つ以上のセンタを設けても良い。さらに物理的にはセンタはエンティティーと同じものでも良い。１０は閾値電子署名システム２に参加した複数のエンティティーで、その総数をＮとし、エンティティー１０を全体としてグループＧ等と呼ぶことがある。センタ６やエンティティー１０に必要な電子署名プログラム１２は、例えばネットワーク４を介して供給される。これに代えて、電子署名プログラム１２をＣＤ−ＲＯＭなどにより供給しても良い。公開鍵１４も同様にネットワーク４を介して供給され、公開鍵１４には例えば、後述の集合Ｓ，法ｎ，逆元Γ-1などがある。メッセージ１６も、ネットワーク４を介してエンティティー１０間やエンティティー１０とセンタ間などで送受信され、電子署名の手続や復号手続(電子署名の確認手続)は後述する。
【００２４】
センタ６の構成を示すと、１８は情報通信処理装置で、パーソナルコンピュータやサーバなどを用い、センタ６の資源を提供し、電子署名プログラム記憶部２０はセンタに必要な電子署名プログラムを記憶し、２２は鍵記憶部で、秘密鍵φ(ｎ)，Γeなどの他に、公開鍵Ｓ，ｎ，Γ-1などを記憶する。秘密通信部２４は、秘密鍵Γeや公開鍵Γ-1などを算出するために、エンティティー１０の鍵選択に関する情報を秘密通信により受信するためのものである。なお秘密通信は、通信しているデータを第３者に秘密にすることを意味する。復号認証部２６は、エンティティーが電子署名したメッセージに対して、閾値以上のエンティティーが署名に参加したものかどうかを確認する。秘密分散処理部２８は、後述の中国人の剰余定理などを用いた秘密分散法により、所定数以上の小グループで電子署名が有効に行われたかどうかを判別する。
【００２５】
エンティティー１０の構成を説明すると、情報通信処理装置３０はエンティティー１０の資源を提供し、パーソナルコンピュータや携帯情報端末、携帯電話などで構成する。電子署名プログラム記憶部３２は、エンティティーに必要な電子署名プログラムを記憶し、秘密通信部３４は鍵の選択に関する情報をセンタ６などへ秘密送信する。電子署名部３６は、メッセージに電子署名用の秘密鍵を用いて電子署名し、最初に電子署名するエンティティーはこれ以外に、メッセージに対して公開鍵Γ-1によるべき乗演算を行う。復号認証部３８は、例えば複数のエンティティー１０間で協力することにより、電子署名に参加したエンティティーの鍵と、電子署名に参加しなかったエンティティーの鍵の推定値とを用いて、所定の制約下に、例えば所定の試行回数以下で、暗号化されたメッセージを復号化できるかどうかをトライする。鍵記憶部４０は、自己の秘密鍵や、必要に応じて公開鍵などを記憶する。
【００２６】
センタ６での電子署名プログラム記憶部２０は、センタに必要なプログラムを記憶すれば良く、その主な命令は公開鍵をエンティティーに送信し、エンティティーから鍵選択に関する情報を受信して、秘密鍵Γeや公開鍵Γ-1などを算出することである。図１では、エンティティー１０とセンタ６の双方に復号認証部２６，３８を設けているが、これらはセンタあるいはエンティティーの一方に設ければ良く、暗号化されたメッセージの復号をセンタ側で行う場合、所定の試行回数内で、電子署名に参加しなかったエンティティーの鍵の積を推定して復号できるかどうかを試みる。また復号をセンタ側で行う場合、電子署名プログラム記憶部に復号のための命令を記憶する。またエンティティー側で復号を行う場合、エンティティーの電子署名プログラム記憶部に、復号のための命令を記憶する。秘密分散処理部２８は特に設けなくても良く、さらに同様の構成の閾値電子署名システム３が、閾値電子署名システム２とは別個に存在するものとして、閾値電子署名システム２で電子署名したメッセージを、閾値電子署名システム３で受信して復号するようにしても良い。
【００２７】
実施例での記載は、電子署名方法やそのためのプログラム、並びに電子署名装置にもそのまま適用し得るものとする。電子署名とその確認とに関する実施例の記載は、電子署名方法のみならず、それに対応した命令が電子署名プログラムにも存在するものとし、またこのような処理を行うための手段が、電子署名装置にも存在するものとする。さらに実施例において、エンティティー間の結託は無視できるものとする。
【００２８】
グループとセンタとの間で対話的なやりとりを行うことによって、必要な鍵を生成する（図２参照）。なおセンタはグループ内のエンティティーの代表によって構成されても良いが、ここでは簡単のためグループとセンタを分離して考える。グループは、数ＮのエンティティーＭ1，Ｍ2，…，ＭNによって構成されている。センタは整数環Ｚ／ｎＺ上の２組のペアから成る集合Ｓ：
Ｓ＝｛(αh(0)，βh(0)),(αh(1)，βh(1))｝：ｈ＝１，２，…，Ｊ            (1)
を公開する。但し、ｎは大きな素数ｐ及びｑの合成数ｎ＝ｐｑである。なお、集合Ｓにおける２組のペア(αh(0)，βh(0)),(αh(1)，βh(1))をｈ番目のクラスと呼ぶ。また、クラスの番号ｈ及びペアの何れであるかが特に問題でない場合には、ペアの第１成分及び第２成分をそれぞれ簡単のため、第１成分α、第２成分βというように呼ぶことにする。
【００２９】
集合Ｓにおける任意のクラスのペア(αh(0)，βh(0)),(αh(1)，βh(1))においては以下の関係が成立するとする。
αh(0)βh(0)≡ｔh(0)modφ(ｎ)                                          (2)
αh(0)βh(1)≡ｔh(1)modφ(ｎ)                                          (3)
ｈ＝１，２，…，Ｊ
但し、φ(ｎ)はｎのオイラーの関数であり、ｔh(0)及びｔh(1)と共にセンタの秘密である。なお剰余成分ｔh(0)，ｔh(1)についてもα，βと同様、特にクラス番号等が問題でない場合には単に剰余成分ｔと呼ぶことにする。
【００３０】
エンティティーにおける鍵生成
グループＧに属するエンティティーＭ1は最初のクラスに属する２組のペア(α1(0)，β1(0)),(α1(1)，β1(1))のうち、何れか１つをランダムに選ぶ。そしてエンティティーＭ1は残り第２〜第Ｊの全てのクラスについても第１あるいは第２成分のペア何れかをランダムに選ぶ。エンティティーＭiが第ｈ番目のクラスにおいて選んだペアを一般に(αhi，βhi)と表記する。
【００３１】
以上の選択に基づいてエンティティーＭ1の秘密の暗号化鍵Ｅ1を
Ｅi＝Παhi(ｈ＝１〜Ｊ)                                            (4)
として与える。一方Ｅiに対応する秘密の復号鍵はペアの第２成分βの積として以下のように与えられる。Ｅi，Ｄiでの乗算の法はオイラー関数φ(ｎ)である。
Ｄi＝Πβhi(ｈ＝１〜Ｊ)                                            (5)
【００３２】
なお、上記式(2)及び(3)を満たす基本方式においては、暗号化鍵は秘密に保たれる。しかし、式(2)及び(3)を一般化して同一のα成分に対し、複数の剰余成分ｔを与えた場合には、暗号化鍵をグループを構成する他のエンティティーやセンタに安全に公開することができる。なおこのことについては後述する。
【００３３】
各エンティティーはそれぞれが選んだ第ｈ番目のクラスに属するペアの第１成分αを互いに秘密にしたまま、例えばのエンティティーと協力してαの積Ｐα(ｈ)，即ち
Ｐα(ｈ)＝Παhi(ｉ＝１〜Ｎ)                                      (6)
を構成し、ここで乗算の法はオイラー関数φ(ｎ)である。Ｐα(ｈ)を以下の逐次暗号化法に従い秘密裏にセンタに送る。
【００３４】
ここでは、グループＧのエンティティーが適切に定められた順番に従って逐次的に暗号化し、全エンティティのα成分の積をセンタに秘密裏に送信する方法について考える。グループＧのエンティティーＭiの秘密鍵(α成分)をαiとする。ここでセンタの逐次暗号化用の公開鍵を大きな素数ｐ，体Ｆpの生成元をｇとし、グループＧのエンティティーは以下に述べる逐次的な暗号化法(アルゴリズムＩ)に基づいて、秘密鍵成分であるα成分の積を以下の順序で構成する。
Ｍ1→Ｍ2→…→ＭN→Ｍ1→Ｍ2→…→ＭN→センタ                    (7)
積α1α2…αNは、Ａ1，Ａ2，…，ＡJ及びａ1，ａ2，…，ａJを適当な整数としてＡ1a1，Ａ2a2，…，ＡJaJという形であって、Ｊ＜＜Ｎが一般に成立する。但し、ａ1＋ａ2＋…＋ａJ＝Ｎである。従ってエンティティーＭiの秘密αiは必ずしも十分に正確に知ることはできない。
【００３５】
アルゴリズムＩ
ステップ１：エンティティーＭiは乱数ｒ1を生成し、
ｇr1α1≡Ｇ1modｐ                                                  (8)
を計算し、エンティティーＭ2に送る。Ｍ2は同様に乱数ｒ2を生成し、
Ｇ1r2α2≡Ｇ2 modｐ                                                (9)
を導く。以下、式(7)に示した順に暗号化を行う。
ステップ２：エンティティーＭNはＮ個のエンティティーの協力で導いた以下のＧN、即ち、
ｇr1r2…rNα1α2…αN≡ＧN modｐ                                    (10)
を再びＭ1に送る。
ステップ３：エンティティーＭ1は
ＧN-r1≡Ｇ1'modｐ                                                (11)
を計算し、エンティティーＭ2に送る。Ｍ2は
Ｇ1'-r2≡Ｇ2'modｐ                                              (12)
を導く。以下の式(7)の後半に示した順に従って暗号化を行う。
ステップ４：エンティティーＭNはＮ個のエンティティーによって導いた以下のＧN'、即ち
ｇα1α2…αN≡ＧN' modｐ                                            (13)
をセンタに送る。センタは、総当たりの手法によってα1α2…αNの値を導き、秘密裏に保有する。
【００３６】
Ｐα(ｈ)の実現値を知るのはセンタのみである。エンティティーが非常に偏った選択、即ち全てが偶然に同じ第１成分を選ぶといったことをしない限り、センタは各エンティティーの選択情報を充分正確に知ることはできない。グループＧの全エンティティーは、以上のことを全てのクラスｈ＝１，２，…，Ｊについて実行し、Ｐα(1)，Ｐα(2)，…，Ｐα(J)を構成する。そしてこれらの全てを秘密裏にセンタに送る。センタは受信したＰα(1)，Ｐα(2)，…，Ｐα(J)に基づいて、これらの積Γe、即ち
Γe＝ПＰα(ｈ)  ：  ｈ＝１〜Ｊ                                (14)
を導く。ここでセンタは選択された第１成分αに対応して定まる第２成分βの全てに渡る積  Γも、式(7)と全く同様にして同時に導いておく。そしてΓ＝ΓE・Γdとし、Γ-1を公開する。Γe，Γd，Γを求めるための乗算の法はφ(ｎ)で，Γ-1は法φ(ｎ)に関するΓの逆数である。
【００３７】
表１
基本的な記号
ｎ        整数環Ｚ／Ｚｎを構成するための整数：公開鍵：｜ｎ｜＝１０００ビット程度
ｐ，ｑ  ｐｑ＝ｎ  となる秘密の素数：センタの秘密
φ(ｎ)  オイラーの関数    φ(ｎ)＝(ｐ−１)(ｑ−１)
ｍ      メッセージ
Ｓ        暗号化鍵と復号鍵の生成に用いるデータの集合
Ｓ＝｛(αｈ(０)，βｈ(０))，(αｈ(１)，βｈ(１))｝：h＝１〜Ｊで、
(αｈ(０)，βｈ(０))等をペア、
２組のペア(αｈ(０)，βｈ(０))，(αｈ(１)，βｈ(１))をクラスという
αｈ(０)，βｈ(０)等は各１０００ビット程度のデータ
クラスの数Ｊはエンティティー毎の鍵選択の自由度に対応し、
Ｊを大きくすると閾値が明確になる
ペアの第１成分αｈ０等と第２成分βｈ０等の積をｔh(０)or(１)とする
αｈ(０)βｈ(０)≡ｔh(０)  modφ(ｎ)    
αｈ(１)βｈ(１)≡ｔh(１)  modφ(ｎ)    
Ｅi        Ｅi＝Παhi    h＝１〜Ｊ    エンティティーｉの暗号化(署名用)鍵
Ｄi        Ｄi＝Παhi    h＝１〜Ｊ    エンティティーｉの復号(認証用)鍵
Γe        Γe＝ΠＥi    i＝１〜Ｎ
Γd        Γd＝ΠＤi    i＝１〜Ｎ
Γ         Γ＝Γe・Γd      Γ・Γ−１≡１
【００３８】
表２
エンティティー関係の記号
Ｎ          エンティティーの数
Ｋ          署名に賛同したエンティティーの数
Ｆ          署名に加わらなかったエンティティーの数
添字        識別対象            代表的な使い方
i          エンティティー        i＝１〜Ｎ
h          クラス                h＝１〜Ｊ
【００３９】
暗号法に必要な鍵情報は以下のようにまとめられる。
【００４０】
表３
センタ        
秘密鍵      φ(ｎ)，Γe
公開鍵      Ｓ，ｎ，Γ-1
【００４１】
センタの公開鍵Ｓのペアの第１成分α、第２成分β及び法ｎのサイズをそれぞれ｜α｜,｜β｜,｜ｎ｜と表記する。これらの値は｜α｜＝｜β｜＝｜ｎ｜＝１０００ビット程度とすることが考えられる。Ｊの値は５０程度であるので、公開鍵サイズは高々２００Ｋビット程度と比較的小さな値に設定することが可能である。ペアＳを公開しても必ずしも安全性は損なわれない。しかしエンティティー内だけで公開する方がより好ましい。
【００４２】
署名法
グループＧの全構成エンティティー数Ｎに対し、ある適切な閾値Ｋを設定する。Ｋ以上のエンティティーがメッセージｍの暗号化に同意した場合、以下のアルゴリズム２を実行する。なお同意したエンティティーを一般性を失うことなく、Ｍ1，Ｍ2，…，ＭKと表記する。また暗号化の順序も同様に一般性を失うことなく、
Ｍ1→Ｍ2→…→ＭK      
の順に行うものとする。なお、以下のアルゴリズムＩにおいては暗号化は前記の逐次暗号化法に従うものとするが、記述が煩雑になることを避けるため、逐次暗号化のプロセスを省略して述べる。エンティティーＭ1が選んだ第１成分と第２成分の籍αhβhのＪ個のクラスに渡る積  Пαhβh  ｋ＝１〜Ｊ  をＴiとする。また、Ｔiの推定値をＴi'とする。
【００４３】
アルゴリズム２
ステップ１：グループＧのＫ個の署名に賛同するエンティティーＭ1，Ｍ2，…、ＭKは
ｍΓ-１≡Ｃ0 modｎ                                                    (15)
を導く。
ステップ２：メッセージｍに対し、エンティティーＭ1は
Ｃ0E1≡Ｃ1  modｎ                                                  (16)
を計算し、エンティティーＭ2に送る。Ｍ2は
Ｃ1E2≡Ｃ2  modｎ                                                  (17)
を導く。以下Ｍ1→Ｍ2→…→ＭKの順に暗号化を行う。
ステップ３：Ｋ個のエンティティーによってグループ暗号化したメッセージ
Ｃ0E1E2…EK≡ＣK  modｎ                                               (18)
を導く。電子署名の手続を図３に示す。
ステップ４：グループＧのＫ個のエンティティーは、復号用鍵として
Ｄ1Ｄ2…ＤKＴK+1'…ＴN'                                         (19)
を推定する。ここでＤ1Ｄ2…ＤKは署名の参加者から得ることができる情報で、ＴK+1'…  ＴN'はＴK+1…ＴNの推定値である。
【００４４】
但し、  Ｔi≡Ｅi・Ｄi  modφ(ｎ)  であって、Ｔi'はその推定値である。なお、この推定が正しく行われたことは式(18)の右辺を総当たり的に、Ｄ1Ｄ2…ＤKＴK+1'…ＴN'乗したとき、メッセージｍが復号されることによって知ることができる。即ち、積ＴK+1'ＴK+2'…ＴN'が正しく推定された時
(ｍE1E2…ENΓ-1 )D1D2…DN   ≡ｍ modｎ                              (20)
の関係が成立している。Γ-1ＴK+1ＴK+2…ＴNをΓ'-1とおく。復号アルゴリズムを図４に示す。
【００４５】
以上のアルゴリズムを実行して導いたｍE1E2…EKΓ-1を公開する。このメッセージを復号することが可能なのは、メッセージｍの暗号化に加わったＫ個のエンティティーであり、復号用鍵は公開鍵の積Ｄ1Ｄ2…ＤKで与えられる。クラス数がＪであることによって推定すべき復号用の鍵の積の総数ＮDは、Ｎ−Ｋ＝Ｆとして
ＮD＝(Ｆ＋１)J                                                        (21)
で与えられることが明らかである。例えばＮD＜１０15のとき、この例では計算量的に復号鍵が推定可能であるという。なお、ＮD＝１０15とＮD＝９×１０14との差は僅かであり、現実的に計算量に差はない。しかし、ここでは議論を煩雑化させないために、１０15を推定可能か否かを決める閾値と定める。
【００４６】
エンティティの暗号化鍵を固定しない暗号化法(変形例)
基本方式においては、第１成分αを暗号化用に、そして第２成分βを復号用として用いている。しかしながら、注意すべきことは、各エンティティーは一度ペアを選ぶと、このペアを固定しなければならないものの、ペアの第１成分αあるいは第２成分βは署名毎にランダムに変更することができることである。即ち暗号化鍵も復号鍵も固定する必要はなく、各エンティティーはその何れかをランダムに選択することができる。そして、この暗号化鍵を自由に選択できるという特徴によって、グループＧが電子署名したメッセージをセンタが復号し得るという問題を解決することができる。
【００４７】
この修正方式においては、第１成分α、第２成分βのいずれを選んでも、ｉ成分には影響を及ぼさない。このためグループＧのエンティティーは毎回暗号化鍵復号化鍵をランダムに変更することが可能となり、センタが電子署名されたメッセージを復号するという問題をうまく防ぐことができる。
【００４８】
暗号システムの設計に直接深く関わったセンタはφ(ｎ)を知っているので、ｕ、ｖを適当な整数として、
ｍu  ≡Ｃ0  modｎ
ｕｖ≡１ modｖ(ｎ)
を満たすメッセージをグループの電子署名メッセージとし、かつｖが復号用鍵であると主張することができる。センタがｖ(ｎ)を知っている以上、このことを防ぐことは困難である。この問題はセンタを複数個置くことによって解決し得るが、実施例においてはセンタの複数化にもかかわらず公開鍵Ｓ等を共有できるので、センタの増加は必ずしも大きな問題とはならない。センタの複数化による安全性の向上については後述する。
【００４９】
数値例
グループ構成エンティティー数Ｎ＝１０，閾値Ｋ＝８，Ｊ＝３１の場合：
推定すべき  Ｎ−Ｋ＝Ｆ＝２  の復号用の積の可能な値の総数ＮDはＮD＝３31＝６.１８×１０14であり、復号鍵が推定可能である。一方、署名に賛同するエンティティーの数がＫ＝８に満たない値Ｋ'＝７である場合、残る３エンティティーの復号用鍵の積の推定値の総数ＮDはＮD＝４.６２×１０18となる。このことにより閾値に満たないエンティティーの場合、残るエンティティーの復号鍵の推定が不可能となり、閾値電子署名が成立しないことが分かる。
【００５０】
この具体例によって明らかなように、グループ構成エンティティー数Ｎと閾値Ｋとの差Ｆ＝Ｎ−Ｋが小さくなるほど閾値未満の場合に必要となる計算量との差を大きくすることができ、閾値を鋭くすることができる。しかし、差Ｆが逆に大きくなると、計算量の差が小さくなり、閾値が緩やかになる。以下ではこの問題を解決した閾値電子証明について述べる。
【実施例２】
【００５１】
前記の実施例では、各クラスに２組のペアを考えたが、ここではこれをより一般化して２のべき乗、即ち２a組のペアを考える。しかし議論を徒に煩雑化させることを避けるため、図５に示すように、各クラスにおいては次式を満たす４組のペア(α，β)が存在するとする。
αh(0)βh(0)≡ｔh(0)modφ(ｎ)
αh(0)βh(1)≡ｔh(1)modφ(ｎ)
αh(1)βh(2)≡ｔh(2)modφ(ｎ)
αh(1)βh(3)≡ｔh(3)modφ(ｎ)                              (30)
【００５２】
式(30)に示したように４組のペアを考えると、あるエンティティーＭ1がクラスｈにおいて例えばαh(0)を選んだことが既知になったとしても剰余成分がｔh(0)あるいはｔh(1)のいずれであるかは確率１／２でしか決定し得ないことが明らかである。このことは任意のエンティティーがＪ個のクラスにおいて選んだα成分の積(情報量はＪビットで与えられる)を全て公開しても、復号鍵については依然としてＪビットの曖昧さが残されていることを意味する。以下の定理が成立する。
【００５３】
定理１  グループのエンティティーＮ中Ｋ個のエンティティーが署名に参加し、残る
Ｆ＝Ｎ−Ｋ  剰余成分ｔの積を推定するとする。剰余成分ｔの値を適切に設定し、クラス数をＪとすると、推定すべき相異なる積の総数ＮFは
ＮF＝(4ＨF)J＝(3+F Ｃ3)J                                              (31)
で与えられる。
【００５４】
この実施例では、以上のことを利用した閾値電子署名方式について述べる。暗号システムの構成を図６に示す。ここでは煩雑さを避けるため、一般性を失うことなく両グループの構成エンティティー数は同一のＮであるとする。図６において、グループＡよりＢに対して閾値電子署名されたデータが送信されるものとする。但し、ここでは法ｎA及びｎBの大小関係による問題は問わないものとする。なお各グループで用いるΓA-1，ｎA，ｐA，ｑA等は最初の実施例で定義したΓ-1，ｎ，ｐ，ｑにグループ名を添え字として付けたものである。グループ間における閾値電子署名のアルゴリズムを以下に与える。
【００５５】
アルゴリズム３
ステップ１：グループＡにおいて、Ｎ中Ｋ個のエンティティーがメッセージｍに対し電子署名することに賛同したとする。Ｋ個のエンティティーはメッセージｍに対し、
Ｃ0≡ｍΓＡ-1  modｎA                                                    (32)
とした上で、
Ｃ0ＤA１…ＤAＫ Ｄ'AＫ+1…Ｄ'AＮ  modｎA                      (33)
というように署名する。但し、Ｄ'AK+1 Ｄ'AK+2…Ｄ'ANは署名に参加しないエンティティーの復号鍵の積ＤAK+1 ＤAK+2…ＤANの推定値である。この推定値が正しいことは、
Ｃ0(ＥA１…ＥAＮ ＤA１…ＤAＫ)Ｄ'AＫ+1…Ｄ'AＮ  ≡  ｍ modｎA  (34)
によって確かめることができる。
ステップ２：  電子署名は以下のように実施される。
(Ｃ0 ＤA１…ＤAＫ ＤAＫ+1 ＤAＮ  modｎA)ＥB１ ＥB２…ＥBＮ  ≡ＣA→B modｎB
(35)
【００５６】
ステップ３：  グループＢのＫ個のエンティティーが同意した場合、残りＮ−Ｋ個の復号用鍵の積を推定し、
Ｃ'A→B ≡ＣA→BΓB-1  modｎB                                          (36)
とした上で
Ｃ'A→BＤB１ ＤB２ ＤBＮ    modｎB                            (37)
を導き、さらにこれをグループＡの公開鍵を指数部に乗じることにより
(Ｃ'A→BＤB１ ＤB２ ＤBＮ    modｎB)ＥA１ ＥA２ ＥAＮ  ≡  ｍ modｎA      (38)
を導く。
【００５７】
以上によってグループＢのＮ中Ｋ個のエンティティーは署名が確かにグループＡの閾値電子署名文であることを知ることができる。
【実施例３】
【００５８】
実施例２で述べた手法においては、鍵生成に関与したセンタは、当然なことではあるが、当該グループの閾値電子署名文を作成することができる。しかしながら、この問題はセンタの複数化によって、比較的容易かつ有効に防ぐことが可能である。
【００５９】
一般にセンタはＨ≧２個設置することができるが、ここでは説明の煩雑化を避けるため、Ｈ＝２とし、各グループに２つのセンタの存在を仮定し、かつこれらのセンタは結託しないものとする。ここで第１のセンタの公開鍵についての表記は前記と同様ｎ，Γ等とし、他方のセンタに関する公開鍵等はｎ'，Γ'等と表記する。図７に、実施例３のグループ間暗号システムを示す。２つのグループＡ及びＢにはそれぞれ２つのセンタが存在するとし、これら４つのセンタは互いに結託しないものとする。以下において、２つのセンタを有するグループ間の閾値電子署名法の概要を示す。
【００６０】
グループＡのＫ個のエンティティーがメッセージｍに対し、閾値電子署名をすることに賛同したとする。グループＡのＫ個のエンティティーは
((ｍΓA-1)ＤA1…ＤAN modｎA)ΓA-1ＤA1'…ＤAN'≡ＣD modｎA'  (40)
を導く。そして閾値電子署名文を
((ＣDＥB1…ＥBN  modｎB)ＥB1'…ＥBN'≡ＣA→B modｎB'            (41)
を作成する。
【００６１】
グループＢのＫ個のエンティティーが電子署名されたメッセージＣA→Bを復号し、グループＡからのメッセージであることを確認する。この方式においては複数個のセンタが結託に関与しない限り、当該グループの電子署名されたメッセージを偽造できない。即ち、グループＡのセンタの１つは当然のことながらｐA，ｑAを知っているので、公開されたＥA1，…，ＥANより復号用の鍵    ПＤAi  ：ｉ＝１〜Ｎ  を容易に算出することができる。しかし他のセンタが作成した公開鍵に関わる秘密鍵ｐA'，ｑA'は未知であるために、復号鍵    ПＤAi'：ｉ＝１〜Ｎ      を算出できない。以上により、センタ間で結託がない限り、グループＡの閾値電子署名済みメッセージを偽造することは極めて困難である。以下に式(30)で与えられる４組のペアを用いた場合について、具体例を示す。
【００６２】
具体例２
グループの構成エンティティー数Ｎ＝１０，閾値Ｋ＝８，Ｊ＝１４の場合：
任意のエンティティーＭ1が選んだ公開鍵は、それぞれのクラスにおいて１ビットであるから、エンティティーＭ1のトータルの公開鍵サイズは２８ビットで与えられる。従ってエンティティーの公開鍵はグループ全体としては２８０ビットとなる。一方、公開鍵Γ-1，Γ'-1，ｎ，ｎ'のサイズの総計は、それぞれ１Ｋビットとして、４Ｋビットで与えられるので、２つのセンタの公開鍵を合わせると８Ｋビットとなる。これに対し、４組のペアから成るクラスの集合Ｓのサイズは｜Ｓ｜＝１１２Ｋビットである。
【００６３】
具体例３
グループの構成エンティティー数Ｎ＝１００，閾値Ｋ＝９０，Ｊ＝６の場合：
クラスを構成するエンティティーの公開鍵はトータルで１.２Ｋビットと非常に少ない。一方、集合Ｓのサイズは、｜Ｓ｜＝４８Ｋビットで与えられる。構成エンティティー総数が１００名であるにもかかわらず、公開鍵のサイズが全てを合わせて５３.２Ｋビットに過ぎないことは注目に値する。
【００６４】
前記２つの具体例が示すように、集合Ｓのサイズ｜Ｓ｜が公開鍵のトータルサイズの主要部分を示すが、このサイズはセンタの複数化にかかわらず不変である。このため、センタが１つ増えることに伴う公開鍵の増加は僅か２Ｋビット程度増えるに過ぎない。従って極端な場合、全エンティティーがセンタとなって公開鍵を公開するといった興味深い方式が現実的となる。
【実施例４】
【００６５】
中国人の剰余定理を利用した電子署名法
以上で述べた方法においては、Ｎの値が大きくなると一般にＦの値も大きくなり、不可避的にＪの値を小さくしなければならない。このため閾値以下の数のエンティティーに対して、復号鍵推定のために必要となる計算量に大きな差を与えることが困難であった。ここでは、このことを改善するために中国人の剰余定理を利用することによって、実施例３の閾値電子署名法を修正することを試みる。
【００６６】
グループ署名すべきメッセージｍを拡大体Ｆ2μ上のｇ次元ベクトルｍで次のように表現する。  
ｍ＝(ｍ1，ｍ2，…，ｍg)，ｍi  ∈Ｆ2μ                            (50)
さらにメッセージｍの多項式表現を
ｍ(Ｘ)＝ｍ1＋ｍ2Ｘ＋…＋ｍgＸg-1，ｍi∈Ｆ2μ                      (51)
とする。
【００６７】
Ｎ＞＞１として、総エンティティー数Ｎを充分小さなエンティティー数ｎsの小グループＧ1，Ｇ2，…，ＧηSに分割する。但し、
ηS＝Ｎ／ｎS                                                    (52)
である。なお、小グループは統一して、グループ全体として与えられているペアクラスの集合Ｓ及び法ｎ等を使用するものとし、エンティティー個々の暗号化、復号用鍵等もセンタを通して構成されるものとする。小グループ毎に独立に法ｎ，集合Ｓを選ぶことも考える。この場合、不正をするグループが一定割合で含まれることを想定して、より安全なシステムを設計することができる。
【００６８】
図８，９に示したように、２つのグループＡとＢの間で閾値電子署名を実行する。なお、グループＡの任意の小グループは、予めランダムに定められている送信先、Ｂの小グループに分割されたメッセージを送るものとする。グループＡからグループＢに署名文を送るとする。ここでは以下の条件が成立するものとする。
(1)  グループＡに属するηS組の小グループの内、ηSｋAの小グループが署名に賛同する。
(2)  署名文を受信したグループＢのηSｋA組の小グループのうち、ηSｋB組の小グループが電子署名の復号に同意する。
(3)  以上において、ηSｋB≦ηSｋAであるが、さらにηSｋB≧ｇが成立する。
実施例４の閾値電子署名法は、以下のように与えられる。
【００６９】
アルゴリズム  ４
ステップ１：センタはηS個のエンティティーより成る小グループＡiにｍ(αi)を与える。
ステップ２：グループＡiの閾値以上のエンティティーが署名に賛同した時、分割メッセージｍ(αi)に対し、実施例の閾値署名法に従って署名する。
ステップ３：  グループＡより(ηSｋA個の)署名文を受信したグループＢのηSｋA組の小グループの内、ηSｋB組のグループが署名文の復号に賛同したとする。これらの小グループはそれぞれの署名文を実施例の閾値署名法に従って復号する。
ステップ４：グループＢは復号したηSｋB個の署名文に対し、中国人の剰余定理を用いて、メッセージｍを復号する。
【００７０】
上記において、以下の自明な定理が成立する。
定理２
ｍ(Ｘ)をＸ−αiで割った余りはｍ(αi)で与えられる。但し、αi∈Ｆ2μである。
定理３
また任意に選ばれたηSｋB個の多項式｛(Ｘ−αi)｝が互いに素であるとき、メッセージｍは一意に復号可能である。但し、ηSｋB≧ｇが成立しているとする。
【００７１】
以上のように述べた閾値電子署名法において、例えばＮ＝１０6，ｎS＝１０とすると、小ブロック数ηSは１０5となる。この１０5組の小グループの内、６５０００組が署名に賛同した時に、署名が復号可能であるように閾値を設定したい場合には単にｇ＝６５０００とすればよい。この場合、署名復号に賛同した小グループが６４９９９組以下であると、署名の復号が不可能になることが明らかである。
【００７２】
閾値電子署名を体Ｆ2m上で考えているとして、ある１つの小グループ(これをＧiとする)にｍ(αi)が与えられているとする。ｍ(αi)の値は２m通りに仮定するとそのうちの１つは正しい値となっている。このため、ｍの値は比較的大きく，例えば｜ｍ｜＝８０ビット程度にしなければならない。このようにｍのサイズが比較的大きい場合は、実施例２の閾値電子署名法に比べ閾値は実用上厳密な意味での閾値を与えることとなる。
【００７３】
上記ではグループ単位での閾値は厳密に与えられていることを述べたが、グループの構成エンティティー数に関して厳密な閾値を設定することは依然として困難なことである。しかし実施例２に比べると閾値は遙かに急峻なものとなる。このことを以下に具体例で考える。
【００７４】
具体例４
１００万のエンティティーの８０％即ち８０万が署名に賛同した場合に、充分高い確率で署名文が復号可能であるようにするためには、詳細については比較的自明であるため割愛するが、ｇ＝６５０００とすればよい。一方８０万に満たない７８万が署名に賛同した場合、同様に詳細については割愛するが、６５０００以上の小ブロックで署名の復号が実行される確率は非常に小さくなる。このように実施例４では署名賛同者が８０万である場合と７８万である場合との間に、大きな較差を与えることが可能である。
【００７５】
因にエンティティー数が我が国の総人口数に匹敵する１億人程度になる場合と、十分な較差を生ずるエンティティー数の幅が相対的にさらに小さくなることは容易に予想される。
【実施例５】
【００７６】
前章までに述べた方法は、べき乗剰余演算によって逐次暗号化処理等が行われているために、並列処理等による高速化の実現が必ずしも容易ではない。ここでは並列処理が容易となる加算演算に基づいて構成する方式について述べるが、基本的な原理は前章までの手法とほぼ同様である。なおセンタの公開鍵は、ｎ，秘密鍵は大きな素数ｐ及びｑとφ(ｎ)である。以下において並列処理容易な閾値電子署名法をアルゴリズムの形で与える。
【００７７】
アルゴリズム５
ステップ１：グループＧのエンティティーは前記の逐次暗号化法に示した手法と全く同様の原理に従って、それぞれがランダムに生成した秘密鍵の集合｛ＳEi｝の元の和：
ＳEI＋SE2＋…＋ＳEN＝ＳE                                              (60)
をセンタに送る。但し、｛ＳEi｝はエンティティーＭiが生成した乱数である。もちろん、ＥＰＯＣ暗号等を利用しても良いが、実用上は前記の逐次暗号化法に基づく手法によって十分な安全性を実現することが可能である。またセンタが総当たりによって計算可能となるようエンティティーＭiはＳEiを分割して送ることが一般には考えられる。
ステップ２：  エンティティーはグループ及びセンタに公開されているランダムなペアの集合｛(Ａh，Ｂh)｝，ｈ＝１，２，…，Ｊに属する全てのペアについて、第１成分または第２成分の何れかを(ペア毎にランダムに)選択する。エンティティーＭiの選択したＪ個の成分の和をＳDiとして、互いに秘匿する鍵集合｛ＳDi｝を導く。
ステップ３：グループＧの全エンティティーは協力してステップ１と全く同様の手法に従って
ＳD1＋ＳD2＋…＋ＳDN＝ＳD                                      (61)
をセンタに秘密裏に送る
ステップ４：  センタは
ＳE・ＳD≡Γs modφ(ｎ)                                        (62)
を計算し、ΓSの逆元ΓS-1を公開する。
【００７８】
以上のアルゴリズムに基づいて構成した閾値電子署名のアルゴリズムを以下に与える。但し、以下では２つのグループをそれぞれＡ，Ｂとし、ｎ，ＳE，ＳD，ΓS-1はグループＡについてはｎA，ＳE(A)，ＳD(A)，ΓS-1(A)とし、グループＢについてはｎB，ＳE(B)，ＳD(B)，ΓS-1(B)と表記する。
【００７９】
アルゴリズム６
ステップ１：  グループＡにおいて、Ｎ中Ｋ個のエンティティーがメッセージｍに対し電子署名することに賛同したとする。Ｋ個のエンティティーはメッセージｍに対し、
Ｃ0ＳD１(A)＋…＋ＳDＫ(A)＋S'DＫ+1(A)＋…＋S'DＮ(A)  modｎA  (63)
というように署名する。但し、Ｃ0≡ｍΓs-1(A)  であり、Ｓ'DＫ+1(A)＋…＋Ｓ'DＮ(A)は署名に参加しないエンティティーの復号鍵の積ＳDＫ+1(A)＋…ＳDＮ(A)の推定値である。この推定値が正しいことは、
Ｃ0(ＳD１(A)＋…＋ＳDＫ(A)＋S'DＫ+1(A)＋…＋S'DＮ(A))ＳE(A)  ≡ｍ modｎ (64)
によって確かめることができる。
ステップ２：  電子署名文を以下のように構成する。
ＣA→B≡(ｍＳD(A)'modｎA)ＳE(B)≡ＣA→B  modｎB                          (65)
【００８０】
ステップ３：  グループＢのＫ個のエンティティーが署名文ＣA→Bを復号することに同意すると、残りＮ−Ｋ個の復号用の鍵を推定し、
Ｃ'A→B ＳD(B)  modｎB                                              (66)
を導く。但し、Ｃ'A→B ≡ＣA→B Γs-1  modｎB  である。
ステップ４：  グループＡの公開鍵ＳE(A)を用いて
(Ｃ'A→BＳＤ(B)  modｎB)ＳE(A)≡  ｍ modｎA                            (67)
を導く。
【００８１】
以上により、グループＢのＮ中Ｋ個のエンティティーは電子署名されたメッセージが確かにグループＢのメッセージであることを知ることができる。本手法では指数部での加算を基本的な演算として用いているために、並列処理が容易になることが明らかである。
【００８２】
結論
実施例では、あるグループを構成するＮ個のエンティティーのうちＫ個が署名に賛同した場合に、グループとしての電子署名付きメッセージが構成可能となる手法を与えた。実施例は以下の右ような特徴を有する。
(1)  グループ内でＫ個のエンティティーが協力して構成した暗号文は当該暗号システムの設計に深く関わったセンタも(仮にＫ個のアイデンティティが明らかにされたとしても)これを復号することは困難である。
(2)  ２つのグループ間で閾値電子署名を実行する手法を与えたが、この手法においてはセンタを複数化することによって安全性を有効に高め得ることを示すととに、１つのセンタ増加に伴う公開鍵の増加は非常に低く押させることが可能である。因に１００エンティティーのグループで閾値が９０程度である場合、センタが１つ増加したことによる公開鍵サイズの全体としての増加は２Ｋビット程度と非常に小さな値に抑えることが可能で、従って全員が２Ｋビット程度の公開鍵を示すことにより、結託フリーな閾値電子署名を実現し得る。
【００８３】
(3)  中国人の剰余定理を応用することにより、閾値を鋭くすることが可能となる。
(4)  閾値電子署名を作成するために必要となる演算を指数部の加算を中心にすることによって暗号化、復号の並列処理による高速化が可能になる。そしてこのことによってグループ構成エンティティー数が非常に大である場合、閾値電子署名を実現することが容易であるようにしている。
【図面の簡単な説明】
【００８４】
【図１】実施例の閾値電子署名システムの構成を示す図
【図２】図１の実施例での、暗号化鍵や復号鍵等の生成メカニズムを示す図
【図３】図１の実施例での閾値電子署名手続を示す図
【図４】図１の実施例での復号手続を示す図
【図５】変形例でのクラスの構成を示す図
【図６】第２の実施例での閾値電子署名手続と認証手続とを示す図
【図７】第３の実施例での閾値電子署名手続と認証手続とを示す図
【図８】第４の実施例の特徴を示す図
【図９】第４の実施例での閾値電子署名と復号手続とを示す図
【符号の説明】
【００８５】
２，３      閾値電子署名システム
４          ネットワーク
６          センタ
１０        エンティティー
１２        電子署名プログラム
１４        公開鍵
１６        署名済みメッセージ
１８        情報通信処理装置
２０        電子署名プログラム記憶部
２２        鍵記憶部
２４        秘密通信部
２６        復号認証部
２８        秘密分散処理部
３０        情報通信処理装置
３２        電子署名プログラム記憶部
３４        秘密通信部
３６        電子署名部
３８        復号認証部
４０        鍵記憶部
【図１】
2005184134.tif 000003
【図２】
2005184134.tif 000004
【図３】
2005184134.tif 000005
【図４】
2005184134.tif 000006
【図５】
2005184134.tif 000007
【図６】
2005184134.tif 000008
【図７】
2005184134.tif 000009
【図８】
2005184134.tif 000010
【図９】
2005184134.tif 000011