JP3620138B2 - Key sharing system - Google Patents
Key sharing system 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の内部の構成を示す図
【図１１】従来例１の鍵共有方法の構成を示す図
【図１２】従来例２の鍵共有方法の構成を示す図
【符号の説明】
１ 分配鍵情報格納部
２ 受信部
３ 秘密鍵算出部
４ 変換部
５ 分配鍵情報更新部
６ 識別情報格納部
１１ 分配鍵情報格納部
１２ 受信部
１３ 秘密鍵算出部
２１ 分配鍵情報格納部
２２ 中間秘密鍵算出部
２３ 分配鍵情報格納部
２４ 中間秘密鍵算出部
２５ 秘密鍵算出部[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a system for performing cryptographic communication in a communication system including a center and a plurality of terminals, and more particularly to an apparatus for securely delivering a common secret key from a center to a plurality of terminals. Further, the present invention relates to a key sharing apparatus that reduces the amount of communication from the center and shares a secret key with all terminals other than the terminals specified by the center.
[0002]
[Prior art]
In a communication system composed of a center and a plurality of terminals, a case is considered in which a plurality of terminals form a group under the management of the center, and the same secret key is shared by the group to perform broadcast encrypted communication. Information encrypted using the group secret key can be decrypted only by terminals in the group having the same secret key. By the way, there may be a case where it is desired to exclude a specific terminal from this group. This is the case, for example, when a certain terminal in the group is stolen and fraud such as eavesdropping on encrypted communication using the terminal or transmission of fake information is considered. At this time, the center managing the secret key needs to remove the stolen terminal as soon as possible and share a new secret key only with the remaining terminals.
[0003]
(Conventional example 1)
FIG. 11 shows a key sharing method in the first conventional example for sharing key data with terminals other than those specified by the center. In this figure, five terminals T1,..., T5 hold unique unique keys k1,..., K5, respectively, and the center C manages the unique keys of all terminals. For example, in order for the center to eliminate the terminal T1 and distribute a new common secret key to the other T2,..., T5, the center first generates a secret key K, which is assigned to k2,. And then delivered to T2,..., T5, respectively. Each terminal decrypts this using a unique key and obtains a secret key K. In the figure, for example, Ek2 (K) is a ciphertext obtained by encrypting K with the unique key k2. Since the data on the communication path is encrypted with the unique keys of the terminals T2 to T5, the distribution key information K generated by the center cannot be acquired even if the terminal T1 sniffs the communication data.
[0004]
However, in this method, in general, in order to eliminate one terminal from N terminals, the center must perform encryption N-1 times and transmit N-1 data. This work becomes very burdensome for the center when the group grows. Also, it is necessary to suspend operations such as cryptographic communications within the group until all stations are updated, but this is a serious problem if the operation suspension period is long until distribution to N-1 stations is completed.
[0005]
(Conventional example 2)
FIG. 12 shows a key sharing method in the second conventional example. In this method, the terminals in Conventional Example 1 are grouped to reduce the center-side encryption effort and the amount of transmission data. In this figure, five terminals are divided into two groups of T1 and T2 and the remaining three terminals, and share common group keys G1 and G2. For example, when the center excludes the terminal T1, the generated distribution key information K is encrypted using the unique key k2 of T2 for the terminal T2, and the group key is used for the remaining T3, T4, and T5. The distribution key information K is encrypted and delivered using G2. Each of the terminals T3, T4, and T5 uses the group key G2 to decrypt it and acquire the distribution key information K. It should be noted that grouping of terminals may be performed in a multiplexed or hierarchical manner.
[0006]
However, in the second conventional example, in addition to the unique key unique to each terminal, the group key needs to be managed on the center side and the terminal side. Furthermore, even in the second conventional example, as in the first conventional example, as the number of terminals increases, the burden of center encryption and data transmission increases, and the business suspension period until all stations are updated becomes longer. Become.
[0007]
[Problems to be solved by the invention]
For example, consider a case where one terminal is excluded from 1000 terminals and a new common secret key is shared by the remaining 999 terminals. At this time, in the first conventional example, it is necessary to perform 999 times of encryption processing and 999 times of ciphertext transmission. In the second conventional example, when 1000 terminals are divided into two groups of 500, for example, the group including the terminals to be excluded is 499 times for each terminal, and the other group is A total of 500 encryption processes and transmission of ciphertext are required in a group key. In any case, these operations are very burdensome for the center. In addition, the business suspension period until all stations are updated becomes longer.
[0008]
Further, in the second conventional example, on the center side and the terminal side, it is necessary to manage many group keys together with the unique key of each terminal depending on the grouping method.
[0009]
SUMMARY OF THE INVENTION In view of the above, the present invention aims to realize a key sharing method characterized in that only a specific terminal is excluded and shared key information is shared with other terminals, and characterized by the following points. .
[0010]
(1) The amount of communication from the center to the terminal is small.
The encryption processing at the center is less and the amount of ciphertext sent is small.
The business suspension period until all stations are updated is short.
[0011]
(2) The terminal has few secret keys.
There are few keys for the terminal to manage at the center.
There are few keys to manage in the terminal.
[0012]
[Means for Solving the Problems]
Key sharing in the first configuration of the present inventionsystemThe centerSide deviceConsisting of multiple terminals with different distribution key informationSide deviceIs provided with an all-terminal distribution key information storage unit for storing distribution key information for all terminals, and a notification unit for notifying all terminals of distribution key information for a specific k number of terminals when k is a positive integer. Each terminal includes a distribution key information storage unit for storing distribution key information, and the centerSide deviceReceiving unit for receiving k pieces of distributed key information notified from, k pieces of distributed key information received by the receiving unit, and k + 1 pieces of distributed key information stored in the distributed key information storage unit Only when the distribution key information of all is different from each other, comprises a secret key calculation unit for calculating a secret key common to the remaining terminals excluding the specific k terminals from these k + 1 distribution key information, The distribution key information of each terminal is predetermined and distributed to each terminal so that the secret key can be restored only when the k + 1 pieces of distribution key information input to the secret key calculation unit are all different. It is characterized by being.
[0013]
Key sharing in the second configuration of the present inventionsystemIs the center in the first configurationSide deviceAre all terminal distribution key information storage units for storing distribution key information for all terminals, spare distribution key information storage units for storing spare distribution key information other than the distribution key information for all terminals, and k and m respectively. When it is a positive integer, it is provided with a notification unit for notifying all terminals by broadcast of a total of k pieces of distribution key information of a specific m number of terminals and an arbitrary km pieces of spare distribution key information And
[0014]
Key sharing in the third configuration of the present inventionsystemIs the center in the first configurationSide deviceComprises a spare distribution key information storage unit for storing spare distribution key information other than the distribution key information of all terminals, and a notification unit for notifying all terminals of any k spare distribution key information by broadcast. It is characterized by that.
[0015]
Key sharing in the fourth configuration of the present inventionsystemEach terminal in the first configuration holds different identification information, and the centerSide deviceIs a secret key storage unit that holds the secret key instead of the all-terminal distribution key information storage unit, and a distribution key that calculates the distribution key information of the corresponding terminal by using the secret key and identification information of an arbitrary terminal as input. An information calculation unit is provided.
[0016]
Key sharing in the fifth configuration of the present inventionsystemThe terminals in the second and third configurations hold different identification information, and the centerSide deviceCalculates the spare distribution key information using the secret key storage unit that holds the secret key instead of the spare distribution key information storage unit, the spare information different from the identification information of any terminal, and the secret key as inputs. And a preliminary distribution key information calculation unit.
[0017]
Key sharing in the sixth configuration of the present inventionsystemThe centerSide deviceConsisting of multiple terminals with different distribution key informationSide deviceIs provided with an all-terminal distribution key information storage unit for storing distribution key information for all terminals, and a notification unit for notifying all terminals of distribution key information for a specific k number of terminals when k is a positive integer. Each terminal includes a distribution key information storage unit for storing distribution key information, and the centerSide deviceReceiving unit for receiving k pieces of distributed key information notified from, k pieces of distributed key information received by the receiving unit, and k + 1 pieces of distributed key information stored in the distributed key information storage unit A secret key calculation unit that calculates a first secret key common to the remaining terminals excluding the specific k terminals from these k + 1 distribution key information only when the distribution key information of A conversion unit for converting the first secret key by a conversion method common to all terminals to obtain a second secret key; calculating new distribution key information of the terminal from the second secret key; and the distribution key information A distribution key information update unit that updates the distribution key information stored in the storage unit, and the distribution key information before the update of each terminal includes k + 1 pieces of distribution key information input in the secret key calculation unit The first secret key is predetermined and distributed to each terminal so that the first secret key can be restored only when they are all different. The distribution key information of each terminal updated by the distribution key information update unit is distributed to each terminal so that the second secret key can be restored as described above. The conversion unit and the distribution key information update unit of the above cannot be observed or changed from the outside, and the centerSide deviceThe all-terminal distributed key information storage unit stores the distributed key information updated in each terminal.
[0018]
Key sharing in the seventh configuration of the present inventionsystemInstead of observing the conversion unit and the distribution key information update unit in the sixth configuration from the outside or preparing for an area that cannot be changed, the distribution key information update unit updates the distribution key information after the second secret It is characterized by deleting the key.
[0019]
Key sharing in the eighth configuration of the present inventionsystemIs the center in the sixth configurationSide deviceAre all terminal distribution key information storage units for storing distribution key information for all terminals, spare distribution key information storage units for storing spare distribution key information other than the distribution key information for all terminals, and k and m respectively. When it is a positive integer, it is provided with a notification unit for notifying all terminals by broadcast of a total of k pieces of distribution key information of a specific m number of terminals and an arbitrary km pieces of spare distribution key information And
[0020]
Key sharing in the ninth configuration of the present inventionsystemIs the center in the sixth configurationSide deviceComprises a spare distribution key information storage unit for storing spare distribution key information other than the distribution key information of all terminals, and a notification unit for notifying all terminals of any k spare distribution key information by broadcast. It is characterized by that.
[0021]
Key sharing in the tenth configuration of the present inventionsystemIs the center in the sixth configurationSide deviceInstead of the all terminal distribution key information storage unit, the secret key storage unit that holds the first secret key, the first secret key and the identification information of an arbitrary terminal as inputs, and distribution of the corresponding terminal A distribution key information calculation unit for calculating key information, a second secret key obtained by converting the first secret key by the same conversion method as the conversion unit of each terminal, and stored in the secret key storage unit The center side conversion part which updates 1 private key is provided, It is characterized by the above-mentioned.
[0022]
Key sharing in the eleventh configuration of the present inventionsystemAre the centers in the eighth and ninth configurations.Side deviceInstead of the spare distribution key information storage unit, the secret key storage unit holding the first secret key, the spare information different from the identification information of any terminal, and the first secret key as inputs, A preliminary distribution key information calculation unit that calculates the distribution key information of the terminal, and a second secret key obtained by converting the first secret key by the same conversion method as the conversion unit of each terminal and stored in the secret key storage unit And a center side conversion unit for updating the first secret key.
[0023]
Key sharing in the twelfth configuration of the present inventionsystemIn the sixth to eleventh configurations, the conversion unit and the center side conversion unit in each terminal use conversion that can be changed from the outside instead of fixed conversion.
[0024]
Key sharing in the thirteenth configuration of the present inventionsystemIn the sixth to eleventh configurations, the distribution key information update unit in each terminal calculates new distribution key information of the terminal using the second secret key and the identification information of the terminal. And
[0025]
Key sharing in the fourteenth configuration of the present inventionsystemIs a distribution key information updating unit in each of the terminals in the sixth to ninth configurations, using the second secret key and the distribution key information before updating the terminal, to calculate new distribution key information of the terminal It is characterized by that.
[0026]
First of the present invention15Key sharing in the configurationsystemIs the first14In the secret key calculation unit in the configuration of the above, if an error can occur in the input k + 1 pieces of distributed key information, or if more than k + 1 pieces of distributed key information are input, the correct k + A secret key is calculated using one piece of different distributed key information.
[0027]
First of the present invention16Key sharing in the configurationsystemIs the first15A version number is added to the secret key in the configuration ofSide deviceIs characterized by storing spare distribution key information of each version and notifying the necessary distribution key information to a terminal whose version does not match.
[0028]
First of the present invention17Key sharing in the configurationsystemIs the 6th ~14A version number is added to the secret key in the configuration, and a correct version of the secret key is individually encrypted and notified to a terminal whose version does not match.
[0029]
DETAILED DESCRIPTION OF THE INVENTION
For the purpose of eliminating a certain terminal in the group and sharing a new secret key with the remaining terminals, the present invention newly introduces a known technique called a secret sharing method or (k, n) threshold method. It is applied. The explanation of the secret sharing method and the (k, n) threshold method is detailed in, for example, Section 6.2 of Eiji Okamoto “Introduction to Cryptography”, Kyoritsu Shuppan (1993). The secret sharing method is conventionally known as a method of storing a highly confidential key. For example, the key is divided into two and stored by two people. When the two are used, the two cannot be used. Is. The (k, n) threshold method generalizes this and divides the secret key into n (hereinafter, the result of dividing the secret key will be referred to as distributed key information). The original secret key can be restored by collecting any k pieces from the above, and the original information cannot be obtained at all if less than k pieces are collected.
[0030]
The embodiment of the present invention will be described below using an example using a polynomial of the (k, n) threshold method.
[0031]
(Embodiment 1)
In the present invention, it is composed of a center and a plurality of terminals, and each terminal holds different distribution key information. FIG. 1 is a diagram schematically showing distribution key information of each terminal in the first embodiment. In this embodiment, p is a prime number, a, b, x is a remainder element under the modulus p, and a first-order polynomial f (x) = ax + b modp on the modulus p is considered, and each terminal is identified. The y coordinate value with the information as the x coordinate is used as the distribution key information of each terminal. For example, the distribution key information of a terminal having IDi as identification information is f (IDi), and the distribution key information of a terminal having IDj as identification information is f (IDj). Assume that these are distributed in advance to each terminal. Here, the identification information of each terminal is assumed to be an integer from 0 to p-1. Further, since the first order polynomial f (x) is obtained by modulo the prime number p, the distribution key information of each terminal is an integer value from 0 to p−1, although it is not represented in FIG. Here, since only one point of the first-order polynomial f (x) is distributed as the distribution key information to each terminal, the distribution key information of other terminals can be obtained from its own distribution key information unless the two terminals collide. Cannot be analogized.
[0032]
In the first embodiment, the center side manages the identification information and distribution key information of each terminal. In the management at the center, the distribution key information itself of each terminal may be managed in a database, but it is sufficient to store only the first-order polynomial f (x). That is, the distribution key information of each terminal can be obtained whenever necessary by substituting the identification information of each terminal into this equation.
[0033]
The part so far is the same as the method of distributing the secret key in the (k, n) threshold method, particularly when k is 2.
[0034]
FIG. 2 shows a case where only the terminal T1 is excluded from the five terminals and the common secret key is shared by the remaining terminals as in the conventional example. The center first obtains the distribution key information of the terminal T1 to be excluded by inputting the identification information of the terminal T1 into the stored first order polynomial. The obtained distribution key information of the terminal T1 is transmitted to each terminal by broadcast. As an example, FIG. 3 shows an internal configuration of the terminal T3. 1 is a storage unit for the distribution key information f (ID3) of the terminal T3, 2 is a reception unit for receiving the distribution key information f (ID1) of the terminal T1 sent from the center, and 3 is a storage with the received distribution key information. This is a secret key calculation unit that obtains a secret key using the distributed key information f (ID3). In the secret key calculation unit, each coefficient of the corresponding first-order polynomial from two different coordinate points in FIG.(Equation 1)Find and solve. The following(Equation 1)Computes over the modulus p.
[0035]
[Expression 1]
In the figure, the secret key calculation unit outputs a as a secret key that is shared by the remaining terminals by excluding the terminal T1, and this is expressed as b or a using the slopes a and b obtained by solving the above equation. + b may be a secret key. On the other hand, although the terminal T1 has the same configuration as that of FIG. 3, only the secret key calculation unit of the terminal T1 has the same distribution key information held by itself and the distribution key information distributed from the center, f (ID1). In FIG. 1, only the coordinates of one point are obtained, and the first order polynomial, that is, the slope a and the intercept b cannot be determined. Therefore, the secret key cannot be shared.
[0037]
Here, for the sake of simplicity, a case has been described in which there are five terminals in total and only terminal T1 is excluded, but in the same way, any one terminal can be excluded from any number of terminals. . Therefore, in the key sharing method in the first embodiment, by transmitting data only once from the center, it is possible to exclude any one terminal and share the secret key with the remaining terminals. In the first embodiment, each terminal only needs to store one piece of distribution key information.
[0038]
(Embodiment 2)
Next, consider a case where the terminal T1 is excluded first and the terminal T2 is subsequently excluded. For example, when 5 terminals share a common secret key and perform encryption communication within the group, the terminal T1 is first stolen, and a new common secret key is assigned to the remaining 4 terminals accordingly. In this scenario, the terminal T2 is also stolen.
[0039]
In the first embodiment, each terminal holds distribution key information corresponding to one primary polynomial f (x). In this embodiment, in addition to this, distributed key information g (IDi) corresponding to another independent first order polynomial g (x) = cx + d modp2 is also stored in advance in each terminal. This is because all the information about f (x) is released at the stage when the terminal T1 is excluded, so that the distribution key information corresponding to the new polynomial g (x) is necessary to eliminate the terminal T2. Because.
[0040]
By the way, two cases can be considered as methods of eliminating the terminal T2 at this time. In the first case, when the terminal T2 is excluded, the terminal T1 is revived as a regular terminal, and the remaining four terminals excluding T2 share a new secret key. In the second case, when the terminal T2 is excluded, the terminal T1 previously excluded is continuously excluded, and the remaining three terminals excluding T1 and T2 share a new secret key. In the former case, in order to exclude the terminal T2, g (ID2) may be broadcast and the secret key may be obtained using the coefficients c and d. In terminals other than the terminal T2 including the terminal T1, the coefficients c and d of g (x) can be obtained. On the other hand, since only terminal T2 cannot determine g (x), a secret key cannot be obtained. Next, the latter case will be described. In this case, the secret key may be obtained using both the coefficients a and b of f (x) and the coefficients c and d of g (x). Instead of the coefficients a and b of f (x), the original secret key shared by the remaining terminals may be used by excluding the initial terminal T1. The terminals T3 to T5 can calculate any of the above a, b, c, and d, and a new secret key is obtained. On the other hand, since the terminal T1 cannot obtain the coefficients a and b of f (x) and the terminal T2 cannot obtain the coefficients c and d of g (x), both can be excluded.
[0041]
In the second embodiment described above, the number of terminal exclusions is two (first T1, then T2 is excluded), but in order to further exclude terminals subsequently, the number of exclusions depends on the number of exclusions. It is necessary to store the distributed key information in each terminal in advance. As described above, this is because the distribution key information used for the previous terminal exclusion cannot be used for the next terminal exclusion.
[0042]
(Embodiment 3)
In the second embodiment, polynomials corresponding to the number of times of terminal exclusion are selected in advance, and distribution key information corresponding to this is stored in each terminal. Each time a terminal is excluded, this is used in turn, and a new secret key is shared with the terminals other than the excluded terminal. In contrast, the third embodiment is a method in which one piece of distribution key information is stored and updated every time a terminal is excluded to obtain new distribution key information at each terminal. Compared to the second embodiment, the storage area for the distribution key information in the terminal can be reduced. In the second embodiment, the number of terminal exclusions is finite depending on the number of distribution key information stored in advance, whereas in the third embodiment, this restriction is not present. FIG. 4 shows a configuration of the terminal T3, and a part for updating the distribution key information is added to FIG. 1, 2, and 3 are the same as FIG. The terminal T3 obtains the slope a and intercept b of the first-order polynomial f (x) as the output of the secret
[0043]
In this case, the same conversion is also performed on the center side, and the previous f (x) is updated to a new first-order polynomial f ′ (x). When the terminal T2 is further excluded thereafter, the center acquires the distribution key information f ′ (ID2) of the terminal T2 from the new first-order polynomial f ′ (x) and notifies the terminal of this by broadcast. . In the terminal T3 not excluded, the coefficient a of the first-order polynomial f ′ (x) using the distribution key information f ′ (ID3) stored in the distribution key information storage unit and the information f ′ (ID2) sent from the center. Find ', b' and calculate a new secret key from them. On the other hand, the terminal T2 cannot determine the first-order polynomial f ′ (x) because the stored distribution key information and the distribution key information from the center overlap. Also, the terminal T1 excluded first cannot acquire the coefficient a'b 'of the new first-order polynomial f' (x) because it cannot acquire the coefficient a, b of the first first-order polynomial f (x). Therefore, when the terminal T2 is excluded, the terminal T1 is also continuously excluded.
[0044]
Although the case where the number of terminal exclusions is 2 has been described above, the same applies to the case where the number of terminal exclusions is 2 or more, and the coefficients of the polynomial obtained in the secret key calculation unit are sequentially converted to obtain the next polynomial and new distribution key information is obtained. . Therefore, in this case, no matter how many times the terminal is excluded, each terminal has only one distribution key information, and the management at the center is only the first-order polynomial at that time.
[0045]
As described above, in Embodiments 1 to 3 described above, the case where only one terminal is excluded at a time has been described, but in the following Embodiments 4 and 5, a method for simultaneously removing a plurality of terminals is described. State.
[0046]
(Embodiment 4)
FIG. 5 is a diagram schematically showing the distribution key information of each terminal in the fourth embodiment. In this example, a prime polynomial p modulo a quadratic polynomial on itF (x) = ax 2 + bx + c modpThus, the y coordinate value with the identification information of each terminal as the x coordinate is used as the distribution key information of each terminal. For example, the distribution key information of a terminal having IDi as identification information is F (IDi), and these are distributed in advance to each terminal. The terminal distribution key information is an integer value from 0 to p−1 although F (x) is modulo the prime number p, which is not represented in FIG. The center side manages the distribution key information and identification information of each terminal. As a management method, each distribution key information may be stored in a database, but only the above-mentioned second order polynomial may be stored, and the distribution key information of the corresponding terminal may be calculated whenever necessary using the identification information of each terminal. Good.
[0047]
FIG. 6 shows a case where the terminal T1 and the terminal T2 are simultaneously excluded from the five terminals, and the remaining terminals share the secret key. The center first obtains the distribution key information of the terminals T1 and T2 to be excluded by inputting the respective identification information into the stored second order polynomial. Then, the obtained distribution key information F (ID1) and F (ID2) is transmitted to each terminal by broadcast. As an example, FIG. 7 shows an internal configuration of the terminal T3. Reference numeral 11 denotes a storage unit for the distribution key information F (ID3) of the terminal T3.
The specific calculation for obtaining a, b, c is as follows:(Equation 2)It is as follows. The following(Equation 2)Computes over the modulus p.
[0048]
[Expression 2]
Similarly, the terminals T4 and T5 obtain coefficients a, b, and c, and calculate the same secret key as that of the terminal T3. In FIG. 7, a is a secret key, but this may be a, a + b, a + b-c, or the like. On the other hand, although the terminals T1 and T2 have the same configuration as that of FIG. 7, the secret key calculation units of the terminals T1 and T2 overlap the distribution key information held by themselves and the distribution key information distributed from the center. In FIG. 5, only the coordinates of two points are acquired, and the second order polynomial cannot be determined.
[0050]
Thus, in the key sharing method in the first embodiment, by transmitting two data from the center, two terminals can be excluded at the same time, and the remaining terminals can share the secret key.
[0051]
Embodiment 4 excludes two terminals at the same time, but it is also possible to exclude only one terminal. For this purpose, the center asks for spare distribution key information. That is, some values not assigned to the identification information of each terminal in the x coordinate in the graph of FIG. 5 are reserved in advance. The corresponding coordinate point is used as spare distribution key information. The distribution key information may be stored in advance in a database, or only the polynomial may be stored and the distribution key information may be obtained each time. For example, when the center excludes only the terminal T1, any one of the distribution key information of the terminal T1 and the spare distribution key information is notified by broadcast. A terminal other than the terminal T1 obtains a secret key using its own distributed key information, the distributed key information of the terminal T1 sent from the center, and spare information. Only the terminal T1 cannot obtain the secret key because its own distributed key information and one of the information sent from the center overlap.
[0052]
Further, by using the above-mentioned spare distribution key information, it is possible to update only the secret key without excluding any terminal. That is, in the example of the fourth embodiment, both pieces of information notified from the center to the terminal by broadcast are both reserved distribution key information. This allows all terminals to calculate a new secret key. In this case, the terminal side only needs to perform the same process without being aware of whether it is a periodic update of the secret key or an update for excluding the terminal.
[0053]
In Embodiment 4 described above, a quadratic polynomial is used to eliminate up to two terminals simultaneously. In general, an Nth order polynomial is used to exclude up to N terminals. At this time, the number of data broadcast from the center to the terminal is N.
[0054]
(Embodiment 5)
Next, another method for simultaneously excluding a plurality of terminals will be described as a fifth embodiment. FIG. 8 is a diagram schematically showing the distribution key information of each terminal in the fifth embodiment. In this example, the prime numbers p1 and p2 are modulo and two first order polynomials (f (x) = ax + b modp1, g (x) = cx + d modp2) are considered, and each terminal in each polynomial The y coordinate value with the identification information as the x coordinate is used as the distribution key information of each terminal. For example, the distribution key information of terminals having IDi as identification information is f (IDi) and g (IDi), and these are distributed to each terminal in advance. The former is referred to as first distribution key information of the terminal, and the latter is referred to as second distribution key information. On the center side, the first order polynomials f (x) and g (x) are stored.
[0055]
FIG. 9 shows a case where the terminals T1 and T2 are simultaneously excluded from the five terminals and the secret keys are shared by the remaining terminals as in the fourth embodiment. The center first inputs the terminal identification information corresponding to the stored first order polynomials f (x), g (x), so that the first distribution key information f (ID1) of the terminal 1 and the
[0056]
By the way, the terminal 1 cannot obtain the first intermediate secret key. Also, the
[0057]
In this example, the center delivered f (ID1) and g (ID2) to all terminals by broadcast and excluded
[0058]
In the fifth embodiment, the fact that the fourth embodiment is realized by using a second-order polynomial is realized by using two first-order polynomials. In Embodiment 4, it is necessary to solve a quadratic polynomial from three coordinates in the secret key calculation unit.(Equation 2)It is necessary to perform the relatively complicated calculation shown in. On the other hand, in the fifth embodiment, it is sufficient to solve the first-order polynomial for each intermediate secret key ((Equation 1)In total, the amount of calculation can be reduced as compared with the fourth embodiment. In particular(Equation 1)It takes 2 multiplications and 1 division (addition / subtraction is negligible compared to the amount of multiplication and division, so it is not considered here)(Equation 2)This calculation takes 23 multiplications and 1 division. Therefore, the number of multiplications in the fifth embodiment is much smaller than that in the fourth embodiment.
[0059]
In the fifth embodiment, it is possible to exclude only one terminal. There are three methods. The first method uses, for example, only f (x). At this time, in FIG. 10, the output of the first intermediate secret key calculation unit becomes the secret key. The second method may be, for example, a method of transmitting terminal distribution key information to be excluded at f (x) and transmitting spare distribution key information at g (x). In this case, all the terminals can obtain the second intermediate secret key, but only the excluded terminal cannot calculate the first intermediate secret key, and thus cannot obtain the final secret key. In the case of the second method, the terminal side may always perform the same process without being aware of whether the number of terminals to be excluded is only one terminal or two terminals. In the third method, two pieces of distributed key information f (ID1) and g (ID1) of the terminal T1 are sent to exclude only the terminal T1. Terminals other than terminal T1 can obtain two pieces of intermediate common data and calculate a secret key therefrom. Only the terminal T1 cannot calculate both of the intermediate common data.
[0060]
The third method can be regarded as a method for improving the first embodiment and reducing the calculation amount of the secret key calculation in the terminal. In the method described in the first embodiment, the secret information is an integer of 0 or more and p−1 or less, and it is necessary to increase p in order to ensure the security against this brute force attack. However, when the modulus p is increased, all the calculations for calculating the secret key are large, and the amount of calculation increases. The increase in the calculation amount increases exponentially compared with the size of p. For example, when p is a 32-bit value, the amount of calculation for 32-bit width multiplication is four times the amount of calculation for 16-bit width multiplication. Therefore, in order to reduce the amount of calculation, a plurality of relatively small methods p ′ are provided instead of the large method p, and a first order polynomial is considered. Each terminal holds coordinates corresponding to each first-order polynomial as distribution key information. The center notifies a plurality of distributed key information of the terminals to be excluded by broadcast, and each terminal obtains an intermediate secret key from each terminal and combines them to obtain a secret key of about a large modulus p. This makes it possible to reduce the processing amount and increase the speed.
[0061]
In the fifth embodiment, two first order polynomials are used to eliminate two terminals simultaneously. In general, N first order polynomials may be used to eliminate N terminals simultaneously. A plurality of relatively low-order polynomials may be used instead of the first-order polynomial.
[0062]
In the fourth and fifth embodiments, the update part of the distribution key information of each terminal described in the third embodiment can be added.
[0063]
In the above five embodiments, the distribution key information of each terminal is the coordinates of the polynomial on the prime field, but nothing is limited to this. For example, this can be expanded to the coordinates of a polynomial over a general finite field such as an extension field of a prime field. It is only necessary that a common key can be shared between terminals only when there are k + 1 pieces of different distributed key information. For this part, known techniques relating to secret sharing and the (k, n) threshold method are applied.
[0064]
In addition, although the conversion unit of the third embodiment (FIG. 4) is realized by performing fixed secret conversion on each coefficient of the polynomial, any conversion unit may be used as long as it converts the secret key to fixed. This conversion itself may be changed from the outside.
[0065]
In the distribution key information update unit of the third embodiment, the distribution key information is calculated based on the identification information of each terminal. However, even if new distribution key information is calculated based on the distribution key information before the update. good. However, in this case, it is necessary to take care that the distribution key information does not overlap for each terminal.
[0066]
In particular, when the distribution key information is automatically updated in the terminal as in the second embodiment, the secret key shared by each terminal is not necessarily designated by the center each time. Therefore, when the center wants to specify the secret key K, the center encrypts it with the secret key holding the K, and sends it to each terminal by broadcast simultaneously with the distribution key information of the terminals to be excluded. Each terminal uses the output of the secret key calculation unit to decrypt the data sent from the center and use the result as a secret key.
[0067]
In addition, when the secret key is updated by broadcasting as described above, there may be a terminal that cannot acquire the communication from the center for some reason and cannot be updated. Therefore, a version number may be added to each distribution key information. If this version conflicts with the center, a request is made to the center, and the preliminary distribution key information of each version held by the center is sent in sequence, and the secret key is updated to the latest version. You can upgrade in order. If the terminal is provided with a part for updating the distribution key, the center may individually encrypt and send the latest secret key to the terminal that requires version matching. The terminal shares the latest secret key with other terminals and calculates the next secret key and distributed key information from the secret key. Note that the version matching method in this case does not require the terminal to know the version information of the secret key initially held by the terminal, and the version can be matched only by reporting once from the center.
[0068]
Also, the distribution key information notified from the center to the terminal by broadcast may include an error in the middle. Research in these cases is done in the field of secret sharing. See M. Tompa, and H. Woll, "How to Share a Secret with Cheaters", Journal of Cryptology, v.1, n.2, 1988, pp133-138 for research results. In the present invention, such research results can be directly applied to the key sharing method.
[0069]
【The invention's effect】
As described above, in the present invention, for example, in order to eliminate one terminal and acquire the same secret key in the remaining terminals, the center need only send one piece of data. In general, in order to eliminate N or less terminals simultaneously, the center only needs to send N information. As a result, the time and effort of processing on the center side are reduced, and the inconvenience is less likely to occur because there is little deviation in updating the secret key between terminals.
[0070]
Also, with the configuration corresponding to claims 4 and 5 of the present invention, there is no need to manage the distribution key information of each terminal on the center side, and in the embodiment only the underlying polynomial need be managed. If necessary, the terminal distribution information of the corresponding terminal can be obtained by substituting the terminal identification information into the polynomial. This reduces the burden of terminal management on the center side.
[0071]
Also, with the configuration corresponding to claim 6 of the present invention, the distribution key information is updated using the conversion unit and the distribution key information update unit, so that one distribution key information may be managed in each terminal. . Thereby, the management burden of the distribution key information on the terminal side and the center side is reduced.
[0072]
In addition, the present inventionPointing out toungueBy using a plurality of relatively low-order polynomials instead of using a higher-order polynomial, the amount of calculation for calculating the secret key in the terminal can be reduced while maintaining security.
[Brief description of the drawings]
FIG. 1 is a diagram schematically showing distribution key information of each terminal according to Embodiment 1 of the present invention;
FIG. 2 is a diagram showing a case where the center excludes terminal T1 out of five terminals in Embodiment 1 of the present invention.
FIG. 3 is a diagram showing an internal configuration of terminal T3 according to Embodiment 1 of the present invention.
FIG. 4 is a diagram showing a configuration that enables updating of distribution key information in a terminal according to
FIG. 5 is a diagram schematically showing distribution key information of each terminal in Embodiment 4 of the present invention;
FIG. 6 is a diagram showing a case where the center simultaneously excludes terminal T1 and terminal T2 out of five terminals in Embodiment 4 of the present invention.
FIG. 7 shows an internal configuration of terminal T3 in Embodiment 4 of the present invention.
FIG. 8 is a diagram schematically showing distribution key information of each terminal in Embodiment 5 of the present invention.
FIG. 9 is a diagram illustrating a case where the center simultaneously eliminates terminal T1 and terminal T2 in Embodiment 5 of the present invention.
FIG. 10 is a diagram showing an internal configuration of terminal T3 according to Embodiment 5 of the present invention.
FIG. 11 is a diagram showing a configuration of a key sharing method of Conventional Example 1;
FIG. 12 is a diagram showing a configuration of a key sharing method of Conventional Example 2
[Explanation of symbols]
1 Distribution key information storage
2 receiver
3 Secret key calculation unit
4 Conversion unit
5 Distribution key information update part
6 Identification information storage
11 Distribution key information storage
12 Receiver
13 Secret key calculation unit
21 Distribution key information storage
22 Intermediate secret key calculation unit
23 Distribution key information storage
24 Intermediate secret key calculation unit
25 Secret key calculator
Claims (17)
センター側装置は全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、kを正整数とするとき、特定のk個の端末の分配鍵情報を同報で全端末に通知する通知部を備え、
各端末は、分配鍵情報を格納する分配鍵情報格納部と、前記センター側装置から通知されたk個の分配鍵情報を受信する受信部と、前記受信部で受信したk個の分配鍵情報と、前記分配鍵情報格納部に格納される分配鍵情報の計k+1個の分配鍵情報がすべて相異なる場合にのみ、これらk+1個の分配鍵情報より前記特定のk個の端末を除く残りの端末で共通の秘密鍵を算出する秘密鍵算出部からなり、
前記各端末の分配鍵情報は、前記秘密鍵算出部に入力されるk+1個の分配鍵情報がすべて相異なる場合にのみ前記秘密鍵が復元できるように予め定められ各端末に分配されたものであることを特徴とする鍵共有システム。 A key sharing system ing from a plurality of terminals having a center-side device and the different distribution key information,
The center side device is an all terminal distribution key information storage unit that stores distribution key information of all terminals, and a notification that notifies all terminals of the distribution key information of specific k terminals when k is a positive integer. Part
Each terminal includes a distribution key information storage unit that stores distribution key information, a reception unit that receives k distribution key information notified from the center side device, and k distribution key information received by the reception unit. Only when the total k + 1 pieces of distributed key information of the distributed key information stored in the distributed key information storage unit are different from each other, the specific k terminals from the k + 1 pieces of distributed key information A secret key calculation unit that calculates a secret key common to the remaining terminals excluding
The distribution key information of each terminal is predetermined and distributed to each terminal so that the secret key can be restored only when k + 1 pieces of distribution key information input to the secret key calculation unit are all different. Key sharing system characterized by being a thing.
センター側装置は全端末の分配鍵情報を格納する全端末分配鍵情報格納部と、kを正整数とするとき、特定のk個の端末の分配鍵情報を同報で全端末に通知する通知部を備え、
各端末は、分配鍵情報を格納する分配鍵情報格納部と、前記センター側装置から通知されたk個の分配鍵情報を受信する受信部と、前記受信部で受信したk個の分配鍵情報と、前記分配鍵情報格納部に格納される分配鍵情報の計k+1個の分配鍵情報がすべて相異なる場合にのみ、これらk+1個の分配鍵情報より前記特定のk個の端末を除く残りの端末で共通の第１の秘密鍵を算出する秘密鍵算出部と、前記第１の秘密鍵を全端末共通の変換方法で変換して第２の秘密鍵を求める変換部と、前記第２の秘密鍵から端末の新しい分配鍵情報を算出し、前記分配鍵情報格納部に格納して分配鍵情報を更新する分配鍵情報更新部からなり、
前記各端末の更新前の分配鍵情報は、前記秘密鍵算出部において入力されるk+1個の分配鍵情報がすべて相異なる場合にのみ前記第１の秘密鍵が復元できるように予め定められ各端末に分配されたものであり、前記分配鍵情報更新部によって更新された各端末の分配鍵情報は、前記と同様に前記第２の秘密鍵が復元できるように定められて各端末に分配されたものになり、前記各端末の変換部と分配鍵情報更新部は、外部より観察したり、変更できないものであり、前記センター側装置の全端末分配鍵情報格納部は、前記各端末で更新された分配鍵情報を格納することを特徴とする鍵共有システム。 A key sharing system ing from a plurality of terminals having a center-side device and the different distribution key information,
The center side device is an all terminal distribution key information storage unit that stores distribution key information of all terminals, and a notification that notifies all terminals of the distribution key information of specific k terminals when k is a positive integer. Part
Each terminal includes a distribution key information storage unit that stores distribution key information, a reception unit that receives k distribution key information notified from the center side device, and k distribution key information received by the reception unit. Only when the total k + 1 pieces of distributed key information of the distributed key information stored in the distributed key information storage unit are different from each other, the specific k terminals from the k + 1 pieces of distributed key information A secret key calculation unit that calculates a first secret key that is common to the remaining terminals except for a conversion unit that converts the first secret key by a conversion method common to all terminals, and obtains a second secret key; A new distribution key information of the terminal is calculated from the second secret key, and stored in the distribution key information storage unit to update the distribution key information;
The distribution key information before updating of each terminal is determined in advance so that the first secret key can be restored only when k + 1 pieces of distribution key information input in the secret key calculation unit are all different. The distribution key information of each terminal updated by the distribution key information update unit is determined so that the second secret key can be restored in the same manner as described above, and distributed to each terminal. The conversion unit and the distribution key information update unit of each terminal cannot be observed or changed from the outside, and the all terminal distribution key information storage unit of the center side device is A key sharing system for storing updated distribution key information.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP01854196A JP3620138B2 (en) | 1996-02-05 | 1996-02-05 | Key sharing system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP01854196A JP3620138B2 (en) | 1996-02-05 | 1996-02-05 | Key sharing system |
Related Child Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2004263626A Division JP3861896B2 (en) | 2004-09-10 | 2004-09-10 | Key sharing system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH09212089A JPH09212089A (en) | 1997-08-15 |
| JP3620138B2 true JP3620138B2 (en) | 2005-02-16 |
Family
ID=11974501
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP01854196A Expired - Fee Related JP3620138B2 (en) | 1996-02-05 | 1996-02-05 | Key sharing system |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3620138B2 (en) |
Families Citing this family (24)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000031956A (en) * | 1998-07-15 | 2000-01-28 | Nippon Telegr & Teleph Corp <Ntt> | Method and system for sharing individual secret information |
| DE19847944A1 (en) * | 1998-10-09 | 2000-04-13 | Deutsche Telekom Ag | Establishing a common key between a central station and a group of subscribers involves using public mathematical group, higher order element of group and threshold process |
| US6813357B1 (en) | 1998-12-25 | 2004-11-02 | Matsushita Communication Industrial Co., Ltd. | Exclusive key sharing method |
| JP2002217891A (en) * | 2001-01-22 | 2002-08-02 | Toshiba Corp | Secret sharing management program and system |
| 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 (en) * | 2003-10-14 | 2010-11-10 | ソニー株式会社 | Information processing apparatus and information processing method |
| JP4708713B2 (en) * | 2004-02-10 | 2011-06-22 | エヌ・ティ・ティ・コミュニケーションズ株式会社 | Confidential information management system, confidential information management method, and confidential information management program |
| WO2005076518A1 (en) | 2004-02-10 | 2005-08-18 | Ntt Communications Corporation | Secret information management scheme based on secret sharing scheme |
| KR100561438B1 (en) * | 2004-07-09 | 2006-03-17 | 삼성전자주식회사 | Authorization method using Lagrangian interpolation method and content transmission method using the same |
| JP4523847B2 (en) * | 2005-01-26 | 2010-08-11 | 日本電信電話株式会社 | In a communication terminal or full mesh network, each terminal can reliably check the connection between all other terminals. |
| 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 (en) * | 2006-03-17 | 2006-06-29 | Fujitsu Ltd | Security method and security device |
| JP4867425B2 (en) * | 2006-03-27 | 2012-02-01 | ソニー株式会社 | Information processing apparatus, information processing method, and computer program |
| JP5043408B2 (en) * | 2006-11-27 | 2012-10-10 | 三菱電機株式会社 | Key management server, terminal, key sharing system, key distribution program, key reception program, key distribution method and key reception method |
| JP4916915B2 (en) * | 2007-02-28 | 2012-04-18 | Ｋｄｄｉ株式会社 | Terminal device, data management device, and computer program |
| FR2925732B1 (en) * | 2007-12-21 | 2010-02-12 | Sagem Securite | GENERATION AND USE OF A BIOMETRIC KEY |
| US8151333B2 (en) | 2008-11-24 | 2012-04-03 | Microsoft Corporation | Distributed single sign on technologies including privacy protection and proactive updating |
| JP5608509B2 (en) * | 2010-10-21 | 2014-10-15 | Ｋｄｄｉ株式会社 | Key management system, key management method, and computer program |
| JP5644453B2 (en) * | 2010-12-08 | 2014-12-24 | 富士通セミコンダクター株式会社 | Authentication system and authentication method |
| JP5911289B2 (en) * | 2011-12-16 | 2016-04-27 | セコム株式会社 | Key management system |
| KR20190047143A (en) | 2013-07-31 | 2019-05-07 | 닛본 덴끼 가부시끼가이샤 | Devices and method for mtc group key management |
| GB201711878D0 (en) * | 2017-07-24 | 2017-09-06 | Nchain Holdings Ltd | Computer - implemented system and method |
| KR20240150285A (en) * | 2023-04-07 | 2024-10-15 | 한양대학교 산학협력단 | Method for threshold secret sharing and reconstruction for multi-compartment |
-
1996
- 1996-02-05 JP JP01854196A patent/JP3620138B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH09212089A (en) | 1997-08-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3620138B2 (en) | Key sharing system | |
| CN110557245B (en) | Method and system for fault-tolerant and secure multi-party computation in SPDZ | |
| CN110380844B (en) | A quantum key distribution method, device and storage medium | |
| JP6363032B2 (en) | Key change direction control system and key change direction control method | |
| KR100404694B1 (en) | Cryptographic key generation system | |
| CN113992330B (en) | Agent re-encryption-based blockchain data controlled sharing method and system | |
| US8886931B2 (en) | Key sharing system, communication terminal, management device, key sharing method, and computer program | |
| CN103873236B (en) | One kind can search for encryption method and equipment | |
| CN112183767A (en) | Multi-key lower model aggregation federal learning method and related equipment | |
| JP3794457B2 (en) | Data encryption / decryption method | |
| CN117494177A (en) | Method and system for data hiding statistical query based on privacy calculation | |
| US20240235832A1 (en) | Selective data sharing | |
| JP4216914B2 (en) | Network system | |
| WO2000039957A1 (en) | Exclusive key sharing method | |
| JP6400743B2 (en) | Terminal device, database server, and computing system | |
| JP3861896B2 (en) | Key sharing system | |
| CN114297721B (en) | Information processing method, information processing device, blockchain platform and storage medium | |
| JPWO2017149686A1 (en) | Key generation apparatus, computer system, and cryptographic statistical processing method | |
| JP3233605B2 (en) | Key update method | |
| JP2865654B1 (en) | Key update method | |
| JPH11252065A (en) | Encryption key generation device | |
| JP2948605B2 (en) | Terminal for encrypted communication common to encryption keys | |
| Pareek et al. | Extended hierarchical key assignment scheme (E-HKAS): how to efficiently enforce explicit policy exceptions in dynamic hierarchies | |
| JP2000196581A (en) | Exclusive key agreement | |
| 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 |