JP3620138B2 - 鍵共有システム - Google Patents
鍵共有システム Download PDFInfo
- Publication number
- JP3620138B2 JP3620138B2 JP01854196A JP1854196A JP3620138B2 JP 3620138 B2 JP3620138 B2 JP 3620138B2 JP 01854196 A JP01854196 A JP 01854196A JP 1854196 A JP1854196 A JP 1854196A JP 3620138 B2 JP3620138 B2 JP 3620138B2
- Authority
- JP
- Japan
- Prior art keywords
- key information
- terminal
- distribution
- key
- distribution key
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Description
【０００１】
【発明の属する技術分野】
本発明は、センターおよび複数端末からなる通信システムにおいて暗号通信を行うシステムに関し、特にセンターから複数端末に共通の秘密鍵を安全に配送する装置に関する。さらにセンターからの通信量を削減してセンターが特定した端末以外のすべての端末で秘密鍵を共有する鍵共有装置に関するものである。
【０００２】
【従来の技術】
センターおよび複数端末からなる通信システムにおいて、センターの管理のもと複数の端末がグループを形成し、グループで同じ秘密鍵を共有して同報の暗号通信を行う場合を考える。グループの秘密鍵を用いて暗号化された情報は、同じ秘密鍵を保有するグループ内の端末だけが復号することができる。ところで、このグループから特定の端末を排除したい場合が生じうる。それは例えばグループ内のある端末が盗難され、その端末を用いた暗号通信の盗聴や偽情報の送信などの不正が考えられる場合などである。このとき、この秘密鍵を管理するセンターは、できるだけ速やかに、盗難された端末を排除して、残りの端末だけで新たな秘密鍵を共有することが必要となる。
【０００３】
（従来例１）
図１１はセンターが特定した端末以外で鍵データを共有するための、第１の従来例における鍵共有方法である。この図では５個の端末T1,…,T5がそれぞれ固有の固有鍵k1,…,k5を保持しており、センターCは全端末の固有鍵を管理している。例えばセンターが端末T1を排除して他のT2,…,T5で新しい共通の秘密鍵を配付するためには、まず、センターは秘密鍵Kを生成し、これをそれぞれk2,…,k5を鍵として暗号化し、それぞれT2,…,T5に配送する。各端末では固有鍵を用いてこれを復号し、秘密鍵Kを獲得する。なお、図中において例えばEk2(K)はKを固有鍵k2で暗号化した暗号文である。この通信路上のデータはそれぞれ端末T2〜T5の固有鍵で暗号化されているため、たとえ端末T1がこの通信データを盗聴したとしてもセンターが生成した分配鍵情報Kを獲得することができない。
【０００４】
しかし、この方法では一般にN個の端末から１つの端末を排除するためには、センターはN-1回の暗号化を行い、N-1個のデータを送信しなくてはならない。グループが大きくなると、この作業はセンターにとって非常に負担になる。また、全局更新まではグループ内の暗号通信等の業務を停止する必要があるが、N-1局に配り終えるまでの業務停止期間が長いと大きな問題である。
【０００５】
（従来例２）
図１２に第２の従来例における鍵共有方法について示す。この方法では、従来例１における端末をグループ化して、センター側の暗号化の手間と送信データ量の削減を行う。この図では５つの端末をT1,T2と残りの３端末の、２つのグループに分けて、それぞれで共通のグループ鍵G1,G2を共有している。そして例えばセンターが端末T1を排除する場合には、端末T2に対しては生成した分配鍵情報KをT2の固有鍵k2を用いて暗号化し、残りのT3,T4,T5に対してはグループ鍵G2を用いて分配鍵情報Kを暗号化して配送する。T3,T4,T5の各端末ではそれぞれグループ鍵G2を用いてこれを復号し分配鍵情報Kを獲得する。なお、端末のグループ化は多重や階層的に行うことも考えられる。
【０００６】
しかし、第２の従来例では各端末に固有の固有鍵に加えて、グループ鍵もセンター側および端末側で管理する必要がある。さらに、第２の従来例であっても第１の従来例と同様、端末の数が多くなるとセンターの暗号化、およびデータの送信の負担は大きくなり、また全局更新までの業務停止期間が長くなる。
【０００７】
【発明が解決しようとする課題】
例えば１０００個の端末から１個の端末を排除して、残りの９９９個の端末で新たな共通の秘密鍵を共有する場合を考える。このとき、第１の従来例では９９９回の暗号化の処理と９９９回の暗号文の送信を行う必要がある。また第２の従来例で例えば１０００個の端末を５００個づつの２つにグループに分けた場合には、排除すべき端末を含むグループでは各端末ごとに４９９回、もう１方のグループにはグループ鍵で一括で、合計５００回の暗号化の処理と暗号文の送信が必要である。いずれにしても、センター側にとってこれら作業は非常に負担なものとなる。また、全局更新までの業務停止期間が長くなる。
【０００８】
さらに、第２の従来例ではセンター側および端末側では、各端末の固有鍵とともに、グループ化の方法によっては多くのグループ鍵を管理する必要がある。
【０００９】
本発明はかかる点に鑑み、特定の端末だけを排除して、他の端末で分配鍵情報を共有する方法であって、次の点を特徴とする鍵共有方法を実現することを目的とする。
【００１０】
(1) センターから端末への通信量が少ない。
センターにおける暗号処理の手間が少なく、暗号文の送信量が少ない。
全局更新までの業務停止期間が短い。
【００１１】
(2) 端末の秘密鍵が少ない。
センターにおいて管理を行う端末の鍵が少ない。
端末において管理を行う鍵が少ない。
【００１２】
【課題を解決するための手段】
本発明の第１の構成における鍵共有システムは、センター側装置と相異なる分配鍵情報を持つ複数の端末からなり、センター側装置は全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、kを正整数とするとき、特定のk個の端末の分配鍵情報を同報で全端末に通知する通知部を備え、各端末は、分配鍵情報を格納する分配鍵情報格納部と、前記センター側装置から通知されたk個の分配鍵情報を受信する受信部と、前記受信部で受信したk個の分配鍵情報と、前記分配鍵情報格納部に格納される分配鍵情報の計k+1個の分配鍵情報がすべて相異なる場合にのみ、これらk+1個の分配鍵情報より前記特定のk個の端末を除く残りの端末で共通の秘密鍵を算出する秘密鍵算出部からなり、前記各端末の分配鍵情報は、前記秘密鍵算出部に入力されるk+1個の分配鍵情報がすべて相異なる場合にのみ前記秘密鍵が復元できるように予め定められ各端末に分配されたものであることを特徴とする。
【００１３】
本発明の第２の構成における鍵共有システムは、第１の構成における前記センター側装置が、全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、kとmをそれぞれ正整数とするとき、特定のm個の端末の分配鍵情報と任意のk-m個の予備分配鍵情報の合計k個の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする。
【００１４】
本発明の第３の構成における鍵共有システムは、第１の構成における前記センター側装置が、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、任意のk個の予備の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする。
【００１５】
本発明の第４の構成における鍵共有システムは、第１の構成における前記各端末は相異なる識別情報を保持し、前記センター側装置は全端末分配鍵情報格納部の代わりに、前記秘密鍵を保持する秘密鍵格納部と、前記秘密鍵と任意の端末の識別情報を入力として、対応する端末の分配鍵情報を算出する分配鍵情報算出部を備えていることを特徴とする。
【００１６】
本発明の第５の構成における鍵共有システムは、第２、３の構成における前記各端末は相異なる識別情報を保持し、前記センター側装置は前記予備分配鍵情報格納部の代わりに、前記秘密鍵を保持する秘密鍵格納部と、どの端末の識別情報とも異なる予備の情報と前記秘密鍵を入力として、前記予備の分配鍵情報を算出する予備分配鍵情報算出部を備えていることを特徴とする。
【００１７】
本発明の第６の構成における鍵共有システムは、センター側装置と相異なる分配鍵情報を持つ複数の端末からなり、センター側装置は全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、kを正整数とするとき、特定のk個の端末の分配鍵情報を同報で全端末に通知する通知部を備え、各端末は、分配鍵情報を格納する分配鍵情報格納部と、前記センター側装置から通知されたk個の分配鍵情報を受信する受信部と、前記受信部で受信したk個の分配鍵情報と、前記分配鍵情報格納部に格納される分配鍵情報の計k+1個の分配鍵情報がすべて相異なる場合にのみ、これらk+1個の分配鍵情報より前記特定のk個の端末を除く残りの端末で共通の第１の秘密鍵を算出する秘密鍵算出部と、前記第１の秘密鍵を全端末共通の変換方法で変換して第２の秘密鍵を求める変換部と、前記第２の秘密鍵から端末の新しい分配鍵情報を算出し、前記分配鍵情報格納部に格納して分配鍵情報を更新する分配鍵情報更新部からなり、前記各端末の更新前の分配鍵情報は、前記秘密鍵算出部において入力されるk+1個の分配鍵情報がすべて相異なる場合にのみ前記第１の秘密鍵が復元できるように予め定められ各端末に分配されたものであり、前記分配鍵情報更新部によって更新された各端末の分配鍵情報は、前記と同様前記第２の秘密鍵が復元できるように定めて各端末に分配されたものになり、前記各端末の変換部と分配鍵情報更新部は、外部より観察したり、変更できないものであり、前記センター側装置の全端末分配鍵情報格納部は、前記各端末で更新された分配鍵情報を格納することを特徴とする。
【００１８】
本発明の第７の構成における鍵共有システムは、第６の構成における前記変換部と分配鍵情報更新部を外部より観察したり、変更できない領域に備える代わりに、分配鍵情報更新部が、分配鍵情報を更新した後に前記第２の秘密鍵を消去することを特徴とする。
【００１９】
本発明の第８の構成における鍵共有システムは、第６の構成における前記センター側装置が、全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、kとmをそれぞれ正整数とするとき、特定のm個の端末の分配鍵情報と任意のk-m個の予備分配鍵情報の合計k個の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする。
【００２０】
本発明の第９の構成における鍵共有システムは、第６の構成における前記センター側装置が、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、任意のk個の予備の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする。
【００２１】
本発明の第１０の構成における鍵共有システムは、第６の構成における前記センター側装置は前記全端末分配鍵情報格納部の代わりに、前記第１の秘密鍵を保持する秘密鍵格納部と、前記第１の秘密鍵と任意の端末の識別情報を入力として、対応する端末の分配鍵情報を算出する分配鍵情報算出部と、前記第１の秘密鍵を各端末の変換部と同じ変換方法で変換して第２の秘密鍵を求め、前記秘密鍵格納部に格納して第１の秘密鍵を更新するセンター側変換部を備えることを特徴とする。
【００２２】
本発明の第１１の構成における鍵共有システムは、第８、９の構成における前記センター側装置は前記予備分配鍵情報格納部の代わりに、前記第１の秘密鍵を保持する秘密鍵格納部と、どの端末の識別情報とも異なる予備の情報と前記第１の秘密鍵を入力として、前記予備の分配鍵情報を算出する予備分配鍵情報算出部と、前記第１の秘密鍵を各端末の変換部と同じ変換方法で変換して第２の秘密鍵を求め、前記秘密鍵格納部に格納して第１の秘密鍵を更新するセンター側変換部を備えることを特徴とする。
【００２３】
本発明の第１２の構成における鍵共有システムは、第６〜１１の構成における前記各端末内の変換部およびセンター側変換部において、固定の変換の代わりに、外部から変更できる変換を用いることを特徴とする。
【００２４】
本発明の第１３の構成における鍵共有システムは、第６〜１１の構成における前記各端末内の分配鍵情報更新部で、前記第２の秘密鍵と前記端末の識別情報を用いて、前記端末の新しい分配鍵情報を算出することを特徴とする。
【００２５】
本発明の第１４の構成における鍵共有システムは、第６〜９の構成における前記各端末内の分配鍵情報更新部で、前記第２の秘密鍵と端末の更新前の分配鍵情報を用いて、前記端末の新しい分配鍵情報を算出することを特徴とする。
【００２６】
本発明の第１５の構成における鍵共有システムは、第１〜１４の構成における前記秘密鍵算出部において、入力のk+1個の分配鍵情報に誤りが生じえる場合や、k+1個より多い分配鍵情報が入力された場合に、その中で正しいk+1個の相異なる分配鍵情報を用いて秘密鍵を算出することを特徴とする。
【００２７】
本発明の第１６の構成における鍵共有システムは、第１〜１５の構成における前記秘密鍵にバージョン番号を付加し、センター側装置は各バージョンの予備の分配鍵情報を保管し、バージョンが一致していない端末に前記必要な分配鍵情報を通知することを特徴とする。
【００２８】
本発明の第１７の構成における鍵共有システムは、第６〜１４の構成における前記秘密鍵にバージョン番号を付加し、バージョンが一致していない端末に正しいバージョンの秘密鍵を個別に暗号化して通知することを特徴とする。
【００２９】
【発明の実施の形態】
本発明は、グループ内のある端末を排除して残りの端末で新しい秘密鍵を共有するという目的に、秘密分散法、または（k,n）しきい値法と呼ばれる公知の手法を、新たに適用したものである。秘密分散法や（k,n）しきい値法の説明は、例えば岡本栄司「暗号理論入門」共立出版（1993）の6.2節に詳しい。秘密分散法は秘密度の高い鍵の保管方法として従来より知られているものであり、例えば鍵を２つに分けて２人が保管し、使うときはその２人が集まらないと使えないといったものである。（k,n）しきい値法はこれを一般化し、秘密鍵をn個に分け（なお以下では秘密鍵を分けた結果のそれぞれを、分配鍵情報と称することにする）、n個の中から任意のk個を集めれば元の秘密鍵が復元でき、k個より少なければ元の情報が全く得られないものである。
【００３０】
この（k,n）しきい値法の多項式を用いた例を用いて、本発明の実施の形態を以下に示す。
【００３１】
（実施の形態１）
本発明ではセンターと複数の端末からなり、各端末は相異なる分配鍵情報を保持している。図１は実施の形態１における各端末の分配鍵情報を模式的に示した図である。この実施の形態では、pを素数、a,b,xを法pのもとでの剰余元とし、法p上の１次多項式f(x)=ax+b modpを考え、各端末の識別情報をx座標としたy座標値を各端末の分配鍵情報としている。例えばIDiを識別情報とする端末の分配鍵情報はf(IDi)、IDjを識別情報とする端末の分配鍵情報はf(IDj)である。これらがそれぞれの端末にあらかじめ配付されているとする。なおここで各端末の識別情報は0からp-1までの整数であるとしている。また、１次多項式f(x)は素数pを法として求めるため、図１では表現されていないが、各端末の分配鍵情報は0からp-1までの整数値となる。ここで、各端末には１次多項式f(x)の１点の座標だけが分配鍵情報として配付されているため、２端末が結託しないかぎり自身の分配鍵情報から他の端末の分配鍵情報を類推することはできない。
【００３２】
本実施の形態１においてはセンター側で各端末の識別情報と分配鍵情報を管理する。センターにおける管理では各端末の分配鍵情報そのものをデータベースで管理してもよいが、上記１次多項式f(x)だけを保管しておけば十分である。つまり、各端末の分配鍵情報はこの式に各端末の識別情報を代入すると、必要な都度求めることができる。
【００３３】
ここまでの部分は（k,n）しきい値法における特にkが２である場合の秘密鍵の分散の方法と同じである。
【００３４】
図２は、従来例と同様に５個の端末のうち端末T1だけを排除して残りの端末で共通の秘密鍵を共有する場合を示している。センターはまず、排除すべき端末T1の分配鍵情報を、保管している１次多項式に端末T1の識別情報を入力することにより求める。そして求めた端末T1の分配鍵情報を同報で各端末に送信する。例として図３に端末T3の内部構成を示している。１は端末T3の分配鍵情報f(ID3)の格納部であり、２はセンターから送付された端末T1の分配鍵情報f(ID1)を受信する受信部、３は受信した分配鍵情報と格納している分配鍵情報f(ID3)を用いて、秘密鍵を求める秘密鍵算出部である。秘密鍵算出部では、図１において相異なる２つの座標点から対応する１次多項式の各係数、つまり傾きaや切片bを以下の（数１）を解いて求める。なお、以下の（数１）は法p上で計算する。
【００３５】
【数１】
【００３６】
図では秘密鍵算出部は、端末T1を排除して残りの端末で共有する秘密鍵としてaを出力しているが、これは上記式を解いて求めた傾きa,bを用いてbまたはa+bを秘密鍵としてもよい。一方、端末T1も図３と同じ構成であるが、端末T1の秘密鍵算出部だけは自分の保持している分配鍵情報とセンターから配付された分配鍵情報が同じf(ID1)であるため、図１において１点の座標しか獲得していないことになり、前記１次多項式、つまり傾きaおよび切片bを双方とも決定することができない。従って上記秘密鍵を共有できない。
【００３７】
ここでは簡単のために端末が全部で５つでありその中から端末T1だけを排除する場合について述べたが、同様にして任意の端末数の中から任意の１つの端末を排除することができる。従って、実施の形態１における鍵共有方式では、センターからわずか１回だけデータ送信することにより、任意の１個の端末を排除して残りの端末で秘密鍵を共有することができる。また、実施の形態１においては各端末はそれぞれ分配鍵情報を１つだけ保管しておけばよい。
【００３８】
（実施の形態２）
次に、最初に端末T1を排除し、続けて端末T2を排除する場合を考える。これは例えば５端末で共通の秘密鍵を共有してグループ内の暗号通信を行っている際に、まず端末T1が盗難され、これに対応して残りの４端末で新たな共通の秘密鍵を共有する、次にさらに端末T2も盗難される、といったシナリオである。
【００３９】
実施の形態１では各端末は１つの１次多項式f(x)に対応した分配鍵情報を保持していた。本実施の形態ではこれに加えて、独立なもう１つの１次多項式g(x)=cx+d modp2に対応する分配鍵情報g(IDi)もあらかじめ各端末に蓄えておく。これは、端末T1を排除した段階でf(x)に関するすべての情報が公開されてしまうため、端末T2を排除するためには新たな多項式g(x)に対応した分配鍵情報が必要であるためである。
【００４０】
ところで、この時の端末T2の排除の仕方として２つの場合が考えられる。１つ目は端末T2を排除するとき、端末T1は正規端末として復活し、T2を除いた残りの４端末で新たな秘密鍵を共有する場合である。２つ目は端末T2を排除するとき、その前に排除した端末T1も継続して排除し、T1,T2を除いた残りの３端末で新たな秘密鍵を共有する場合である。前者の場合には、端末T2を排除するためにg(ID2)を同報送信し、秘密鍵を係数c,dを用いて求めればよい。端末T1も含め端末T2以外の端末では、g(x)の係数c,dを求めることができる。一方端末T2だけは、g(x)を決定できないため、秘密鍵を求めることができない。次に、後者の場合について説明する。この場合秘密鍵を、f(x)の係数a,bとg(x)の係数c,dの双方を用いて求めればよい。また、f(x)の係数a,bの代わりに当初端末T1を排除して残りの端末で共有した前の秘密鍵を用いてもよい。端末T3〜T5は上記a,b,c,dのいずれも算出でき新たな秘密鍵を求められる。一方、端末T1はf(x)の係数a,bを求められず、端末T2はg(x)の係数c,dを求められないため、双方を排除することができる。
【００４１】
なお、以上の実施の形態２では端末排除の回数が２回（最初にT1、次にT2を排除）であったが、これに引き続いてさらに端末を排除するためには、排除の回数に応じた分配鍵情報をあらかじめ各端末に格納しておく必要がある。先にも述べたとおり、これは前の端末排除に用いた分配鍵情報が次の端末排除のために利用できないためである。
【００４２】
（実施の形態３）
実施の形態２では、あらかじめ端末排除の回数分の多項式を選択し、これに対応した分配鍵情報を各端末に格納しておく。そして端末排除のたびにこれを順番に使用し、その都度排除した端末以外で、新しい秘密鍵が共有されるものであった。これに対し、実施の形態３では、１つの分配鍵情報を格納し、端末排除のたびにこれを更新して新しい分配鍵情報を各端末で求めるといった方法である。実施の形態２に比べて端末における分配鍵情報の格納領域が削減できる。また実施の形態２が端末排除の回数があらかじめ格納している分配鍵情報の個数に依存して有限であったのに対し、実施の形態３ではこの制限がない。図４は、端末T3の構成を示したものであり、図３に分配鍵情報を更新する部分を追加している。１、２、３は図３と同じである。端末T3は秘密鍵算出部３の出力として前記１次多項式f(x)の傾きaと切片bを求める。なお、図では秘密鍵算出部は、端末T1を排除して残りの端末で共有する秘密鍵としてaを出力しているが、これは上記求めた傾きa,bを用いて例えばbまたはa+bなどを秘密鍵としてもよい。４は秘密鍵算出部２で求めた前記aとbをそれぞれ固定の秘密変換して、その結果のa'、b'を新たな傾きと切片とする新しい１次多項式f'(x)=a'x+b' modpを求める変換部である。５はこの新しい１次多項式f'(x)に、端末T3の識別情報格納部５に格納されているID3を代入して新しい分配鍵情報を求める分配鍵情報更新部である。この出力が１の分配鍵情報格納部に新たに設定され、分配鍵情報が更新される。なお、このうち変換部と分配鍵情報更新部はユーザに内部が見られないことが必要である。図４におけるハッチングはこのことを意味にしている。これは、もし端末で新しい多項式f'(x)が見られると、他の端末の分配鍵情報は勿論、本来センターから排除すべき端末の分配鍵情報が通知されて初めて求められるはずの秘密鍵がすでに求められるからである。なお、変換部と分配鍵情報更新部をユーザに見られない部分で実行する代わりに、実行時のデータを見ることはできないという前提のもと、分配鍵情報を更新した後に新しい多項式f'(x)の係数a', b'を消去してもよい。これにより、ユーザに見られない特別な部分を備える必要はなくなる。
【００４３】
なお、この場合センター側でも同じ変換を行って前のf(x)を新しい１次多項式f'(x)に更新する。そして、この後さらに端末T2を排除する場合には、センターは新しい１次多項式f'(x)から端末T2の分配鍵情報f'(ID2)を獲得してこれを同報で端末に通知する。排除されていない端末T3では分配鍵情報格納部に格納された分配鍵情報f'(ID3)とセンターから送られた情報f'(ID2)を用いて１次多項式f'(x)の係数a',b'を求めこれらから新しい秘密鍵を算出する。一方、端末T2は格納している分配鍵情報とセンターからの分配鍵情報が重なるため前記１次多項式f'(x)を決定できない。また最初に排除された端末T1も、最初の１次多項式f(x)の係数a,bを獲得できないために、新しい１次多項式f'(x)の係数a'b'を獲得できない。そのため端末T2が排除された場合には継続して端末T1も排除されている。
【００４４】
以上端末排除回数が２回の場合について述べたが、３回以上の場合も同様で、秘密鍵算出部において求める多項式の係数を順次変換して、次の多項式を求め新たな分配鍵情報を求める。従ってこの場合端末排除回数が何回であっても、各端末で保有する分配鍵情報は１つであり、またセンターにおける管理もそのときの１次多項式だけである。
【００４５】
以上、ここまでの実施の形態１〜３では、１回には１個の端末だけを排除する場合について述べたが、以降の実施の形態４および５では、同時に複数の端末を排除する方法について述べる。
【００４６】
（実施の形態４）
図５は実施の形態４における各端末の分配鍵情報を模式的に示した図である。この例では、素数pを法としてその上での２次多項式F(x)=ax ２ +bx+c modpを考え、各端末の識別情報をx座標としたy座標値を各端末の分配鍵情報としている。例えばIDiを識別情報として持つ端末の分配鍵情報は、F(IDi)となり、これらが各端末にあらかじめ配付されているとする。端末の分配鍵情報は、F(x)が素数pを法としているため、図５では表現されていないが0からp-1までの整数値となる。センター側では各端末の分配鍵情報と識別情報を管理する。管理方法としては分配鍵情報をそれぞれデータベースで保管してもいいが、上記２次多項式だけを保管し、各端末の識別情報を用いて必要な都度対応する端末の分配鍵情報を算出してもよい。
【００４７】
図６は、５個の端末のうち端末T1と端末T2を同時に排除して残りの端末で秘密鍵を共有する場合を示している。センターはまず、排除すべき端末T1とT2の分配鍵情報を、保管している２次多項式にそれぞれの識別情報を入力することにより求める。そして求めた分配鍵情報F(ID1), F(ID2)を同報で各端末に送信する。例として図７に端末T3の内部構成を示している。１１は端末T3の分配鍵情報F(ID3)の格納部であり、１２はこの分配鍵情報F(ID3)とセンターから送付された２つの端末の分配鍵情報F(ID1),F(ID2)を用いて、秘密鍵を求める秘密鍵算出部である。秘密鍵算出部では、図５において相異なる３点の座標点F(ID1),F(ID2),F(ID3)から対応する２次多項式の係数a,b,cを求め、これをもとに秘密鍵を算出する。
なお、a,b,cを求めるための具体的な計算は以下の（数２）のとおりである。なお、以下の（数２）は法p上で計算する。
【００４８】
【数２】
【００４９】
端末T4,T5も同様に係数a,b,cを求めて端末T3と同じ秘密鍵を算出する。図７ではaを秘密鍵としているが、これが例えばaやa+b、a+b-cなどであってよい。一方、端末T1,T2も図７と同じ構成であるが、端末T1と端末T2の秘密鍵算出部は自分の保持している分配鍵情報とセンターから配付された分配鍵情報が重なっているため、図５において２点の座標しか獲得していないことになり、前記２次多項式を決定できない。
【００５０】
このことにより、第１の実施の形態における鍵共有方式では、センターから２個のデータを送信することにより、同時に２個の端末を排除して残りの端末で秘密鍵を共有できる。
【００５１】
実施の形態４は２端末を同時に排除するが、１端末だけを排除することも可能である。そのためにはセンターは予備の分配鍵情報を求める。つまり、図５のグラフにおけるx座標において各端末の識別情報に割り当てていない値をいくつか予備に確保しておく。そして対応する座標点を予備の分配鍵情報とする。この分配鍵情報はあらかじめデータベースで保管しておいても良いし、多項式だけを保管しておいて分配鍵情報は都度求めてもよい。例えばセンターが端末T1だけを排除する場合には、端末T1の分配鍵情報と予備の分配鍵情報のうち任意の１つを同報で通知する。端末T1以外の端末では、自身の分配鍵情報とセンターから送付される端末T1の分配鍵情報と予備の情報を用いて秘密鍵を求める。端末T1だけは自身の分配鍵情報とセンターから送付される一方の情報が重なっているため秘密鍵を求めることができない。
【００５２】
また、上記述べた予備の分配鍵情報を用いることにより、どの端末も排除せずに秘密鍵の更新だけを行うことも可能である。つまり、実施の形態４の例ではセンターから端末に同報で通知する２つの情報を双方とも予備の分配鍵情報とする。このことにより、すべての端末は新しい秘密鍵を算出できる。この場合、端末側は秘密鍵の定期的な更新なのか、端末を排除するための更新なのかを全く意識せず、同じ処理を行うだけでよい。
【００５３】
なお、以上の実施の形態４においては２個までの端末を同時に排除するために２次多項式を用いたが、一般にN個までの端末を排除するためにはN次多項式を用いる。このとき、センターから端末に同報通信されるデータの個数はN個である。
【００５４】
（実施の形態５）
次に、複数端末を同時に排除するためのもう１つの方法を実施の形態５として説明する。図８は実施の形態５における各端末の分配鍵情報を模式的に示した図である。この例では、素数p1、p2を法としてその上での１次多項式を２つ（f(x)=ax+b modp1、g(x)=cx+d modp2）考え、それぞれの多項式における各端末の識別情報をx座標としたy座標値を各端末の分配鍵情報としている。例えばIDiを識別情報として持つ端末の分配鍵情報は、f(IDi)とg(IDi)となり、これらが各端末にあらかじめ配付されているとする。なお、前者を端末の第１の分配鍵情報、後者を第２の分配鍵情報と呼ぶことにする。センター側では上記１次多項式f(x),g(x)を保管している。
【００５５】
図９は、実施の形態４と同様に５個の端末のうち端末T1と端末T2を同時に排除して残りの端末で秘密鍵を共有する場合を示している。センターはまず、保管している１次多項式f(x),g(x)に対応する端末の識別情報を入力することにより、端末１の第１の分配鍵情報f(ID1)と端末２の第２の分配鍵情報g(ID2)を求める。そして求めた分配鍵情報を同報で各端末に送信する。例として図１０に端末T3の内部構成を示している。２１は端末T3の第１の分配鍵情報f(ID3)の格納部であり、２２はこの分配鍵情報f(ID3)とセンターから送付された端末T1の分配鍵情報f(ID1)を用いて、１次多項式f(x)に関する中間秘密鍵を求める第１の中間秘密鍵算出部である。また２３は端末T3の第２の分配鍵情報g(ID3)の格納部であり、２４はこの分配鍵情報g(ID3)とセンターから送付された端末T2の分配鍵情報g(ID2)を用いて、１次多項式g(x)に関する中間秘密鍵を求める第２の中間秘密鍵算出部である。そして２５は前記第１、第２の中間秘密鍵を用いて秘密鍵を算出する秘密鍵算出部である。前記第１、第２の中間秘密鍵算出部では、図８における直線f(x)およびg(x)上の相異なる２点から直線の係数（傾き、切片）の全部または一部から所定の方法で導出されるデータを中間秘密鍵として求める。図ではそれぞれの傾きの係数a,cを出力する場合について示している。前記秘密鍵算出部では前記中間秘密鍵算出部の出力を、ある関数Data()に入力し秘密鍵を算出する。秘密の関数としては例えば入力値の加算や排他的論理和といった簡単なものであってもよい。図１０では中間秘密鍵a,cの加算結果a+cを秘密鍵としている。
【００５６】
ところで、端末１は第１の中間秘密鍵を得ることができない。また端末２は第２の中間秘密鍵を得ることはできない。この結果、端末１および２は他の端末が共有する秘密鍵を獲得することができない。
【００５７】
なお、この例ではセンターはf(ID1)とg(ID2)を全端末に同報で配送して端末１と端末２を排除したが、この代わりにg(ID1)とf(ID2)を配送してもよい。
【００５８】
この実施の形態５では、実施の形態４が２次多項式を用いて実現していることを１次多項式を２つ用いて実現している。実施の形態４では、秘密鍵算出部において３個の座標から２次多項式を解くことが必要であり、そのためには（数２）で示した比較的複雑な計算を行なわなければならない。これに対して実施の形態５では各中間秘密鍵では１次多項式を解けばよく（（数１）の計算）、トータルでは実施の形態４に比べて計算量が削減できる。具体的には（数１）の計算には乗算が2回、除算が1回（加減算は乗除算の計算量に比べると無視できるほどわずかであるため、ここでは考慮しない）かかり、（数２）の計算には乗算が23回、除算が1回かかる。そのため、実施の形態５では実施の形態４に比べてはるかに乗算回数が少なくてすむ。
【００５９】
なお、実施の形態５においても１端末だけを排除することが可能である。方法としては３つある。第１の方法は、例えばf(x)の方だけを使用する。このとき図１０においては第１の中間秘密鍵算出部の出力が秘密鍵となる。第２の方法は、例えばf(x)において排除すべき端末の分配鍵情報を送付し、g(x)においては予備の分配鍵情報を送信する方法であってもよい。この場合すべての端末は第２の中間秘密鍵を獲得できるが、排除される端末だけは第１の中間秘密鍵を算出できないため、最終的な秘密鍵を求めることができない。第２の方法の場合には端末側は排除すべき端末の数が１端末だけなのか２端末なのかを意識することなく常に同じ処理を行えばよい。また、第３の方法では、端末T1だけを排除するに端末T1の２つの分配鍵情報f(ID1)とg(ID1)を送付する。端末T1以外の端末は２つの中間共通データを求めこれから秘密鍵を算出できる。端末T1だけは中間共通データを双方とも算出することができない。
【００６０】
なお、前記第３の方法を、実施の形態１を改善して端末における秘密鍵算出の計算量を削減する方法と見ることができる。実施の形態１に述べた方法では、秘密情報は0以上p-1以下の整数となり、この総当たり攻撃に対する安全性を確保するためにはpを大きく取る必要がある。ところが法pを大きくすると秘密鍵の算出のための計算がすべて大きな法の計算となり計算量が多くなる。その計算量の増加はpの大きさに比べて指数関数的に増加する。例えばpを32ビットの値として32ビットの幅の乗算の計算量は、16ビット幅の乗算の計算量の4倍になるといった具合である。そこで、この計算量を削減するため、大きな法pの代わりに比較的小さな法p'を複数備え、この上での１次多項式を考える。各端末は、それぞれの１次多項式に対応する座標を分配鍵情報として保持する。センターは排除する端末の、複数の分配鍵情報を同報で通知し、各端末ではそれぞれから中間秘密鍵を求め、それらを結合することにより大きな法p程度の秘密鍵を獲得する。これにより処理量の削減、速度アップが可能になる。
【００６１】
なお、実施の形態５では２個の端末を同時に排除するために１次多項式を２個用いたが、一般にN個の端末を同時に排除するためには１次多項式をN個用いればよい。また、１次多項式ではなく比較的低次の多項式を複数個用いてもよい。
【００６２】
なお、実施の形態４、５においても実施の形態３で述べている各端末の分配鍵情報の更新部分を追加することができる。
【００６３】
以上の５つの実施の形態では各端末の分配鍵情報を、素体上の多項式の座標としていたが何もこれに限るものではない。例えばこれを素体の拡大体等の一般の有限体上の多項式の座標に拡張することができる。その他相異なるk+1個の分配鍵情報がそろった場合にのみ、各端末間で共通の鍵が共有できるものであればよい。この部分は秘密分散や（k,n）しきい値法に関する公知の技術が適用される。
【００６４】
また、実施の形態３（図４）の変換部を、多項式の係数をそれぞれ固定の秘密変換して実現しているが、秘密鍵を固定に変換するようなものであればどんなものでもよい。この変換自身を外から変更できるようにしておいてもよい。
【００６５】
また、実施の形態３の分配鍵情報更新部において、各端末の識別情報を元に分配鍵情報を算出しているが、更新前の分配鍵情報を元に新しい分配鍵情報を算出しても良い。ただし、この場合には分配鍵情報が各端末ごとに重ならないよう留意する必要がある。
【００６６】
また、特に実施の形態２のように分配鍵情報を自動的に端末内で更新していく場合には、各端末が共有する秘密鍵は必ずしもセンターが都度指定したものにはならない。そこで、センターが秘密鍵Kを指定したい場合には、センターは前記Kを保持している秘密鍵で暗号化し、排除する端末の分配鍵情報などと同時に同報で各端末に送付する。各端末では秘密鍵算出部の出力を用いて、センターから送られてきたデータを復号し、その結果を秘密鍵とする。
【００６７】
また、このように秘密鍵を同報で更新していく場合、何らかの都合でセンターからの通信を獲得できず、更新ができない端末が生じる場合がある。このために、各分配鍵情報にはバージョン番号を付加するとよい。そしてセンターとのやり取りでこのバージョンが食い違ってしまった場合には、センターに要求を行い、センターが保持している各バージョンの予備の分配鍵情報を順次送付してもらい、秘密鍵を最新のバージョンまで順番にバージョンアップすることができる。また、端末に分配鍵を更新する部分が備えられている場合には、センターはバージョン合わせが必要となる端末に対して、最新の秘密鍵を個別に暗号化して送ってもよい。当該の端末では最新の秘密鍵を他の端末と共有すると同時に、この秘密鍵から次の秘密鍵と分散鍵情報を算出する。なお、この場合のバージョン合わせの方法では、端末から端末が最初保持している秘密鍵のバージョンの情報を知る必要がないし、センターから１回通知するだけでバージョンが整合する。
【００６８】
また、センターから端末に同報で通知される分配鍵情報が途中で誤りを含んでしまう場合がある。こういった場合の研究が秘密分散の分野でなされている。研究成果は、M.Tompa, and H.Woll, "How to Share a Secret with Cheaters", Journal of Cryptology, v.1, n.2, 1988, pp133-138などを参照。本発明はこのような研究成果もそのまま鍵共有方法に応用できる。
【００６９】
【発明の効果】
以上説明したように、本発明では例えば１個の端末を排除して残りの端末で同じ秘密鍵を獲得するために、センターはわずか１個のデータを送付するだけでよい。一般にはN個以下の端末を同時に排除するためには、センターはN個の情報を送ればよい。このことによりセンター側の処理の手間および通信量が削減され、また端末間での秘密鍵の更新のずれが少ないため不都合が生じにくい。
【００７０】
また、本発明の請求項４および５に対応した構成により、センター側では各端末の分配鍵情報をそれぞれ管理する必要はなく、実施の形態ではその元になる多項式だけを管理すればよい。そして必要な場合に多項式に端末の識別情報を代入することにより対応する端末の分配鍵情報を得ることができる。これによりセンター側の端末管理の負担が軽減される。
【００７１】
また、本発明の請求項６に対応した構成により、分配鍵情報は変換部と分配鍵情報更新部を用いて更新することにより、各端末においては１つの分配鍵情報を管理しておけばよい。これにより端末側およびセンター側の分配鍵情報の管理負担が軽減される。
【００７２】
また、本発明に示した構成により、高次の多項式を使用する代わりに、比較的低次の多項式を複数個用いることにより、安全性を保持しつつ端末における秘密鍵の算出のための計算量を削減することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態１における各端末の分配鍵情報を模式的に示す図
【図２】本発明の実施の形態１においてセンターが５つの端末のうち端末T1を排除する場合について示す図
【図３】本発明の実施の形態１における端末T3の内部の構成を示す図
【図４】本発明の実施の形態３における端末内での分配鍵情報の更新を可能にする構成を示す図
【図５】本発明の実施の形態４における各端末の分配鍵情報を模式的に示す図
【図６】本発明の実施の形態４においてセンターが５つの端末のうち端末T1と端末T2を同時に排除する場合について示す図
【図７】本発明の実施の形態４における端末T3の内部の構成を示す図
【図８】本発明の実施の形態５における各端末の分配鍵情報を模式的に示す図
【図９】本発明の実施の形態５においてセンターが端末T1と端末T2を同時に排除する場合について示す図
【図１０】本発明の実施の形態５における端末T3の内部の構成を示す図
【図１１】従来例１の鍵共有方法の構成を示す図
【図１２】従来例２の鍵共有方法の構成を示す図
【符号の説明】
１ 分配鍵情報格納部
２ 受信部
３ 秘密鍵算出部
４ 変換部
５ 分配鍵情報更新部
６ 識別情報格納部
１１ 分配鍵情報格納部
１２ 受信部
１３ 秘密鍵算出部
２１ 分配鍵情報格納部
２２ 中間秘密鍵算出部
２３ 分配鍵情報格納部
２４ 中間秘密鍵算出部
２５ 秘密鍵算出部
【発明の属する技術分野】
本発明は、センターおよび複数端末からなる通信システムにおいて暗号通信を行うシステムに関し、特にセンターから複数端末に共通の秘密鍵を安全に配送する装置に関する。さらにセンターからの通信量を削減してセンターが特定した端末以外のすべての端末で秘密鍵を共有する鍵共有装置に関するものである。
【０００２】
【従来の技術】
センターおよび複数端末からなる通信システムにおいて、センターの管理のもと複数の端末がグループを形成し、グループで同じ秘密鍵を共有して同報の暗号通信を行う場合を考える。グループの秘密鍵を用いて暗号化された情報は、同じ秘密鍵を保有するグループ内の端末だけが復号することができる。ところで、このグループから特定の端末を排除したい場合が生じうる。それは例えばグループ内のある端末が盗難され、その端末を用いた暗号通信の盗聴や偽情報の送信などの不正が考えられる場合などである。このとき、この秘密鍵を管理するセンターは、できるだけ速やかに、盗難された端末を排除して、残りの端末だけで新たな秘密鍵を共有することが必要となる。
【０００３】
（従来例１）
図１１はセンターが特定した端末以外で鍵データを共有するための、第１の従来例における鍵共有方法である。この図では５個の端末T1,…,T5がそれぞれ固有の固有鍵k1,…,k5を保持しており、センターCは全端末の固有鍵を管理している。例えばセンターが端末T1を排除して他のT2,…,T5で新しい共通の秘密鍵を配付するためには、まず、センターは秘密鍵Kを生成し、これをそれぞれk2,…,k5を鍵として暗号化し、それぞれT2,…,T5に配送する。各端末では固有鍵を用いてこれを復号し、秘密鍵Kを獲得する。なお、図中において例えばEk2(K)はKを固有鍵k2で暗号化した暗号文である。この通信路上のデータはそれぞれ端末T2〜T5の固有鍵で暗号化されているため、たとえ端末T1がこの通信データを盗聴したとしてもセンターが生成した分配鍵情報Kを獲得することができない。
【０００４】
しかし、この方法では一般にN個の端末から１つの端末を排除するためには、センターはN-1回の暗号化を行い、N-1個のデータを送信しなくてはならない。グループが大きくなると、この作業はセンターにとって非常に負担になる。また、全局更新まではグループ内の暗号通信等の業務を停止する必要があるが、N-1局に配り終えるまでの業務停止期間が長いと大きな問題である。
【０００５】
（従来例２）
図１２に第２の従来例における鍵共有方法について示す。この方法では、従来例１における端末をグループ化して、センター側の暗号化の手間と送信データ量の削減を行う。この図では５つの端末をT1,T2と残りの３端末の、２つのグループに分けて、それぞれで共通のグループ鍵G1,G2を共有している。そして例えばセンターが端末T1を排除する場合には、端末T2に対しては生成した分配鍵情報KをT2の固有鍵k2を用いて暗号化し、残りのT3,T4,T5に対してはグループ鍵G2を用いて分配鍵情報Kを暗号化して配送する。T3,T4,T5の各端末ではそれぞれグループ鍵G2を用いてこれを復号し分配鍵情報Kを獲得する。なお、端末のグループ化は多重や階層的に行うことも考えられる。
【０００６】
しかし、第２の従来例では各端末に固有の固有鍵に加えて、グループ鍵もセンター側および端末側で管理する必要がある。さらに、第２の従来例であっても第１の従来例と同様、端末の数が多くなるとセンターの暗号化、およびデータの送信の負担は大きくなり、また全局更新までの業務停止期間が長くなる。
【０００７】
【発明が解決しようとする課題】
例えば１０００個の端末から１個の端末を排除して、残りの９９９個の端末で新たな共通の秘密鍵を共有する場合を考える。このとき、第１の従来例では９９９回の暗号化の処理と９９９回の暗号文の送信を行う必要がある。また第２の従来例で例えば１０００個の端末を５００個づつの２つにグループに分けた場合には、排除すべき端末を含むグループでは各端末ごとに４９９回、もう１方のグループにはグループ鍵で一括で、合計５００回の暗号化の処理と暗号文の送信が必要である。いずれにしても、センター側にとってこれら作業は非常に負担なものとなる。また、全局更新までの業務停止期間が長くなる。
【０００８】
さらに、第２の従来例ではセンター側および端末側では、各端末の固有鍵とともに、グループ化の方法によっては多くのグループ鍵を管理する必要がある。
【０００９】
本発明はかかる点に鑑み、特定の端末だけを排除して、他の端末で分配鍵情報を共有する方法であって、次の点を特徴とする鍵共有方法を実現することを目的とする。
【００１０】
(1) センターから端末への通信量が少ない。
センターにおける暗号処理の手間が少なく、暗号文の送信量が少ない。
全局更新までの業務停止期間が短い。
【００１１】
(2) 端末の秘密鍵が少ない。
センターにおいて管理を行う端末の鍵が少ない。
端末において管理を行う鍵が少ない。
【００１２】
【課題を解決するための手段】
本発明の第１の構成における鍵共有システムは、センター側装置と相異なる分配鍵情報を持つ複数の端末からなり、センター側装置は全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、kを正整数とするとき、特定のk個の端末の分配鍵情報を同報で全端末に通知する通知部を備え、各端末は、分配鍵情報を格納する分配鍵情報格納部と、前記センター側装置から通知されたk個の分配鍵情報を受信する受信部と、前記受信部で受信したk個の分配鍵情報と、前記分配鍵情報格納部に格納される分配鍵情報の計k+1個の分配鍵情報がすべて相異なる場合にのみ、これらk+1個の分配鍵情報より前記特定のk個の端末を除く残りの端末で共通の秘密鍵を算出する秘密鍵算出部からなり、前記各端末の分配鍵情報は、前記秘密鍵算出部に入力されるk+1個の分配鍵情報がすべて相異なる場合にのみ前記秘密鍵が復元できるように予め定められ各端末に分配されたものであることを特徴とする。
【００１３】
本発明の第２の構成における鍵共有システムは、第１の構成における前記センター側装置が、全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、kとmをそれぞれ正整数とするとき、特定のm個の端末の分配鍵情報と任意のk-m個の予備分配鍵情報の合計k個の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする。
【００１４】
本発明の第３の構成における鍵共有システムは、第１の構成における前記センター側装置が、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、任意のk個の予備の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする。
【００１５】
本発明の第４の構成における鍵共有システムは、第１の構成における前記各端末は相異なる識別情報を保持し、前記センター側装置は全端末分配鍵情報格納部の代わりに、前記秘密鍵を保持する秘密鍵格納部と、前記秘密鍵と任意の端末の識別情報を入力として、対応する端末の分配鍵情報を算出する分配鍵情報算出部を備えていることを特徴とする。
【００１６】
本発明の第５の構成における鍵共有システムは、第２、３の構成における前記各端末は相異なる識別情報を保持し、前記センター側装置は前記予備分配鍵情報格納部の代わりに、前記秘密鍵を保持する秘密鍵格納部と、どの端末の識別情報とも異なる予備の情報と前記秘密鍵を入力として、前記予備の分配鍵情報を算出する予備分配鍵情報算出部を備えていることを特徴とする。
【００１７】
本発明の第６の構成における鍵共有システムは、センター側装置と相異なる分配鍵情報を持つ複数の端末からなり、センター側装置は全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、kを正整数とするとき、特定のk個の端末の分配鍵情報を同報で全端末に通知する通知部を備え、各端末は、分配鍵情報を格納する分配鍵情報格納部と、前記センター側装置から通知されたk個の分配鍵情報を受信する受信部と、前記受信部で受信したk個の分配鍵情報と、前記分配鍵情報格納部に格納される分配鍵情報の計k+1個の分配鍵情報がすべて相異なる場合にのみ、これらk+1個の分配鍵情報より前記特定のk個の端末を除く残りの端末で共通の第１の秘密鍵を算出する秘密鍵算出部と、前記第１の秘密鍵を全端末共通の変換方法で変換して第２の秘密鍵を求める変換部と、前記第２の秘密鍵から端末の新しい分配鍵情報を算出し、前記分配鍵情報格納部に格納して分配鍵情報を更新する分配鍵情報更新部からなり、前記各端末の更新前の分配鍵情報は、前記秘密鍵算出部において入力されるk+1個の分配鍵情報がすべて相異なる場合にのみ前記第１の秘密鍵が復元できるように予め定められ各端末に分配されたものであり、前記分配鍵情報更新部によって更新された各端末の分配鍵情報は、前記と同様前記第２の秘密鍵が復元できるように定めて各端末に分配されたものになり、前記各端末の変換部と分配鍵情報更新部は、外部より観察したり、変更できないものであり、前記センター側装置の全端末分配鍵情報格納部は、前記各端末で更新された分配鍵情報を格納することを特徴とする。
【００１８】
本発明の第７の構成における鍵共有システムは、第６の構成における前記変換部と分配鍵情報更新部を外部より観察したり、変更できない領域に備える代わりに、分配鍵情報更新部が、分配鍵情報を更新した後に前記第２の秘密鍵を消去することを特徴とする。
【００１９】
本発明の第８の構成における鍵共有システムは、第６の構成における前記センター側装置が、全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、kとmをそれぞれ正整数とするとき、特定のm個の端末の分配鍵情報と任意のk-m個の予備分配鍵情報の合計k個の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする。
【００２０】
本発明の第９の構成における鍵共有システムは、第６の構成における前記センター側装置が、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、任意のk個の予備の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする。
【００２１】
本発明の第１０の構成における鍵共有システムは、第６の構成における前記センター側装置は前記全端末分配鍵情報格納部の代わりに、前記第１の秘密鍵を保持する秘密鍵格納部と、前記第１の秘密鍵と任意の端末の識別情報を入力として、対応する端末の分配鍵情報を算出する分配鍵情報算出部と、前記第１の秘密鍵を各端末の変換部と同じ変換方法で変換して第２の秘密鍵を求め、前記秘密鍵格納部に格納して第１の秘密鍵を更新するセンター側変換部を備えることを特徴とする。
【００２２】
本発明の第１１の構成における鍵共有システムは、第８、９の構成における前記センター側装置は前記予備分配鍵情報格納部の代わりに、前記第１の秘密鍵を保持する秘密鍵格納部と、どの端末の識別情報とも異なる予備の情報と前記第１の秘密鍵を入力として、前記予備の分配鍵情報を算出する予備分配鍵情報算出部と、前記第１の秘密鍵を各端末の変換部と同じ変換方法で変換して第２の秘密鍵を求め、前記秘密鍵格納部に格納して第１の秘密鍵を更新するセンター側変換部を備えることを特徴とする。
【００２３】
本発明の第１２の構成における鍵共有システムは、第６〜１１の構成における前記各端末内の変換部およびセンター側変換部において、固定の変換の代わりに、外部から変更できる変換を用いることを特徴とする。
【００２４】
本発明の第１３の構成における鍵共有システムは、第６〜１１の構成における前記各端末内の分配鍵情報更新部で、前記第２の秘密鍵と前記端末の識別情報を用いて、前記端末の新しい分配鍵情報を算出することを特徴とする。
【００２５】
本発明の第１４の構成における鍵共有システムは、第６〜９の構成における前記各端末内の分配鍵情報更新部で、前記第２の秘密鍵と端末の更新前の分配鍵情報を用いて、前記端末の新しい分配鍵情報を算出することを特徴とする。
【００２６】
本発明の第１５の構成における鍵共有システムは、第１〜１４の構成における前記秘密鍵算出部において、入力のk+1個の分配鍵情報に誤りが生じえる場合や、k+1個より多い分配鍵情報が入力された場合に、その中で正しいk+1個の相異なる分配鍵情報を用いて秘密鍵を算出することを特徴とする。
【００２７】
本発明の第１６の構成における鍵共有システムは、第１〜１５の構成における前記秘密鍵にバージョン番号を付加し、センター側装置は各バージョンの予備の分配鍵情報を保管し、バージョンが一致していない端末に前記必要な分配鍵情報を通知することを特徴とする。
【００２８】
本発明の第１７の構成における鍵共有システムは、第６〜１４の構成における前記秘密鍵にバージョン番号を付加し、バージョンが一致していない端末に正しいバージョンの秘密鍵を個別に暗号化して通知することを特徴とする。
【００２９】
【発明の実施の形態】
本発明は、グループ内のある端末を排除して残りの端末で新しい秘密鍵を共有するという目的に、秘密分散法、または（k,n）しきい値法と呼ばれる公知の手法を、新たに適用したものである。秘密分散法や（k,n）しきい値法の説明は、例えば岡本栄司「暗号理論入門」共立出版（1993）の6.2節に詳しい。秘密分散法は秘密度の高い鍵の保管方法として従来より知られているものであり、例えば鍵を２つに分けて２人が保管し、使うときはその２人が集まらないと使えないといったものである。（k,n）しきい値法はこれを一般化し、秘密鍵をn個に分け（なお以下では秘密鍵を分けた結果のそれぞれを、分配鍵情報と称することにする）、n個の中から任意のk個を集めれば元の秘密鍵が復元でき、k個より少なければ元の情報が全く得られないものである。
【００３０】
この（k,n）しきい値法の多項式を用いた例を用いて、本発明の実施の形態を以下に示す。
【００３１】
（実施の形態１）
本発明ではセンターと複数の端末からなり、各端末は相異なる分配鍵情報を保持している。図１は実施の形態１における各端末の分配鍵情報を模式的に示した図である。この実施の形態では、pを素数、a,b,xを法pのもとでの剰余元とし、法p上の１次多項式f(x)=ax+b modpを考え、各端末の識別情報をx座標としたy座標値を各端末の分配鍵情報としている。例えばIDiを識別情報とする端末の分配鍵情報はf(IDi)、IDjを識別情報とする端末の分配鍵情報はf(IDj)である。これらがそれぞれの端末にあらかじめ配付されているとする。なおここで各端末の識別情報は0からp-1までの整数であるとしている。また、１次多項式f(x)は素数pを法として求めるため、図１では表現されていないが、各端末の分配鍵情報は0からp-1までの整数値となる。ここで、各端末には１次多項式f(x)の１点の座標だけが分配鍵情報として配付されているため、２端末が結託しないかぎり自身の分配鍵情報から他の端末の分配鍵情報を類推することはできない。
【００３２】
本実施の形態１においてはセンター側で各端末の識別情報と分配鍵情報を管理する。センターにおける管理では各端末の分配鍵情報そのものをデータベースで管理してもよいが、上記１次多項式f(x)だけを保管しておけば十分である。つまり、各端末の分配鍵情報はこの式に各端末の識別情報を代入すると、必要な都度求めることができる。
【００３３】
ここまでの部分は（k,n）しきい値法における特にkが２である場合の秘密鍵の分散の方法と同じである。
【００３４】
図２は、従来例と同様に５個の端末のうち端末T1だけを排除して残りの端末で共通の秘密鍵を共有する場合を示している。センターはまず、排除すべき端末T1の分配鍵情報を、保管している１次多項式に端末T1の識別情報を入力することにより求める。そして求めた端末T1の分配鍵情報を同報で各端末に送信する。例として図３に端末T3の内部構成を示している。１は端末T3の分配鍵情報f(ID3)の格納部であり、２はセンターから送付された端末T1の分配鍵情報f(ID1)を受信する受信部、３は受信した分配鍵情報と格納している分配鍵情報f(ID3)を用いて、秘密鍵を求める秘密鍵算出部である。秘密鍵算出部では、図１において相異なる２つの座標点から対応する１次多項式の各係数、つまり傾きaや切片bを以下の（数１）を解いて求める。なお、以下の（数１）は法p上で計算する。
【００３５】
【数１】
図では秘密鍵算出部は、端末T1を排除して残りの端末で共有する秘密鍵としてaを出力しているが、これは上記式を解いて求めた傾きa,bを用いてbまたはa+bを秘密鍵としてもよい。一方、端末T1も図３と同じ構成であるが、端末T1の秘密鍵算出部だけは自分の保持している分配鍵情報とセンターから配付された分配鍵情報が同じf(ID1)であるため、図１において１点の座標しか獲得していないことになり、前記１次多項式、つまり傾きaおよび切片bを双方とも決定することができない。従って上記秘密鍵を共有できない。
【００３７】
ここでは簡単のために端末が全部で５つでありその中から端末T1だけを排除する場合について述べたが、同様にして任意の端末数の中から任意の１つの端末を排除することができる。従って、実施の形態１における鍵共有方式では、センターからわずか１回だけデータ送信することにより、任意の１個の端末を排除して残りの端末で秘密鍵を共有することができる。また、実施の形態１においては各端末はそれぞれ分配鍵情報を１つだけ保管しておけばよい。
【００３８】
（実施の形態２）
次に、最初に端末T1を排除し、続けて端末T2を排除する場合を考える。これは例えば５端末で共通の秘密鍵を共有してグループ内の暗号通信を行っている際に、まず端末T1が盗難され、これに対応して残りの４端末で新たな共通の秘密鍵を共有する、次にさらに端末T2も盗難される、といったシナリオである。
【００３９】
実施の形態１では各端末は１つの１次多項式f(x)に対応した分配鍵情報を保持していた。本実施の形態ではこれに加えて、独立なもう１つの１次多項式g(x)=cx+d modp2に対応する分配鍵情報g(IDi)もあらかじめ各端末に蓄えておく。これは、端末T1を排除した段階でf(x)に関するすべての情報が公開されてしまうため、端末T2を排除するためには新たな多項式g(x)に対応した分配鍵情報が必要であるためである。
【００４０】
ところで、この時の端末T2の排除の仕方として２つの場合が考えられる。１つ目は端末T2を排除するとき、端末T1は正規端末として復活し、T2を除いた残りの４端末で新たな秘密鍵を共有する場合である。２つ目は端末T2を排除するとき、その前に排除した端末T1も継続して排除し、T1,T2を除いた残りの３端末で新たな秘密鍵を共有する場合である。前者の場合には、端末T2を排除するためにg(ID2)を同報送信し、秘密鍵を係数c,dを用いて求めればよい。端末T1も含め端末T2以外の端末では、g(x)の係数c,dを求めることができる。一方端末T2だけは、g(x)を決定できないため、秘密鍵を求めることができない。次に、後者の場合について説明する。この場合秘密鍵を、f(x)の係数a,bとg(x)の係数c,dの双方を用いて求めればよい。また、f(x)の係数a,bの代わりに当初端末T1を排除して残りの端末で共有した前の秘密鍵を用いてもよい。端末T3〜T5は上記a,b,c,dのいずれも算出でき新たな秘密鍵を求められる。一方、端末T1はf(x)の係数a,bを求められず、端末T2はg(x)の係数c,dを求められないため、双方を排除することができる。
【００４１】
なお、以上の実施の形態２では端末排除の回数が２回（最初にT1、次にT2を排除）であったが、これに引き続いてさらに端末を排除するためには、排除の回数に応じた分配鍵情報をあらかじめ各端末に格納しておく必要がある。先にも述べたとおり、これは前の端末排除に用いた分配鍵情報が次の端末排除のために利用できないためである。
【００４２】
（実施の形態３）
実施の形態２では、あらかじめ端末排除の回数分の多項式を選択し、これに対応した分配鍵情報を各端末に格納しておく。そして端末排除のたびにこれを順番に使用し、その都度排除した端末以外で、新しい秘密鍵が共有されるものであった。これに対し、実施の形態３では、１つの分配鍵情報を格納し、端末排除のたびにこれを更新して新しい分配鍵情報を各端末で求めるといった方法である。実施の形態２に比べて端末における分配鍵情報の格納領域が削減できる。また実施の形態２が端末排除の回数があらかじめ格納している分配鍵情報の個数に依存して有限であったのに対し、実施の形態３ではこの制限がない。図４は、端末T3の構成を示したものであり、図３に分配鍵情報を更新する部分を追加している。１、２、３は図３と同じである。端末T3は秘密鍵算出部３の出力として前記１次多項式f(x)の傾きaと切片bを求める。なお、図では秘密鍵算出部は、端末T1を排除して残りの端末で共有する秘密鍵としてaを出力しているが、これは上記求めた傾きa,bを用いて例えばbまたはa+bなどを秘密鍵としてもよい。４は秘密鍵算出部２で求めた前記aとbをそれぞれ固定の秘密変換して、その結果のa'、b'を新たな傾きと切片とする新しい１次多項式f'(x)=a'x+b' modpを求める変換部である。５はこの新しい１次多項式f'(x)に、端末T3の識別情報格納部５に格納されているID3を代入して新しい分配鍵情報を求める分配鍵情報更新部である。この出力が１の分配鍵情報格納部に新たに設定され、分配鍵情報が更新される。なお、このうち変換部と分配鍵情報更新部はユーザに内部が見られないことが必要である。図４におけるハッチングはこのことを意味にしている。これは、もし端末で新しい多項式f'(x)が見られると、他の端末の分配鍵情報は勿論、本来センターから排除すべき端末の分配鍵情報が通知されて初めて求められるはずの秘密鍵がすでに求められるからである。なお、変換部と分配鍵情報更新部をユーザに見られない部分で実行する代わりに、実行時のデータを見ることはできないという前提のもと、分配鍵情報を更新した後に新しい多項式f'(x)の係数a', b'を消去してもよい。これにより、ユーザに見られない特別な部分を備える必要はなくなる。
【００４３】
なお、この場合センター側でも同じ変換を行って前のf(x)を新しい１次多項式f'(x)に更新する。そして、この後さらに端末T2を排除する場合には、センターは新しい１次多項式f'(x)から端末T2の分配鍵情報f'(ID2)を獲得してこれを同報で端末に通知する。排除されていない端末T3では分配鍵情報格納部に格納された分配鍵情報f'(ID3)とセンターから送られた情報f'(ID2)を用いて１次多項式f'(x)の係数a',b'を求めこれらから新しい秘密鍵を算出する。一方、端末T2は格納している分配鍵情報とセンターからの分配鍵情報が重なるため前記１次多項式f'(x)を決定できない。また最初に排除された端末T1も、最初の１次多項式f(x)の係数a,bを獲得できないために、新しい１次多項式f'(x)の係数a'b'を獲得できない。そのため端末T2が排除された場合には継続して端末T1も排除されている。
【００４４】
以上端末排除回数が２回の場合について述べたが、３回以上の場合も同様で、秘密鍵算出部において求める多項式の係数を順次変換して、次の多項式を求め新たな分配鍵情報を求める。従ってこの場合端末排除回数が何回であっても、各端末で保有する分配鍵情報は１つであり、またセンターにおける管理もそのときの１次多項式だけである。
【００４５】
以上、ここまでの実施の形態１〜３では、１回には１個の端末だけを排除する場合について述べたが、以降の実施の形態４および５では、同時に複数の端末を排除する方法について述べる。
【００４６】
（実施の形態４）
図５は実施の形態４における各端末の分配鍵情報を模式的に示した図である。この例では、素数pを法としてその上での２次多項式F(x)=ax ２ +bx+c modpを考え、各端末の識別情報をx座標としたy座標値を各端末の分配鍵情報としている。例えばIDiを識別情報として持つ端末の分配鍵情報は、F(IDi)となり、これらが各端末にあらかじめ配付されているとする。端末の分配鍵情報は、F(x)が素数pを法としているため、図５では表現されていないが0からp-1までの整数値となる。センター側では各端末の分配鍵情報と識別情報を管理する。管理方法としては分配鍵情報をそれぞれデータベースで保管してもいいが、上記２次多項式だけを保管し、各端末の識別情報を用いて必要な都度対応する端末の分配鍵情報を算出してもよい。
【００４７】
図６は、５個の端末のうち端末T1と端末T2を同時に排除して残りの端末で秘密鍵を共有する場合を示している。センターはまず、排除すべき端末T1とT2の分配鍵情報を、保管している２次多項式にそれぞれの識別情報を入力することにより求める。そして求めた分配鍵情報F(ID1), F(ID2)を同報で各端末に送信する。例として図７に端末T3の内部構成を示している。１１は端末T3の分配鍵情報F(ID3)の格納部であり、１２はこの分配鍵情報F(ID3)とセンターから送付された２つの端末の分配鍵情報F(ID1),F(ID2)を用いて、秘密鍵を求める秘密鍵算出部である。秘密鍵算出部では、図５において相異なる３点の座標点F(ID1),F(ID2),F(ID3)から対応する２次多項式の係数a,b,cを求め、これをもとに秘密鍵を算出する。
なお、a,b,cを求めるための具体的な計算は以下の（数２）のとおりである。なお、以下の（数２）は法p上で計算する。
【００４８】
【数２】
端末T4,T5も同様に係数a,b,cを求めて端末T3と同じ秘密鍵を算出する。図７ではaを秘密鍵としているが、これが例えばaやa+b、a+b-cなどであってよい。一方、端末T1,T2も図７と同じ構成であるが、端末T1と端末T2の秘密鍵算出部は自分の保持している分配鍵情報とセンターから配付された分配鍵情報が重なっているため、図５において２点の座標しか獲得していないことになり、前記２次多項式を決定できない。
【００５０】
このことにより、第１の実施の形態における鍵共有方式では、センターから２個のデータを送信することにより、同時に２個の端末を排除して残りの端末で秘密鍵を共有できる。
【００５１】
実施の形態４は２端末を同時に排除するが、１端末だけを排除することも可能である。そのためにはセンターは予備の分配鍵情報を求める。つまり、図５のグラフにおけるx座標において各端末の識別情報に割り当てていない値をいくつか予備に確保しておく。そして対応する座標点を予備の分配鍵情報とする。この分配鍵情報はあらかじめデータベースで保管しておいても良いし、多項式だけを保管しておいて分配鍵情報は都度求めてもよい。例えばセンターが端末T1だけを排除する場合には、端末T1の分配鍵情報と予備の分配鍵情報のうち任意の１つを同報で通知する。端末T1以外の端末では、自身の分配鍵情報とセンターから送付される端末T1の分配鍵情報と予備の情報を用いて秘密鍵を求める。端末T1だけは自身の分配鍵情報とセンターから送付される一方の情報が重なっているため秘密鍵を求めることができない。
【００５２】
また、上記述べた予備の分配鍵情報を用いることにより、どの端末も排除せずに秘密鍵の更新だけを行うことも可能である。つまり、実施の形態４の例ではセンターから端末に同報で通知する２つの情報を双方とも予備の分配鍵情報とする。このことにより、すべての端末は新しい秘密鍵を算出できる。この場合、端末側は秘密鍵の定期的な更新なのか、端末を排除するための更新なのかを全く意識せず、同じ処理を行うだけでよい。
【００５３】
なお、以上の実施の形態４においては２個までの端末を同時に排除するために２次多項式を用いたが、一般にN個までの端末を排除するためにはN次多項式を用いる。このとき、センターから端末に同報通信されるデータの個数はN個である。
【００５４】
（実施の形態５）
次に、複数端末を同時に排除するためのもう１つの方法を実施の形態５として説明する。図８は実施の形態５における各端末の分配鍵情報を模式的に示した図である。この例では、素数p1、p2を法としてその上での１次多項式を２つ（f(x)=ax+b modp1、g(x)=cx+d modp2）考え、それぞれの多項式における各端末の識別情報をx座標としたy座標値を各端末の分配鍵情報としている。例えばIDiを識別情報として持つ端末の分配鍵情報は、f(IDi)とg(IDi)となり、これらが各端末にあらかじめ配付されているとする。なお、前者を端末の第１の分配鍵情報、後者を第２の分配鍵情報と呼ぶことにする。センター側では上記１次多項式f(x),g(x)を保管している。
【００５５】
図９は、実施の形態４と同様に５個の端末のうち端末T1と端末T2を同時に排除して残りの端末で秘密鍵を共有する場合を示している。センターはまず、保管している１次多項式f(x),g(x)に対応する端末の識別情報を入力することにより、端末１の第１の分配鍵情報f(ID1)と端末２の第２の分配鍵情報g(ID2)を求める。そして求めた分配鍵情報を同報で各端末に送信する。例として図１０に端末T3の内部構成を示している。２１は端末T3の第１の分配鍵情報f(ID3)の格納部であり、２２はこの分配鍵情報f(ID3)とセンターから送付された端末T1の分配鍵情報f(ID1)を用いて、１次多項式f(x)に関する中間秘密鍵を求める第１の中間秘密鍵算出部である。また２３は端末T3の第２の分配鍵情報g(ID3)の格納部であり、２４はこの分配鍵情報g(ID3)とセンターから送付された端末T2の分配鍵情報g(ID2)を用いて、１次多項式g(x)に関する中間秘密鍵を求める第２の中間秘密鍵算出部である。そして２５は前記第１、第２の中間秘密鍵を用いて秘密鍵を算出する秘密鍵算出部である。前記第１、第２の中間秘密鍵算出部では、図８における直線f(x)およびg(x)上の相異なる２点から直線の係数（傾き、切片）の全部または一部から所定の方法で導出されるデータを中間秘密鍵として求める。図ではそれぞれの傾きの係数a,cを出力する場合について示している。前記秘密鍵算出部では前記中間秘密鍵算出部の出力を、ある関数Data()に入力し秘密鍵を算出する。秘密の関数としては例えば入力値の加算や排他的論理和といった簡単なものであってもよい。図１０では中間秘密鍵a,cの加算結果a+cを秘密鍵としている。
【００５６】
ところで、端末１は第１の中間秘密鍵を得ることができない。また端末２は第２の中間秘密鍵を得ることはできない。この結果、端末１および２は他の端末が共有する秘密鍵を獲得することができない。
【００５７】
なお、この例ではセンターはf(ID1)とg(ID2)を全端末に同報で配送して端末１と端末２を排除したが、この代わりにg(ID1)とf(ID2)を配送してもよい。
【００５８】
この実施の形態５では、実施の形態４が２次多項式を用いて実現していることを１次多項式を２つ用いて実現している。実施の形態４では、秘密鍵算出部において３個の座標から２次多項式を解くことが必要であり、そのためには（数２）で示した比較的複雑な計算を行なわなければならない。これに対して実施の形態５では各中間秘密鍵では１次多項式を解けばよく（（数１）の計算）、トータルでは実施の形態４に比べて計算量が削減できる。具体的には（数１）の計算には乗算が2回、除算が1回（加減算は乗除算の計算量に比べると無視できるほどわずかであるため、ここでは考慮しない）かかり、（数２）の計算には乗算が23回、除算が1回かかる。そのため、実施の形態５では実施の形態４に比べてはるかに乗算回数が少なくてすむ。
【００５９】
なお、実施の形態５においても１端末だけを排除することが可能である。方法としては３つある。第１の方法は、例えばf(x)の方だけを使用する。このとき図１０においては第１の中間秘密鍵算出部の出力が秘密鍵となる。第２の方法は、例えばf(x)において排除すべき端末の分配鍵情報を送付し、g(x)においては予備の分配鍵情報を送信する方法であってもよい。この場合すべての端末は第２の中間秘密鍵を獲得できるが、排除される端末だけは第１の中間秘密鍵を算出できないため、最終的な秘密鍵を求めることができない。第２の方法の場合には端末側は排除すべき端末の数が１端末だけなのか２端末なのかを意識することなく常に同じ処理を行えばよい。また、第３の方法では、端末T1だけを排除するに端末T1の２つの分配鍵情報f(ID1)とg(ID1)を送付する。端末T1以外の端末は２つの中間共通データを求めこれから秘密鍵を算出できる。端末T1だけは中間共通データを双方とも算出することができない。
【００６０】
なお、前記第３の方法を、実施の形態１を改善して端末における秘密鍵算出の計算量を削減する方法と見ることができる。実施の形態１に述べた方法では、秘密情報は0以上p-1以下の整数となり、この総当たり攻撃に対する安全性を確保するためにはpを大きく取る必要がある。ところが法pを大きくすると秘密鍵の算出のための計算がすべて大きな法の計算となり計算量が多くなる。その計算量の増加はpの大きさに比べて指数関数的に増加する。例えばpを32ビットの値として32ビットの幅の乗算の計算量は、16ビット幅の乗算の計算量の4倍になるといった具合である。そこで、この計算量を削減するため、大きな法pの代わりに比較的小さな法p'を複数備え、この上での１次多項式を考える。各端末は、それぞれの１次多項式に対応する座標を分配鍵情報として保持する。センターは排除する端末の、複数の分配鍵情報を同報で通知し、各端末ではそれぞれから中間秘密鍵を求め、それらを結合することにより大きな法p程度の秘密鍵を獲得する。これにより処理量の削減、速度アップが可能になる。
【００６１】
なお、実施の形態５では２個の端末を同時に排除するために１次多項式を２個用いたが、一般にN個の端末を同時に排除するためには１次多項式をN個用いればよい。また、１次多項式ではなく比較的低次の多項式を複数個用いてもよい。
【００６２】
なお、実施の形態４、５においても実施の形態３で述べている各端末の分配鍵情報の更新部分を追加することができる。
【００６３】
以上の５つの実施の形態では各端末の分配鍵情報を、素体上の多項式の座標としていたが何もこれに限るものではない。例えばこれを素体の拡大体等の一般の有限体上の多項式の座標に拡張することができる。その他相異なるk+1個の分配鍵情報がそろった場合にのみ、各端末間で共通の鍵が共有できるものであればよい。この部分は秘密分散や（k,n）しきい値法に関する公知の技術が適用される。
【００６４】
また、実施の形態３（図４）の変換部を、多項式の係数をそれぞれ固定の秘密変換して実現しているが、秘密鍵を固定に変換するようなものであればどんなものでもよい。この変換自身を外から変更できるようにしておいてもよい。
【００６５】
また、実施の形態３の分配鍵情報更新部において、各端末の識別情報を元に分配鍵情報を算出しているが、更新前の分配鍵情報を元に新しい分配鍵情報を算出しても良い。ただし、この場合には分配鍵情報が各端末ごとに重ならないよう留意する必要がある。
【００６６】
また、特に実施の形態２のように分配鍵情報を自動的に端末内で更新していく場合には、各端末が共有する秘密鍵は必ずしもセンターが都度指定したものにはならない。そこで、センターが秘密鍵Kを指定したい場合には、センターは前記Kを保持している秘密鍵で暗号化し、排除する端末の分配鍵情報などと同時に同報で各端末に送付する。各端末では秘密鍵算出部の出力を用いて、センターから送られてきたデータを復号し、その結果を秘密鍵とする。
【００６７】
また、このように秘密鍵を同報で更新していく場合、何らかの都合でセンターからの通信を獲得できず、更新ができない端末が生じる場合がある。このために、各分配鍵情報にはバージョン番号を付加するとよい。そしてセンターとのやり取りでこのバージョンが食い違ってしまった場合には、センターに要求を行い、センターが保持している各バージョンの予備の分配鍵情報を順次送付してもらい、秘密鍵を最新のバージョンまで順番にバージョンアップすることができる。また、端末に分配鍵を更新する部分が備えられている場合には、センターはバージョン合わせが必要となる端末に対して、最新の秘密鍵を個別に暗号化して送ってもよい。当該の端末では最新の秘密鍵を他の端末と共有すると同時に、この秘密鍵から次の秘密鍵と分散鍵情報を算出する。なお、この場合のバージョン合わせの方法では、端末から端末が最初保持している秘密鍵のバージョンの情報を知る必要がないし、センターから１回通知するだけでバージョンが整合する。
【００６８】
また、センターから端末に同報で通知される分配鍵情報が途中で誤りを含んでしまう場合がある。こういった場合の研究が秘密分散の分野でなされている。研究成果は、M.Tompa, and H.Woll, "How to Share a Secret with Cheaters", Journal of Cryptology, v.1, n.2, 1988, pp133-138などを参照。本発明はこのような研究成果もそのまま鍵共有方法に応用できる。
【００６９】
【発明の効果】
以上説明したように、本発明では例えば１個の端末を排除して残りの端末で同じ秘密鍵を獲得するために、センターはわずか１個のデータを送付するだけでよい。一般にはN個以下の端末を同時に排除するためには、センターはN個の情報を送ればよい。このことによりセンター側の処理の手間および通信量が削減され、また端末間での秘密鍵の更新のずれが少ないため不都合が生じにくい。
【００７０】
また、本発明の請求項４および５に対応した構成により、センター側では各端末の分配鍵情報をそれぞれ管理する必要はなく、実施の形態ではその元になる多項式だけを管理すればよい。そして必要な場合に多項式に端末の識別情報を代入することにより対応する端末の分配鍵情報を得ることができる。これによりセンター側の端末管理の負担が軽減される。
【００７１】
また、本発明の請求項６に対応した構成により、分配鍵情報は変換部と分配鍵情報更新部を用いて更新することにより、各端末においては１つの分配鍵情報を管理しておけばよい。これにより端末側およびセンター側の分配鍵情報の管理負担が軽減される。
【００７２】
また、本発明に示した構成により、高次の多項式を使用する代わりに、比較的低次の多項式を複数個用いることにより、安全性を保持しつつ端末における秘密鍵の算出のための計算量を削減することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態１における各端末の分配鍵情報を模式的に示す図
【図２】本発明の実施の形態１においてセンターが５つの端末のうち端末T1を排除する場合について示す図
【図３】本発明の実施の形態１における端末T3の内部の構成を示す図
【図４】本発明の実施の形態３における端末内での分配鍵情報の更新を可能にする構成を示す図
【図５】本発明の実施の形態４における各端末の分配鍵情報を模式的に示す図
【図６】本発明の実施の形態４においてセンターが５つの端末のうち端末T1と端末T2を同時に排除する場合について示す図
【図７】本発明の実施の形態４における端末T3の内部の構成を示す図
【図８】本発明の実施の形態５における各端末の分配鍵情報を模式的に示す図
【図９】本発明の実施の形態５においてセンターが端末T1と端末T2を同時に排除する場合について示す図
【図１０】本発明の実施の形態５における端末T3の内部の構成を示す図
【図１１】従来例１の鍵共有方法の構成を示す図
【図１２】従来例２の鍵共有方法の構成を示す図
【符号の説明】
１ 分配鍵情報格納部
２ 受信部
３ 秘密鍵算出部
４ 変換部
５ 分配鍵情報更新部
６ 識別情報格納部
１１ 分配鍵情報格納部
１２ 受信部
１３ 秘密鍵算出部
２１ 分配鍵情報格納部
２２ 中間秘密鍵算出部
２３ 分配鍵情報格納部
２４ 中間秘密鍵算出部
２５ 秘密鍵算出部
Claims (17)
- センター側装置と相異なる分配鍵情報を持つ複数の端末からなる鍵共有システムであって、
センター側装置は全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、kを正整数とするとき、特定のk個の端末の分配鍵情報を同報で全端末に通知する通知部を備え、
各端末は、分配鍵情報を格納する分配鍵情報格納部と、前記センター側装置から通知されたk個の分配鍵情報を受信する受信部と、前記受信部で受信したk個の分配鍵情報と、前記分配鍵情報格納部に格納される分配鍵情報の計k+1個の分配鍵情報がすべて相異なる場合にのみ、これらk+1個の分配鍵情報より前記特定のk個の端末を除く残りの端末で共通の秘密鍵を算出する秘密鍵算出部からなり、
前記各端末の分配鍵情報は、前記秘密鍵算出部に入力されるk+1個の分配鍵情報がすべて相異なる場合にのみ前記秘密鍵が復元できるように予め定められ各端末に分配されたものであることを特徴とする鍵共有システム。 - 前記センター側装置が、全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、kとmをそれぞれ正整数とするとき、特定のm個の端末の分配鍵情報と任意のk-m個の予備分配鍵情報の合計k個の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする請求項１記載の鍵共有システム。
- 前記センター側装置が、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、任意のk個の予備の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする請求項１記載の鍵共有システム。
- 前記各端末は相異なる識別情報を保持し、前記センター側装置は全端末分配鍵情報格納部の代わりに、前記秘密鍵を保持する秘密鍵格納部と、前記秘密鍵と任意の端末の識別情報を入力として、対応する端末の分配鍵情報を算出する分配鍵情報算出部を備えていることを特徴とする請求項１記載の鍵共有システム。
- 前記各端末は相異なる識別情報を保持し、前記センター側装置は前記予備分配鍵情報格納部の代わりに、前記秘密鍵を保持する秘密鍵格納部と、どの端末の識別情報とも異なる予備の情報と前記秘密鍵を入力として、前記予備の分配鍵情報を算出する予備分配鍵情報算出部を備えていることを特徴とする請求項２または請求項３記載の鍵共有システム。
- センター側装置と相異なる分配鍵情報を持つ複数の端末からなる鍵共有システムであって、
センター側装置は全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、kを正整数とするとき、特定のk個の端末の分配鍵情報を同報で全端末に通知する通知部を備え、
各端末は、分配鍵情報を格納する分配鍵情報格納部と、前記センター側装置から通知されたk個の分配鍵情報を受信する受信部と、前記受信部で受信したk個の分配鍵情報と、前記分配鍵情報格納部に格納される分配鍵情報の計k+1個の分配鍵情報がすべて相異なる場合にのみ、これらk+1個の分配鍵情報より前記特定のk個の端末を除く残りの端末で共通の第１の秘密鍵を算出する秘密鍵算出部と、前記第１の秘密鍵を全端末共通の変換方法で変換して第２の秘密鍵を求める変換部と、前記第２の秘密鍵から端末の新しい分配鍵情報を算出し、前記分配鍵情報格納部に格納して分配鍵情報を更新する分配鍵情報更新部からなり、
前記各端末の更新前の分配鍵情報は、前記秘密鍵算出部において入力されるk+1個の分配鍵情報がすべて相異なる場合にのみ前記第１の秘密鍵が復元できるように予め定められ各端末に分配されたものであり、前記分配鍵情報更新部によって更新された各端末の分配鍵情報は、前記と同様に前記第２の秘密鍵が復元できるように定められて各端末に分配されたものになり、前記各端末の変換部と分配鍵情報更新部は、外部より観察したり、変更できないものであり、前記センター側装置の全端末分配鍵情報格納部は、前記各端末で更新された分配鍵情報を格納することを特徴とする鍵共有システム。 - 前記変換部と分配鍵情報更新部を外部より観察したり、変更できない領域に備える代わりに、分配鍵情報更新部が、分配鍵情報を更新した後に前記第２の秘密鍵を消去することを特徴とする請求項６記載の鍵共有システム。
- 前記センター側装置が、全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、kとmをそれぞれ正整数とするとき、特定のm個の端末の分配鍵情報と任意のk-m個の予備分配鍵情報の合計k個の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする請求項６記載の鍵共有システム。
- 前記センター側装置が、前記全端末の分配鍵情報以外の予備の分配鍵情報を格納する予備分配鍵情報格納部と、任意のk個の予備の分配鍵情報を同報で全端末に通知する通知部を備えることを特徴とする請求項６記載の鍵共有システム。
- 前記センター側装置は前記全端末分配鍵情報格納部の代わりに、前記第１の秘密鍵を保持する秘密鍵格納部と、前記第１の秘密鍵と任意の端末の識別情報を入力として、対応する端末の分配鍵情報を算出する分配鍵情報算出部と、前記第１の秘密鍵を各端末の変換部と同じ変換方法で変換して第２の秘密鍵を求め、前記秘密鍵格納部に格納して第１の秘密鍵を更新するセンター側変換部を備えることを特徴とする請求項６記載の鍵共有システム。
- 前記センター側装置は前記予備分配鍵情報格納部の代わりに、前記第１の秘密鍵を保持する秘密鍵格納部と、どの端末の識別情報とも異なる予備の情報と前記第１の秘密鍵を入力として、前記予備の分配鍵情報を算出する予備分配鍵情報算出部と、前記第１の秘密鍵を各端末の変換部と同じ変換方法で変換して第２の秘密鍵を求め、前記秘密鍵格納部に格納して第１の秘密鍵を更新するセンター側変換部を備えることを特徴とする請求項８または請求項９記載の鍵共有システム。
- 前記各端末内の変換部およびセンター側変換部において、固定の変換の代わりに、外部から変更できる変換を用いることを特徴とする請求項６〜１１のいずれか１項に記載の鍵共有システム。
- 前記各端末内の分配鍵情報更新部で、前記第２の秘密鍵と前記端末の識別情報を用いて、前記端末の新しい分配鍵情報を算出することを特徴とする請求項６〜１１のいずれか１項に記載の鍵共有システム。
- 前記各端末内の分配鍵情報更新部で、前記第２の秘密鍵と端末の更新前の分配鍵情報を用いて、前記端末の新しい分配鍵情報を算出することを特徴とする請求項６〜９のいずれか１項に記載の鍵共有システム。
- 前記秘密鍵算出部において、入力のk+1個の分配鍵情報に誤りが生じえる場合や、k+1個より多い分配鍵情報が入力された場合に、その中で正しいk+1個の相異なる分配鍵情報を用いて秘密鍵を算出することを特徴とする請求項１〜１４のいずれか１項に記載の鍵共有システム。
- 前記秘密鍵にバージョン番号を付加し、センター側装置は各バージョンの予備の分配鍵情報を保管し、バージョンが一致していない端末に前記必要な分配鍵情報を通知することを特徴とする請求項１〜１５のいずれか１項に記載の鍵共有システム。
- 前記秘密鍵にバージョン番号を付加し、バージョンが一致していない端末に正しいバージョンの秘密鍵を個別に暗号化して通知することを特徴とする請求項６〜１４のいずれか１項に記載の鍵共有システム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP01854196A JP3620138B2 (ja) | 1996-02-05 | 1996-02-05 | 鍵共有システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP01854196A JP3620138B2 (ja) | 1996-02-05 | 1996-02-05 | 鍵共有システム |
Related Child Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2004263626A Division JP3861896B2 (ja) | 2004-09-10 | 2004-09-10 | 鍵共有システム |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH09212089A JPH09212089A (ja) | 1997-08-15 |
| JP3620138B2 true JP3620138B2 (ja) | 2005-02-16 |
Family
ID=11974501
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP01854196A Expired - Fee Related JP3620138B2 (ja) | 1996-02-05 | 1996-02-05 | 鍵共有システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3620138B2 (ja) |
Families Citing this family (24)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000031956A (ja) * | 1998-07-15 | 2000-01-28 | Nippon Telegr & Teleph Corp <Ntt> | 個別秘密情報共有交信方法及びシステム装置 |
| DE19847944A1 (de) * | 1998-10-09 | 2000-04-13 | Deutsche Telekom Ag | Verfahren zum Etablieren eines gemeinsamen Schlüssels zwischen einer Zentrale und einer Gruppe von Teilnehmern |
| US6813357B1 (en) | 1998-12-25 | 2004-11-02 | Matsushita Communication Industrial Co., Ltd. | Exclusive key sharing method |
| JP2002217891A (ja) * | 2001-01-22 | 2002-08-02 | Toshiba Corp | 秘密分散管理プログラム及びシステム |
| TWI246298B (en) | 2002-04-30 | 2005-12-21 | Ibm | Cryptographic communication system, key distribution server and terminal device constituting the system, and method for sharing key |
| JP4576824B2 (ja) * | 2003-10-14 | 2010-11-10 | ソニー株式会社 | 情報処理装置および情報処理方法 |
| JP4708713B2 (ja) * | 2004-02-10 | 2011-06-22 | エヌ・ティ・ティ・コミュニケーションズ株式会社 | 機密情報管理システム、機密情報管理方法、および機密情報管理プログラム |
| WO2005076518A1 (en) | 2004-02-10 | 2005-08-18 | Ntt Communications Corporation | Secret information management scheme based on secret sharing scheme |
| KR100561438B1 (ko) * | 2004-07-09 | 2006-03-17 | 삼성전자주식회사 | 라그랑즈 보간법을 이용한 권한 해제 방법 및 이를 이용한콘텐츠 송신 방법 |
| JP4523847B2 (ja) * | 2005-01-26 | 2010-08-11 | 日本電信電話株式会社 | コミュニケーション端末、フルメッシュ網において各端末が他の全端末間のコネクション接続を確実に確認する方法 |
| US7690026B2 (en) * | 2005-08-22 | 2010-03-30 | Microsoft Corporation | Distributed single sign-on service |
| EP1955472B1 (en) | 2005-12-01 | 2016-06-29 | Telefonaktiebolaget LM Ericsson (publ) | Key management |
| JP2006174519A (ja) * | 2006-03-17 | 2006-06-29 | Fujitsu Ltd | セキュリティ方法及びセキュリティ装置 |
| JP4867425B2 (ja) * | 2006-03-27 | 2012-02-01 | ソニー株式会社 | 情報処理装置、および情報処理方法、並びにコンピュータ・プログラム |
| JP5043408B2 (ja) * | 2006-11-27 | 2012-10-10 | 三菱電機株式会社 | 鍵管理サーバ、端末、鍵共有システム、鍵配信プログラム、鍵受信プログラム、鍵配信方法及び鍵受信方法 |
| JP4916915B2 (ja) * | 2007-02-28 | 2012-04-18 | Ｋｄｄｉ株式会社 | 端末装置、データ管理装置およびコンピュータプログラム |
| FR2925732B1 (fr) * | 2007-12-21 | 2010-02-12 | Sagem Securite | Generation et utilisation d'une cle biometrique |
| US8151333B2 (en) | 2008-11-24 | 2012-04-03 | Microsoft Corporation | Distributed single sign on technologies including privacy protection and proactive updating |
| JP5608509B2 (ja) * | 2010-10-21 | 2014-10-15 | Ｋｄｄｉ株式会社 | 鍵管理システム、鍵管理方法及びコンピュータプログラム |
| JP5644453B2 (ja) * | 2010-12-08 | 2014-12-24 | 富士通セミコンダクター株式会社 | 認証システム、及び認証方法 |
| JP5911289B2 (ja) * | 2011-12-16 | 2016-04-27 | セコム株式会社 | 鍵管理システム |
| KR20190047143A (ko) | 2013-07-31 | 2019-05-07 | 닛본 덴끼 가부시끼가이샤 | Mtc 그룹 키 관리를 위한 디바이스들 및 방법 |
| GB201711878D0 (en) * | 2017-07-24 | 2017-09-06 | Nchain Holdings Ltd | Computer - implemented system and method |
| KR20240150285A (ko) * | 2023-04-07 | 2024-10-15 | 한양대학교 산학협력단 | 멀티-컴파트먼트 기반의 임계 비밀 공유 및 복원 방법 |
-
1996
- 1996-02-05 JP JP01854196A patent/JP3620138B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH09212089A (ja) | 1997-08-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3620138B2 (ja) | 鍵共有システム | |
| CN110557245B (zh) | 用于spdz的容错和安全多方计算的方法和系统 | |
| CN110380844B (zh) | 一种量子密钥分发方法、设备及存储介质 | |
| JP6363032B2 (ja) | 鍵付替え方向制御システムおよび鍵付替え方向制御方法 | |
| KR100404694B1 (ko) | 비밀 키 생성 시스템 | |
| CN113992330B (zh) | 一种基于代理重加密的区块链数据受控共享方法及系统 | |
| US8886931B2 (en) | Key sharing system, communication terminal, management device, key sharing method, and computer program | |
| CN103873236B (zh) | 一种可搜索加密方法及设备 | |
| CN112183767A (zh) | 一种多密钥下模型聚合的联邦学习方法及相关设备 | |
| JP3794457B2 (ja) | データの暗号化復号化方法 | |
| CN117494177A (zh) | 一种基于隐私计算的数据隐匿统计查询的方法和系统 | |
| US20240235832A1 (en) | Selective data sharing | |
| JP4216914B2 (ja) | ネットワークシステム | |
| WO2000039957A1 (en) | Exclusive key sharing method | |
| JP6400743B2 (ja) | 端末装置、データベースサーバおよび計算システム | |
| JP3861896B2 (ja) | 鍵共有システム | |
| CN114297721B (zh) | 信息处理方法、信息处理装置、区块链平台和存储介质 | |
| JPWO2017149686A1 (ja) | 鍵生成装置、計算機システム、および暗号統計処理方法 | |
| JP3233605B2 (ja) | 鍵更新方法 | |
| JP2865654B1 (ja) | 鍵更新方法 | |
| JPH11252065A (ja) | 暗号鍵の生成装置 | |
| JP2948605B2 (ja) | 暗号鍵共通の暗号通信用端末 | |
| Pareek et al. | Extended hierarchical key assignment scheme (E-HKAS): how to efficiently enforce explicit policy exceptions in dynamic hierarchies | |
| JP2000196581A (ja) | 排他的鍵共有法 | |
| US20240364513A1 (en) | A Computer-Implemented Method For Storing A Payload Data In Nodes Of A DLT Network |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040406 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20040727 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040910 |
|
| A911 | Transfer to examiner for re-examination before appeal (zenchi) |
Free format text: JAPANESE INTERMEDIATE CODE: A911 Effective date: 20040915 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20041026 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20041108 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20071126 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081126 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091126 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091126 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101126 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111126 Year of fee payment: 7 |
|
| LAPS | Cancellation because of no payment of annual fees |