(57)【要約】【課題】分散値の更新のための通信回数を少なくする。【解決手段】端末装置１２は自身に、ｋ−１個の新たな更新用の鍵ｋｅｙ２ｊ（ｔ）（ｊ＝ｎ-ｋ＋２,・・・,ｎ）を設定し、分散値を更新するための乱数を以前生成するために用いた更新用の鍵ｋｅｙ２ｊ（ｔ-１）（ｊ＝ｈ＋１,・・・,ｎ）と、今回新たに分散値を更新するための乱数を生成するための鍵ｋｅｙ２ｊ（ｔ）（ｊ＝ｈ＋１,・・・,ｎ）とを、データサーバ１４Ｐｊに送信する。データサーバ１４Ｐｊは、上位送信された鍵ｋｅｙ２ｊ（ｔ-１）と鍵ｋｅｙ２ｊ（ｔ）とを受信し、受信した鍵ｋｅｙ２ｊ（ｔ-１）と鍵ｋｅｙ２ｊ（ｔ）とを用いて、ｍ個の更新値（乱数）uｉｊ（ｔ-１）とuｉｊ（ｔ）を生成し、現在の分散値Ｗｉｊ（ｔ-１）から以前の更新値uｉｊ（ｔ-１）を引くことで、最初の分散値に戻し、新たな更新値uｉｊ（ｔ）を加えることで新たな分散値Ｗｉｊ（ｔ）を得る。【選択図】図１
2018005089.tif 000002
【特許請求の範囲】
【請求項１】
秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない手段を用いて情報秘匿を行うと共に、前記分散値を更新する分散値更新装置を備えるシステムにおける、前記分散値更新装置であって、
鍵を用いて乱数を生成する乱数生成手段と、
前記乱数生成手段により生成された乱数と分散値とを演算することにより、前記分散値を更新した新たな分散値を得る演算手段と、
を備える分散値更新装置。
【請求項２】
鍵を受信する受信手段を更に備え、
前記乱数生成手段は、前記受信手段により受信された鍵を用いて、前記乱数を生成する、
請求項１に記載の分散値更新装置。
【請求項３】
鍵を生成する鍵生成手段を更に備え、
前記乱数生成手段は、前記鍵生成手段により生成された鍵を用いて、前記乱数を生成する、
請求項１に記載の分散値更新装置。
【請求項４】
前記鍵は、最初の分散値を更新するための第１の乱数を生成するための第１の鍵と、前記新たな分散値を得るための第２の乱数を生成するための第２の鍵と、を含み、
前記分散値更新装置は、前記第１の乱数で前記最初の分散値を更新した更新済み分散値を有し、
前記乱数生成手段は、前記第１の鍵を用いて前記第１の乱数を生成し且つ前記第２の鍵を用いて前記第２の乱数を生成し、
前記演算手段は、前記更新済み分散値、前記第１の乱数、及び前記第２の乱数に基づいて、前記新たな分散値を得る、
請求項１〜請求項３の何れか１項に記載の分散値更新装置。
【請求項５】
秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない手段を用いて情報秘匿を行うと共に、請求項１に記載の分散値更新装置と、分散値を計算する分散値計算装置とを備えるシステムにおける、前記分散値計算装置であって、
鍵を用いて乱数を生成する乱数生成手段と、
前記乱数生成手段により生成された乱数から、分散値を更新するために用いた値を計算する値計算手段と、
前記値計算手段により計算された前記値に基づいて、自らの新たな分散値を計算する分散値計算手段と、
を備える分散値計算装置。
【請求項６】
前記値計算手段は、最初の分散値を更新した更新済み分散値と前記最初の分散値との差を計算することにより、前記値を生成し、
前記分散値計算手段は、前記値計算手段により計算された前記値から、自らの分散値を更新するための差分値を計算し、前記最初の分散値と演算することにより、前記自らの新たな分散値として前記更新済み分散値を計算する、請求項５に記載の分散値計算装置。
【請求項７】
秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない手段を用いて情報秘匿を行うと共に、前記分散値を検証する分散値検証装置を備えるシステムにおける、前記分散値検証装置であって、
正当であることが保証された第１の分散値と、受信された分散値とから第１の秘密情報を復元する第１の復元手段と、
前記受信された分散値を、正当であることが保証された第２の分散値に変えて第２の秘密情報を復元する第２の復元手段と、
前記第１の復元手段により復元された第１の秘密情報と前記第２の復元手段により復元された第２の秘密情報とに基づいて、前記第１の秘密情報の復元の正当性を検証する検証手段と、
を備える分散値検証装置。
【請求項８】
前記第１の分散値及び前記第２の分散値の少なくとも一方は、請求項５又は請求項６に記載の分散値計算装置により生成されたものである請求項７に記載された分散値検証装置。
【請求項９】
秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない手段を用いて情報秘匿を行うと共に、コンピュータを含む分散値更新装置を備えるシステムにおける、前記分散値を更新する分散値更新プログラムであって、
前記分散値更新装置のコンピュータに、
鍵を用いて乱数を生成する乱数生成工程と、
前記乱数生成工程により生成された乱数と分散値とを演算することにより、前記分散値を更新した新たな分散値を得る演算工程と、
を実行させる分散値更新プログラム。
【請求項１０】
前記分散値更新プログラムは、前記コンピュータに、鍵を受信する受信工程を更に実行させ、
前記乱数生成工程では、前記受信工程で受信された鍵を用いて、前記乱数を生成する、
請求項９に記載の分散値更新プログラム。
【請求項１１】
前記分散値更新プログラムは、前記コンピュータに、鍵を生成する鍵生成工程を更に実行させ、
前記乱数生成工程では、前記鍵生成工程により生成された鍵を用いて、前記乱数を生成する、
請求項９に記載の分散値更新プログラム。
【請求項１２】
前記鍵は、最初の分散値を更新するための第１の乱数を生成するための第１の鍵と、前記新たな分散値を得るための第２の乱数を生成するための第２の鍵と、を含み、
前記第１の乱数で前記最初の分散値を更新した更新済み分散値が得られており、
前記乱数生成工程では、前記第１の鍵を用いて前記第１の乱数を生成し且つ前記第２の鍵を用いて前記第２の乱数を生成し、
前記演算工程では、前記更新済み分散値、前記第１の乱数、及び前記第２の乱数に基づいて、前記新たな分散値を得る、
請求項９〜請求項１１の何れか１項に記載の分散値更新プログラム。
【請求項１３】
秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない工程を用いて情報秘匿を行うと共に、請求項１に記載の分散値更新装置と、コンピュータを含む分散値計算装置とを備るシステムにおける、前記分散値を計算する分散値更新プログラムであって、
前記分散値計算装置のコンピュータに、
鍵を用いて乱数を生成する乱数生成工程と、
前記乱数生成工程により生成された乱数から、分散値を更新するために用いた値を計算する値計算工程と、
前記値計算工程により計算された前記値から、自らの新たな分散値を計算する分散値計算工程と、
を実行させる分散値計算プログラム。
【請求項１４】
前記値計算工程では、最初の分散値を更新した更新済み分散値と前記最初の分散値との差を計算することにより、前記値を生成し、
前記分散値計算工程では、前記値計算工程で計算された前記値から、自らの分散値を更新するための差分値を計算し、前記最初の分散値と演算することにより、前記自らの新たな分散値として前記更新済み分散値を計算する、請求項１３に記載の分散値計算プログラム。
【請求項１５】
秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない工程を用いて情報秘匿を行うと共に、コンピュータを含む分散値検証装置を備えるシステムにおける、前記分散値を検証する分散値検証プログラムであって、
前記分散値検証装置のコンピュータに、
正当であることが保証された第１の分散値と、受信された分散値とから第１の秘密情報を復元する第１の復元工程と、
前記受信された分散値を、正当であることが保証された第２の分散値に変えて第２の秘密情報を復元する第２の復元工程と、
前記第１の復元工程により復元された第１の秘密情報と前記第２の復元工程により復元された第２の秘密情報とに基づいて、前記第１の秘密情報の復元の正当性を検証する検証工程と、
を実行させる分散値検証プログラム。
【請求項１６】
前記第１の分散値及び前記第２の分散値の少なくとも一方は、請求項１３又は請求項１４に記載の分散値計算プログラムにより生成されたものである請求項１５に記載された分散値検証プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散値更新装置及び分散値更新プログラム、分散値計算装置及び分散値計算プログラム、分散値検証装置及び分散値検証プログラムに関する。
【背景技術】
【０００２】
近年、クラウドコンピューティングの利用やアプリの開発が盛んに行われている。クラウドは従来ユーザが自前の装置などに管理していたデータを、オンライン上のサーバに保有、管理する。そのため、ユーザは自身のデータを持ち歩くことなしに、ネットワークを介していつでもどこでも必要なデータにアクセスできるようになり、クラウド上に大量のデータを保存しておくこともできる。さらに、上記データを上記サーバに短期間で導入することが可能というメリットもある。しかしながら、クラウドを使用する際には、基本的にはすべてのデータがクラウドに集約されるため、安全性に関して気を付けなければならない問題点がいくつかある。その一つは、サーバやネットワークの障害などによって、クラウドサービスが利用できなくなってしまう場合である。さらに集中的なデータの管理は攻撃の標的となりやすく、情報流出の危険性が高まる。特に、企業の機密情報などが流出した場合には、致命的な被害を生じさせる場合もある。また、情報を守るために通常暗号化を行うが、秘匿計算まで考慮に入れた場合、一般に準同型性を持つ暗号化は処理が重く、秘匿計算しようとした際に時間がかかってしまう。以上の問題を解決するため、クラウドシステムに「秘密分散法」（ｓｅｃｒｅｔ ｓｈａｒｉｎｇ ｓｃｈｅｍｅ）を適用することが考えられている。
【０００３】
ここで、秘密分散法は、一つの情報をｎ個の異なる情報に分散し、そのうちのｋ個以上が集まれば元の情報が復元可能だが、ｋ個未満では元の情報は全く復元されないという手法である。これは（ｋ,ｎ）秘密分散法と呼ばれ、サーバやネットワークの障害などによりデータの一部が使えなくても、データの一部が使えなくなったサーバの数がｎ-ｋ以下ならば元の情報が復元でき、さらにｋ個以上の情報が漏洩しない限り情報漏洩は起こらないという安全な情報管理システムが実現できる。具体的な秘密分散法として、以下のＳｈａｍｉｒの（ｋ,ｎ）秘密分散法（以降、「Ｓｈａｍｉｒ法」ともいう）がよく知られている。
［Ｓｈａｍｉｒ法］
［分散］
以下の分散の手順１〜４は、ｎ個のサーバと通信し且つ秘密情報ｓを有するオーナ（ユーザ）の端末装置が実行する。
【０００４】
１．ｓ＜ｐかつｎ＜ｐである任意の素数pを選ぶ。
【０００５】
２．Ｚ/ｐＺ（または有限体：ガロア体（ＧＦ（ｐ））から、異なるｎ個のｘｉ（ｉ＝１,２,・・・,ｎ） を選び出し、ｎ個のサーバのサーバＩＤとしてメモリに記憶しておく。
【０００６】
３．Ｚ/ｐＺ から、ｋ−１個の乱数ａｌ（ｌ＝１,２,・・・,ｋ−１）を選んで、以下の式（１）（以降、分散式と呼ぶ）を生成する。
【０００７】
Ｗｉ＝ｓ＋ａ１ｘｉ＋ａ２ｘｉ２＋・・・＋ａｋ−１ｘｉｋ−１（ｍoｄ p） （１）
４．上記式（１）のｘｉに各サーバのサーバＩＤを代入して、分散値Ｗｉを計算し、各サーバにこれらのサーバＩＤであるｘｉと分散値Ｗｉを送信する（配布する）。
【０００８】
［復元］
以下の復元の手順１〜２は、復元を許可されたユーザ（オーナを含む）の端末装置が実行する。
１．ｎ個のサーバの中から任意に選択したｋ個のサーバから、復元に用いる分散値Ｗｉ（ｉ＝１,２,・・・,ｋ）を受信する。また，その分散値に対応するサーバＩＤ（ｘｉ）を、自端末装置のメモリから読み出す。または分散値Ｗｉとともに送信してもらう。
【０００９】
２．分散式（式（１））にｘｉとＷｉを代入し、ｋ個の連立方程式を解いて、ｓを得る。ｓの復元の際には、Ｌａｇｒａｎｇｅの補間公式を用いると便利である。
【００１０】
一方、Ｓｈａｍｉｒ法をはじめとする従来の秘密分散法は一つの情報がｎ個の情報に変換されるため、管理すべき情報の量がｎ倍になるという問題点がある。また、一般的なクラウド利用は利用者が１つのクラウド業者と契約して情報保管してもらうという場合がほとんどである。よって、そのクラウド業者のサーバに分散値を記憶させるのに秘密分散法を適用していても、そのクラウド業者は全てのサーバにアクセス可能なため秘密情報の復元が可能である。従って、利用者は秘密情報の意図しない復元の危惧から逃れられない。
【００１１】
その一つの解決策として高橋らによって提案された非対称秘密分散法がある。非対称秘密分散法とは、ランプ型秘密分散法のように全サーバの記憶容量を均等に削減するのではなく、特定のサーバの持つ分散値を削減して非均一に記憶容量を削減する手法である。分散値を削減されたサーバは、鍵サーバと呼ばれ、鍵の情報のみを管理する、ようにできる。また、非対称秘密分散法も準同性をもつため、秘密情報を秘匿したまま演算を行う秘匿演算を実行できる。ここで、秘密情報のオーナ自身が鍵サーバとなり鍵を自ら管理すればオーナ自身が秘密情報の復元や秘匿演算を制御することが可能である。この場合、管理すべき秘密情報が膨大でもオーナは鍵のみを管理すればよいためスマホなどの携帯端末を鍵サーバとすることができる。以下に、Ｓｈａｍｉｒ法に基づく非対称秘密分散法を示す。
【００１２】
［非対称秘密分散法］
複数の異なるオーナにより利用されるクラウドシステムを構成する物理的に異なるｎ台のサーバの中からｈ台（ｈ＜ｋ）が予め選択されて鍵サーバとして指定されている。これらの鍵サーバは分散値を持たず、擬似乱数を生成するための鍵情報のみを持つ。鍵サーバ以外の（ｎ−ｈ）個のサーバは、データサーバと呼ばれ、分散値を生成するオーナの端末装置から送信された分散値を保管する。また、秘密情報を分散する各オーナの端末装置にはオーナ識別のためＩＤ［ｙ］（ｙ＝１,・・・,r）が割り当てられており、それぞれのオーナが持つｍ個の秘密情報ｓ１ｊ,・・・, ｓｍｊ （ｊ＝１,・・・,r）にもそれぞれデータ識別のためｄＩＤ［ｓｉｊ］（ｉ＝１,・・・,ｍ） が割り振られているものとする。なお、Ｅｎｃ（ａ,b）はａをｂという鍵を用いて暗号化する処理を表すものとする。
【００１３】
［分散］
分散の手順１〜６を説明する。
１．オーナの端末装置は対応するＩＤ［ｙ］を鍵サーバｘ１,・・・,ｘｈに送信する。
２．ＩＤ［ｙ］を受け取った鍵サーバｘ１,・・・,ｘｈは自身の持つ暗号装置と鍵ｋｅｙｊ（ｊ＝１,・・・,ｈ）を利用して、以下の式（２）より、Ｅｉｄ（ｙ,ｊ）を生成し、オーナの端末装置に送信する。なお、ここでのｊは、鍵サーバを識別する。
Ｅｉｄ（ｙ,ｊ）＝Ｅｎｃ（ＩＤ［ｙ］,ｋｅｙｊ）（ｊ＝１,・・・,ｈ）    （２）
３．Ｅｉｄ（ｙ,ｊ）を受信したオーナの端末装置は自身の秘密情報に関するデータ識別子ｄＩＤ［ｓｉ］（ｉ＝１,・・・,ｍ）を用いて、以下の式（３）より、擬似乱数ｑｉｊを生成する。
ｑｉｊ＝Ｅｎｃ（ｄＩＤ［ｓｉ］,Ｅｉｄ（ｙ,ｊ））        （３）
４．オーナの端末装置はまず式（１）のｋ−１次の分散式の係数ベクトルＡ（ｉ）＝［ｓｉ,ａｉ１,・・・,ａｉｋ−１］Ｔにおける（ｋ−ｈ−１）次の部分ベクトルＡ’ｋ-ｈ−1＝［ａｉｈ＋１,・・・,ａｉｋ−１］Ｔを真性乱数を用いてｉごとに定める。その後、オーナの端末装置は、分散の手順３で生成したｈ次の擬似乱数系列Ｑ＝［ｑｉ１,・・・,ｑｉｈ］Ｔ及び鍵サーバのＩＤ系列
【００１４】
【数１】
2018005089.tif 000003
【００１５】
を用いて以下の式から分散式のｋ−１次の部分ベクトルＡ（ｉ）ｋ−１＝［ａｉ１,・・・,ａｉｋ−１］Ｔにおける残りの部分ベクトルＡ’ｈ（ｉ）＝［ａｉ１,・・・,ａｉｈ］Ｔを、秘密情報ｉごとに算出する。
【００１６】
【数２】
2018005089.tif 000004
【００１７】
ここで上記式においてＳ＝［ｓｉ,・・・,ｓｉ］Ｔとすると、
Ａ（ｉ）ｋ−１＝Ｘ’-１（Ｑ-Ｓ）   （６）
となる。これにより、オーナの端末装置は、ｋ−１次の分散式の係数ベクトルＡ（ｉ）＝［ｓｉ,ａｉ１,・・・,ａｉｋ−１］Ｔにおけるｋ−１次の部分ベクトルＡ（ｉ）ｋ−１＝［ａｉ１,・・・,ａｉｋ−１］Ｔをすべて決定することができる。
【００１８】
５．オーナの端末装置は、データサーバｘｈ＋１,・・・,ｘｎに関する分散値Ｗｉｈ＋１,・・・,Ｗｉｎを、分散の手順４で生成した係数行列を利用して、（ｋ,ｎ）秘密分散法と同様の手順により算出する。
６．オーナの端末装置は、それぞれのデータサーバに、生成した分散値Ｗ１ｊ,・・・,Ｗｍｊ（ｊ＝ｈ＋１,・・・,ｎ）を送信する。
【００１９】
［復元］
復元の手順１〜４を説明する。
１．秘密情報ｓｉを復元するユーザの端末装置は、ｎ個のサーバ（鍵サーバ及びデータサーバ）ｘ１,・・・,ｘｎの中から任意のｋ個のサーバを選択し、選択したサーバに対してオーナの端末装置のＩＤ［ｙ］及び秘密情報ｓｉのデータ識別子ｄＩＤ［ｓｉｊ］を送信する。
２．ｎ個のサーバの中で、（ＩＤ［ｙ］,ｄＩＤ［ｓｉｊ］）を受け取った鍵サーバは自身の持つ鍵ｋｅｙｊ及び暗号装置を利用して、式（２）よりＥｉｄ（ｙ,ｊ）を生成し、式（３）より擬似乱数ｑｉｊを生成してユーザの端末装置に送信する。
３．ｎ個のサーバの中で、（ＩＤ［ｙ］,ｄＩＤ［ｓｉｊ］）を受け取ったデータサーバはこれらのＩＤ情報に対応する分散値Ｗｉｊをオーナの端末装置に送信する。
４．データサーバにより生成された分散値及び擬似乱数を受け取ったオーナの端末装置は、これらを利用して（ｋ,ｎ）秘密分散法と同様の手段で、秘密情報ｓｉを復元する。
【００２０】
このような応用においては、オーナが携帯端末をなくすまたは盗難される、壊れるなどの問題が考えられる。オーナの携帯端末は鍵を管理しているだけなので、鍵のバックアップ値を別の安全なところに保管しておけば新たな携帯端末にそのバックアップ値を再設定することによって秘密情報の分散・復元または秘匿演算を継続して行うことができる。しかし、盗まれるまたは失われた携帯端末はパスワードや生体認証などを用いて厳重に管理されていたとしても、携帯端末に含まれる鍵が他人の手に渡った可能性がある場合、その携帯端末で管理されていた分散値は全て更新されることが望まれる。以下に、Ｈｅｒｚｂｅｒｇらによる分散値の更新手法を示す。
【００２１】
［Ｈｅｒｚｂｅｒｇらによる分散値更新法］
Ｈｅｒｚｂｅｒｇらの更新手法では分散値の更新を行うだけの基本方式と、更新時または復元時に不正サーバがいる場合を想定し、検証情報によってその正当性を確認する２つの検証方式が提案されている。以下にそれらを示す。
【００２２】
（基本方式）
分散値更新の手順１〜３を説明する。
ｎ台のサーバにＳｈａｍｉｒ法を用いた分散値が保存されているとして、以下にその更新手順を示す。ただし、各サーバは互いに安全な暗号通信を行うことができるとする。
【００２３】
１．ｎ台のサーバの各々のサーバPｉはｋ−１個の乱数bｉｊ （ｊ＝１,２,・・・,ｋ−１）を生成し，式（７）を満たすｋ−１次多項式bｉ（ｘ）を作る。
bｉ（ｘ）＝bｉ１ｘ１＋bｉ２ｘ２＋・・・＋bｉｋ−１ｘｋ−１     （７）
bｉ（０）＝０                      （８）
２．ｎ台のサーバの各々のサーバPｉは他のすべてのサーバPｊのＩＤであるｘｊをｘに入力したuｉｊ＝bｉ（ｘｊ）を生成し、暗号化してサーバPｊに安全に送信する。
３．暗号化されたuｉｊを受け取った各サーバPｊは、各uｉｊを復号し、式（９）に従って自身の分散値に加える。なお、Ｗｊ（ｔ）は時刻ｔにおける分散値を表し，ｔは分散値の更新が行われる度に＋１される。
Ｗｊ（ｔ）＝Ｗｊ（ｔ-１）＋（u１ｊ＋u２ｊ＋・・・＋uｎｊ）     （９）
以上によって、すべてのサーバが分散値更新の手順１〜３を正しく行う場合、分散値の更新が正しく行われる。 
【００２４】
（第１の検証方式：更新時での不正に対する検証方式）
第１の検証方式の手順１〜７を説明する。
基本方式において、あるサーバが式（７）を満足しないｋ−１次式方程式を使ってuｉｊを作成し、それを配布した場合、分散値の更新は正しく行われない。すなわち、どのｋ台のサーバの分散値を集めても正しい秘密情報は復元されない（不正を行ったサーバはその差分値を知るため、そのサーバのみ正しく秘密情報を復元できる）。
よって、式（７）を満足しない情報を送る攻撃を想定する場合は以下の手順で更新を行う。
【００２５】
以下において、送信者をＳ、受信者をＲとしたとき、ＥＮＣRは受信者の公開鍵で暗号化することを意味し、ＳＩGＳは送信者の秘密鍵で署名することを意味する。
１．サーバPｉはｋ−１個の乱数を生成し式（１０）のｋ−１次多項式を作る。また、式（１０）の多項式の各係数に対して式（１１）を計算する。ただし、以降gを離散対数問題において安全な生成元、すなわち現段階では１０００bｉｔ以上の値とする。
【００２６】
bｉ（ｘ）＝bｉ１ｘ１＋bｉ２ｘ２＋・・・＋bｉｋ−１ｘｋ−１           （１０）
【００２７】
【数３】
2018005089.tif 000005
【００２８】
２．サーバPｉは他のすべてのサーバPｊに対してuｉｊ＝bｉ （ｘｊ）とｅｉｊ＝ＥＮＣｊ（uｉｊ）を計算する。
３．サーバPｉはＶＳＳｉ（ｔ）＝（ｉ,ｔ,εｉｍ,ｅｉｊ）とＳＩGｉ （ＶＳＳｉ（ｔ））をブロードキャストする。（ＶＳＳｉ（ｔ）は時間ｔにおけるＶＳＳｉ）
４．サーバPｉは送られてきた情報ｅｉｊを復号し、以下の式で検証する。
【００２９】
【数４】
2018005089.tif 000006
【００３０】
５．正確な情報と判断したら、送られてきた情報を保持し、検証が通ったことを他のサーバにブロードキャストする。
６．すべてのサーバの検証が通ったらサーバPｉはbｊ （ｉ）を自身の分散値に加える。
７．５.で検証が通らなかった際には、不正サーバから送られるbｉを使用しない。また、不正サーバの存在を他のサーバにブロードキャストする。
【００３１】
（第２の検証方式：復元時での不正に対する検証方式）
第２の検証方式の手順１〜３を説明する。
第２の検証方式は、復元時に不正な分散値を提出するサーバに対して行う検証法である。
【００３２】
１．分散値の生成時、分散値生成者の端末装置は検証鍵
【００３３】
【数５】
2018005089.tif 000007
をブロードキャストする。
２．分散値の更新時、基本方式の３.または、更新時の検証方式の４.において、各サーバは以下の式によって検証鍵の更新を行い、ブロードキャストする。
【００３４】
【数６】
2018005089.tif 000008
３．秘密情報の復元時、復元者の端末装置は集めた分散値を検証鍵で検証を行うことで分散値が正しいものかを判別する。
【００３５】
なお、安全な掲示板などを準備できる場合．ブロードキャストは掲示板での公開とすることもできる。
【発明の概要】
【発明が解決しようとする課題】
【００３６】
しかし、従来よく知られているＨｅｒｚｂｅｒｇらによる分散値の更新手法はサーバ台数をｎとした場合、１つの秘密情報に対する分散値の更新のためにｎ×（ｎ-１）回の通信を必要とすることが知られている。よって、秘密情報の数をｍとするとｍ×ｎ×（ｎ-１）回の通信が必要となる。例えば、ｎ＝４、ｍ＝１００００とすると１２万回の通信を必要とする。
【００３７】
本発明は、分散値の更新のための通信回数を少なくすることが可能な分散値更新装置及び分散値更新プログラム、分散値計算装置及び分散値計算プログラムを提供することを第１の目的とする。
【００３８】
また、不正に対する検証方式では、式（１１）〜式（１３）から理解されるように、べき乗を計算しなければならず、計算量が多くなる。
【００３９】
本発明は、分散値の検証の際の計算量を少なくすることが可能な分散値検証装置及び分散値検証プログラムを提供することを第２の目的とする。
【課題を解決するための手段】
【００４０】
第１の目的を達成するために請求項１に記載の発明は、秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない手段を用いて情報秘匿を行うと共に、前記分散値を更新する分散値更新装置を備えるシステムにおける、前記分散値更新装置であって、鍵を用いて乱数を生成する乱数生成手段と、前記乱数生成手段により生成された乱数と分散値とを演算することにより、前記分散値を更新した新たな分散値を得る演算手段と、を備える。
【００４１】
前記乱数生成手段は、鍵を用いて乱数を生成する。
【００４２】
請求項２に記載の発明は、請求項１に記載の発明において、鍵を受信する受信手段を更に備え、前記乱数生成手段は、前記受信手段により受信された鍵を用いて、前記乱数を生成する。
【００４３】
請求項３に記載の発明は、請求項１に記載の発明において、鍵を生成する鍵生成手段を更に備え、前記乱数生成手段は、前記鍵生成手段により生成された鍵を用いて、前記乱数を生成する。
【００４４】
前記演算手段は、前記乱数生成手段により生成された乱数と分散値とを演算することにより、前記分散値を更新した新たな分散値を得る。
【００４５】
請求項４に記載の発明は、請求項１〜請求項３の何れか１項に記載の発明において、前記鍵は、最初の分散値を更新するための第１の乱数を生成するための第１の鍵と、前記新たな分散値を得るための第２の乱数を生成するための第２の鍵と、を含む。請求項４に記載の発明の前記分散値更新装置は、前記第１の乱数で前記最初の分散値を更新した更新済み分散値を有する。
【００４６】
請求項４に記載の前記乱数生成手段は、前記第１の鍵を用いて前記第１の乱数を生成し且つ前記第２の鍵を用いて前記第２の乱数を生成し、前記演算手段は、前記更新済み分散値、前記第１の乱数、及び前記第２の乱数に基づいて、前記新たな分散値を得る。
【００４７】
このように、分散値更新装置は、鍵を受信したり生成したりして得た当該鍵を用いて乱数を生成し、生成された乱数と分散値とを演算することにより、分散値を更新した新たな分散値を得る。鍵を受信等するだけなので、分散値の更新のための通信回数を少なくすることができる。
【００４８】
請求項５に記載の発明は、秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない手段を用いて情報秘匿を行うと共に、請求項１に記載の分散値更新装置と、分散値を計算する分散値計算装置とを備えるシステムにおける、前記分散値計算装置であって、鍵を用いて乱数を生成する乱数生成手段と、前記乱数生成手段により生成された乱数から、分散値を更新するために用いた値を計算する値計算手段と、前記値計算手段により計算された前記値に基づいて、自らの新たな分散値を計算する分散値計算手段と、を備える。
【００４９】
乱数生成手段は、鍵を用いて乱数を生成する。
【００５０】
値計算手段は、前記乱数生成手段により生成された乱数から、分散値を更新するために用いた値を計算する。分散値計算手段は、前記値計算手段により計算された前記値から、自らの新たな分散値を計算する。
【００５１】
請求項６に記載の発明の前記値計算手段は、最初の分散値を更新した更新済み分散値と前記最初の分散値との差を計算することにより、前記値を生成する。
【００５２】
前記分散値計算手段は、前記値計算手段により計算された前記値から、自らの分散値を更新するための差分値を計算し、前記最初の分散値と演算することにより、前記自らの新たな分散値として前記更新済み分散値を計算する。
【００５３】
第２の目的を達成するために請求項７に記載の発明は、秘密情報をｎ個に分散し、そのうちｋ個の分散値を集めれば秘密情報を復元でき、ｋ−Ｌ個（Ｌは１以上ｋ以下の整数）以下では秘密情報を復元できない手段を用いて情報秘匿を行うと共に、前記分散値を検証する分散値検証装置を備えるシステムにおける、前記分散値検証装置であって、正当であることが保証された第１の分散値と、受信された分散値とから第１の秘密情報を復元する第１の復元手段と、前記受信された分散値を、正当であることが保証された第２の分散値に変えて第２の秘密情報を復元する第２の復元手段と、前記第１の復元手段により復元された第１の秘密情報と前記第２の復元手段により復元された第２の秘密情報とに基づいて、前記第１の秘密情報の復元の正当性を検証する検証手段と、を備える。
【００５４】
第１の復元手段は、正当であることが保証された第１の分散値と、受信された分散値とから第１の秘密情報を復元し、第２の復元手段は、前記受信された分散値を、正当であることが保証された第２の分散値に変えて第２の秘密情報を復元する。
【００５５】
検証手段は、前記第１の復元手段により復元された第１の秘密情報と前記第２の復元手段により復元された第２の秘密情報とに基づいて、前記第１の秘密情報の復元の正当性を検証する。
【００５６】
このように、前記第１の復元手段により復元された第１の秘密情報と前記第２の復元手段により復元された第２の秘密情報とに基づいて、前記第１の秘密情報の復元の正当性を検証するので、べき乗を計算しなくてもよい。よって、計算量を少なくすることができる。
請求項８に記載の発明では、前記第１の分散値及び前記第２の分散値の少なくとも一方は、請求項５又は請求項６に記載の分散値計算装置により生成されたものである。
【００５７】
請求項９〜１２の発明に係る分散値更新プログラムは、分散値更新装置のコンピュータを、請求項１〜請求項４の何れか１項に記載の発明の各手段として機能させるためのプログラムである。
【００５８】
請求項１３、１４の発明に係る分散値計算プログラムは、分散値計算装置のコンピュータを、請求項５、６に記載の発明の各手段として機能させるためのプログラムである。
【００５９】
請求項１５、１６の発明に係る分散値更新プログラムは、分散値検証装置のコンピュータを、請求項７、８に記載の発明の各手段として機能させるためのプログラムである。
【発明の効果】
【００６０】
請求項１〜６、９〜１４の発明は、分散値の更新のための通信回数を少なくすることができる。
【００６１】
請求項７、８、１５、１６の発明は、分散値の検証の際の計算量を少なくすることができる。
【図面の簡単な説明】
【００６２】
【図１】第１の実施の形態の秘密情報分散検証システムの構成図である。
【図２】第１の実施の形態の端末装置１２のブロック図である。
【図３】端末装置１２が実行する鍵送信プログラムを示すフローチャートである。
【図４】データサーバ１４Ｐｊが実行する分散値更新プログラムを示すフローチャートである。
【図５】オーナの端末装置１２が実行する分散値更新及び秘密情報復元プログラムのフローチャートである。
【図６】データサーバ１４Ｐｊが実行する分散値送信プログラムのフローチャートである。
【図７】端末装置１２が実行する分散値検証プログラムを示すフローチャートである。
【図８】データサーバが実行する分散値送信プログラムを示すフローチャートである。
【発明を実施するための形態】
【００６３】
以下、図面を参照して本発明の実施の形態の一例を詳細に説明する。
＜ 第１の実施の形態＞
まず、第１の実施の形態の構成を説明する。
図１に示すように、第１の実施の形態の秘密情報分散復元検証システムは、ネットワーク１０を介して相互に接続された、オーナの端末装置１２、秘匿演算・復元の管理を実現するため複数のデータサーバ１４Ｐ１、１４Ｐ２、１４Ｐ３、・・・を備えている。
【００６４】
端末装置１２は、請求項５、６、請求項１３、１４の分散値計算装置、請求項７、８、１５、１６の分散値検証装置の１例である。データサーバ１４Ｐ１、１４Ｐ２、１４Ｐ３、・・・は、請求項１〜４、請求項９〜１２の分散値更新装置の１例である。秘密情報分散復元検証システムは、請求項１〜１６のシステムの１例である。
【００６５】
端末装置１２、及び複数のデータサーバ１４Ｐ１、１４Ｐ２、１４Ｐ３、・・・は、同様の構成になっているので、端末装置１２のみの構成を、図２を参照して説明する。図２に示すように、端末装置１２は、コンピュータを含んで構成され、ＣＰＵ２２、ＲＯＭ２４、ＲＡＭ２６、メモリ２８、入力装置３０、送受信装置３２、表示装置３４がバス３６を介して相互に接続されて、構成されている。端末装置１２及びデータサーバ１４Ｐ１、１４Ｐ２、１４Ｐ３、・・・の各ＣＰＵ２２が後述する対応するプログラムを実行することにより各手段として機能する。
【００６６】
端末装置１２のメモリ２８には、後述する鍵送信プログラム（図３参照）、分散値更新及び秘密情報復元プログラム（図５参照）、分散値検証プログラム（図７参照）が記憶されており、これらのプログラムが読み出され、実行される。データサーバ１４Ｐ１、１４Ｐ２、１４Ｐ３、・・・のメモリ２８には、後述する分散値更新プログラム（図４参照）、２つの分散値送信プログラム（図６、図８参照）が記憶されており、これらのプログラムが読み出され、実行される。
【００６７】
次に、本実施の形態の作用を説明する。
本実施の形態では、オーナが鍵を管理する端末装置を紛失した場合における分散値の更新を考える。本実施の形態では、非対称秘密分散方式を対象とする。従来の非対称秘密分散方式では、物理的に異なるｎ個のサーバの中のｈのサーバが鍵サーバ、残りのｄ（＜ｋ−１）個のサーバがデータサーバとして指定されている。なお、ｎ＝ｈ＋ｄである。
【００６８】
これに対し、本実施の形態では、秘密情報のオーナの端末装置１２（例えば、携帯端末）は、ｈ個の鍵サーバの役割も果たす。よって、非対称秘密分散法においてオーナの端末装置１２は、ｈ個の鍵を管理する。この場合、背景技術の［分散］における１〜２の処理は以下の１つの処理となり、以降、Ｅｉｄ（ｙ,ｊ）＝Ｅｉｄ（ｊ）として３以降の処理を実行する。
【００６９】
「オーナは自身の携帯端末に、ｈ個の鍵Ｅｉｄ（ｊ）（ｊ＝１,・・・,ｈ）を設定する。」
【００７０】
この場合、オーナの端末装置１２は秘密情報の所有者であるため、全分散値をディーラとして自ら決めることができる。また、更新に必要な情報を発信することができるのはオーナの端末装置１２のみであり、他のサーバはそれらを受けて分散値を更新するだけとするので更新時における不正は考えない。よって、ここでは更新を行う基本方式と復元時における検証方式のみを考える。また、式（７）における未知数の数はｋ−１個であるため、ｋ−１個のサーバを解析すれば更新情報が漏洩する。よって、ｄ＜ｋ−１とすれば、全データサーバが解析されても更新情報を含め秘密情報は漏洩しないことが言える。ｄ＝ｋ−２とする。更新における前提としてｈ個の非対称秘密分散用の鍵Ｅｉｄ（ｊ）（オーナの端末装置１２が１つの鍵から鍵サーバの鍵を作る場合はその１つの鍵）と、今まで用いていた更新用の鍵ｋｅｙ２ｊ（ｔ-１）のバックアップは安全な場所に保管されており、携帯端末が紛失または盗難されたとしても復活できるとする。また、オーナがもつ携帯端末とデータサーバ間の通信は暗号化などにより安全に行われるとする。
【００７１】
（基本方式）
図１に示すように、時点ｔ-１において各データサーバ１４Ｐ１、１４Ｐ２、１４Ｐ３、・・・（１４Ｐｊ）は既にｍ個の秘密情報ｓｉ（ｉ＝１,・・・,ｍ）∈Ｚ/ｐＺ（pは素数）に対する分散値Ｗｉｊ（ｔ-１）を所持しているとする。また、端末装置１２は非対称秘密分散に用いる分散値生成用の鍵Ｅｉｄ（ｊ）と、時点ｔ-１において用いた更新用の鍵ｋｅｙ２ｊ（ｔ-１）を保持しているとする。
【００７２】
ここでは、ｉにより、ｍ個の秘密情報が識別され、ｊによりデータサーバ１４Ｐ１、１４Ｐ２、１４Ｐ３、・・・（１４Ｐｊ）が識別される。分散値の更新は以前の更新に用いた値uｉｊ（ｔ-１）を現在の分散値Ｗｉｊ（ｔ-１）から引くことで最初の分散値に戻し、同時に新たな更新値uｉｊ（ｔ）を加えることで新たな分散値を生成する。
【００７３】
ここで、本実施の形態における計算は基本的にＺ/ｐＺ（pは分散値生成時に用いた素数）上で行われるものとする。時点ｔにおいて以下の手順で更新を行う。ただし、オーナは時点０ではそれ以前の更新用の鍵ｋｅｙ２ｊ（ｔ-１）（ｊ＝ｎ-ｋ＋２,・・・,ｎ）を保持していないので、最初の更新ではuｉｊ（ｔ-１）＝０として計算すればよい。
【００７４】
［更新］
図３には、端末装置１２が実行する鍵送信プログラムを示すフローチャートが示され、図４には、データサーバ１４Ｐｊが実行する分散値更新プログラムを示すフローチャートが示されている。
【００７５】
図３に示すように、ステップ４０で、端末装置１２は自身に、ｋ−１個の新たな更新用の鍵ｋｅｙ２ｊ（ｔ）（ｊ＝ｎ-ｋ＋２,・・・,ｎ）を設定する。ステップ４２で、端末装置１２は、分散値を更新するための乱数を以前生成するために用いた更新用の鍵ｋｅｙ２ｊ（ｔ-１）（ｊ＝ｈ＋１,・・・,ｎ）と、今回新たに分散値を更新するための乱数を生成するための鍵ｋｅｙ２ｊ（ｔ）（ｊ＝ｈ+１,・・・,ｎ）とを、ｊにより識別される対応するデータサーバ１４Ｐｊに送信する。
【００７６】
図４に示すように、ステップ５０で、データサーバ１４Ｐｊは、端末装置１２から送信された鍵ｋｅｙ２ｊ（ｔ-１）と鍵ｋｅｙ２ｊ（ｔ）とを受信する。なお、ステップ５０は、請求項２の受信手段の受信、請求項１０の受信工程の１例である。
【００７７】
端末装置１２から1個のデータサーバに対して２個の鍵（鍵ｋｅｙ２ｊ（ｔ-１）と鍵ｋｅｙ２ｊ（ｔ））が送信される。よって、ｍ個の秘密情報は送られた鍵から生成される乱数によって、一括して更新されるため、秘密情報分散復元検証システムの全体での通信回数は、２ｄ回、即ち、最大２（ｋ−２）回である。
【００７８】
ステップ５２で、データサーバ１４Ｐｊは、受信した鍵ｋｅｙ２ｊ（ｔ-１）と鍵ｋｅｙ２ｊ（ｔ）とを用いて、ｍ個の更新値（乱数）uｉｊ（ｔ-１）とuｉｊ（ｔ）を生成する。uｉｊ（ｔ-１）は、式（１４）において、ｋｅｙ２ｊ（ｔ）に代えてｋｅｙ２ｊ（ｔ-１）を用いる。なお、ステップ５２は、請求項１、２の乱数の生成、請求項９、１０の乱数生成工程の１例である。
【００７９】
【数７】
2018005089.tif 000009
【００８０】
ここで、新しい分散値Ｗｉ（ｔ）と差分uｉは式（１５）、（１６）のように表されるものとする。ａｉ１（ｔ）,・・・,ａｉｋ−１（ｔ）は分散式の係数である。
【００８１】
【数８】
2018005089.tif 000010
【００８２】
ステップ５４で、データサーバ１４Ｐｊは、式（１７）に従って、現在の分散値Ｗｉｊ（ｔ-１）から、ステップ５２で生成した以前の更新値uｉｊ（ｔ-１）を引くことで、最初の分散値に戻し、最初の分散値に、ステップ５２で生成された新たな更新値uｉｊ（ｔ）を加えることで新たな分散値Ｗｉｊ（ｔ）を得る。式（１７）はＨｅｒｚｂｅｒｇ法における式（９）に相当する。なお、ステップ５４は、請求項１、２の演算手段の演算、請求項９、１０の演算工程の１例である。
【００８３】
【数９】
2018005089.tif 000011
【００８４】
ステップ５６で、データサーバ１４Ｐｊは、以前の分散値Ｗｉｊ（ｔ-１）、更新用の鍵ｋｅｙ２ｊ（ｔ-１）、及び鍵ｋｅｙ２ｊ（ｔ）を消去する。
【００８５】
最終的に、オーナの端末装置１２はｈ個の非対称秘密分散用の鍵Ｅｉｄ（ｊ）（ｊ＝１,・・・,ｈ）と最新のｋ−１個の更新用の鍵ｋｅｙ２ｊ（ｔ）（ｊ＝ｎ-ｋ＋２,・・・,ｎ）を持つことになる。
【００８６】
以上によって、データサーバ１４Ｐｊが管理する全分散値が更新される。
【００８７】
前述したように本実施の形態では、分散値の数が膨大であっても、定められた回数の通信だけで分散値を更新することができる。本実施の形態では、ｎ＝４，ｍ＝１００００に対して２（ｋ-２）、即ち、２ｄ回、すなわち、１つの秘密情報について最大４回（ｎ＝ｋの場合）の通信で分散値を更新することができる。これによって、従来の方法の１２万回に比べて非常に大きな通信量の削減を実現することがわかる。さらに本実施の形態では、全データサーバを解析されても秘密情報を含め更新情報も全く漏洩しない方法が実現できる。
【００８８】
上記例では、ステップ５４で、最初の分散値に新たな更新値uｉｊ（ｔ）を加えているが、本発明はこれに限定されず、第１の変形例として、ステップ５４では、最初の分散値と新たな更新値uｉｊ（ｔ）との減算、乗算、商算の何れかをして、新たな分散値Ｗｉｊ（ｔ）を得るようにしてもよい。
【００８９】
また、上記実施の形態及び第１の変形例では、データサーバ１４Ｐｊは、端末装置１２から送信された鍵ｋｅｙ２ｊ（ｔ-１）と鍵ｋｅｙ２ｊ（ｔ）とを受信するようにしているが、本発明はこれに限定されず、第２の変形例として、ステップ５０では、データサーバ１４Ｐｊが鍵ｋｅｙ２ｊ（ｔ-１）と鍵ｋｅｙ２ｊ（ｔ）を生成し、ステップ５２では、鍵ｋｅｙ２ｊ（ｔ-１）と鍵ｋｅｙ２ｊ（ｔ）とを用いて、ｍ個の更新値（乱数）uｉｊ（ｔ-１）とuｉｊ（ｔ）を生成してもよい。なお、第２の変形例のステップ５０は、請求項３の鍵生成手段の生成、請求項１１の鍵生成工程の１例であり、第２の変形例のステップ５２は、請求項１、３の乱数生成手段の生成、請求項９、１１の乱数生成工程の１例である。
【００９０】
更に、更新用の鍵もオーナの端末装置１２が管理する１つの鍵から生成してもよい。
【００９１】
前述した分散値の更新方法は、Ｓhａｍｉr法だけでなく、（ｋ,ｎ）秘密分散法全般に対して適用するようにしてもよい。
【００９２】
（復元）
次に、更新後において１つの秘密情報ｓｉを復元する方法を示す（ｍ個の秘密情報のうち１つの秘密情報をｓｉとする）。
【００９３】
図５には、オーナの端末装置１２が実行する分散値更新及び秘密情報復元プログラムのフローチャートが、図６には、データサーバ１４Ｐｊが実行する分散値送信プログラムのフローチャートが示されている。
【００９４】
図５のステップ６０で、オーナの端末装置１２は、自身の非対称秘密分散用の鍵Ｅｉｄ（ｊ）（ｊ＝１,・・・,ｈ）を用いてｈ個の疑似乱数ｑｉｊ （ｊ＝１,・・・,ｈ）を、式（１８）に従って生成する。
【００９５】
ｑｉｊ＝Ｅｎｃ（ｄＩＤ［ｓｉ］,Ｅｉｄ（ｊ）） （ｊ＝１,・・・,ｈ）    （１８）
ステップ６２で、端末装置１２は、ｋ-ｈ個のデータサーバ１４Ｐｊ（ｊ＝ｈ＋１,・・・,ｋ）を選択し、選択したデータサーバ１４Ｐｊ（ｊ＝ｈ＋１,・・・,ｋ）に、分散値Ｗｉｊ（ｔ）（ｊ＝ｈ＋１,・・・,ｋ）を送信するように指示する指示信号を送信する。
【００９６】
図６のステップ８２で、データサーバ１４Ｐｊは、指示信号を受信する。ステップ８４で、データサーバ１４Ｐｊは、更新後の分散値Ｗｉｊ（ｔ）（ｊ＝ｈ＋１,・・・,ｋ）を暗号化し、ステップ８６で、データサーバ１４Ｐｊは、暗号化した更新後の分散値Ｗｉｊ（ｔ）（ｊ＝ｈ＋１,・・・,ｋ）を端末装置１２に送信する。
【００９７】
図５のステップ６３で、端末装置１２は、更新後の分散値Ｗｉｊ（ｔ）（ｊ＝ｈ＋１,・・・,ｋ）を受信する。ステップ６４で、端末装置１２は、ｋ−１個の更新用の鍵ｋｅｙ２ｊ（ｔ）（ｊ＝ｎ-ｋ＋２,・・・,ｎ）とｄＩＤ［ｓｉ］とより、式（１９）に従って、ｋ−１個の更新値（乱数）uｉｊ（ｔ）を生成する。なお、ステップ６４は、請求項５の乱数生成手段の生成、請求項１３の乱数生成工程の１例である。
【００９８】
uｉｊ（ｔ）＝Ｅｎｃ（ｄＩＤ［ｓｉ］,ｋｅｙ２ｊ（ｔ））（ｊ＝ｎ-ｋ＋２,・・・,ｎ）   （１９）
ステップ６６で、端末装置１２は、ｋ−１個の更新値（乱数）uｉｊ（ｔ）から式（１６）を連立させて、時点ｔと時点０との分散式の各係数の変化量（ａｉ１（ｔ）-ａｉ１（０））,・・・,（ａｉｋ−１（ｔ）-ａｉｋ−１（０）） を計算する。なお、ステップ６６は、請求項５、６の値計算手段の計算、請求項１３、１４の値計算工程の１例である。
【００９９】
ステップ６８で、端末装置１２は、変化量（ａｉ１（ｔ）-ａｉ１（０））,・・・,（ａｉｋ−１（ｔ）-ａｉｋ−１（０））から疑似乱数ｑｉｊ（ｊ＝１,・・・,ｈ）の差分uｉｊ（ｊ＝１,・・・,ｈ）を計算する。すなわち、オーナは得られた各係数の変化量（ａｉ１（ｔ）-ａｉ１（０））,・・・,（ａｉｋ−１（ｔ）-ａｉｋ−１（０）） とオーナのＩＤであるｘｉ（ｉ＝１,・・・,ｈ）から式（１６）に対応する差分情報（更新値）を計算する。ステップ７０で、端末装置１２は、式（２０）に従って、疑似乱数ｑｉｊ（ｊ＝１,・・・,ｈ）と差分uｉｊ（ｊ＝１,・・・,ｈ）とを加算することにより更新後のオーナの端末装置１２の分散値Ｗｉｊ（ｔ）（ｊ＝１,・・・,ｈ）を得る。なお、ステップ７０は、請求項５、６の分散値計算手段の計算、請求項１３、１４の分散値計算工程の１例である。
【０１００】
Ｗｉｊ（ｔ）＝ｑｉｊ＋uｉｊ （２０）
ステップ７２で、端末装置１２は、ステップ７０で得られたｈ個の分散値Ｗｉｊ（ｔ）（ｊ＝１,・・・,ｈ）と、ステップ６３で、受信したデータサーバ１４Ｐｊ（ｊ＝ｈ＋１,・・・,ｋ）から受信した分散値Ｗｉｊ（ｔ）（ｊ＝ｈ＋１,・・・,ｋ）とより、秘密情報ｓｉを復元する。
【０１０１】
以上説明した例では、ステップ７０で、疑似乱数ｑｉｊ（ｊ＝１,・・・,ｈ）と差分uｉｊ（ｊ＝１,・・・,ｈ）とを加算しているが、本発明はこれに限定されず、変形例として、ステップ７０では、疑似乱数ｑｉｊ（ｊ＝１,・・・,ｈ）と差分uｉｊ（ｊ＝１,・・・,ｈ）との減算、乗算、商算の何れかをして、更新後のオーナの分散値Ｗｉｊ（ｔ）（ｊ＝１,・・・,ｈ）を得るようにしてもよい。
また、以上の例ではオーナが秘密情報を復元する場合を示したが、オーナ以外の許可されたユーザが秘密を復元する場合、図５のステップ６２、６３及び７２はそのユーザが行う。この場合、図６のデータサーバはステップ８２においてそのユーザから指示を受信し、ステップ８４、８６でそのユーザに向けて暗号化した分散値を送信する。
【０１０２】
（ランプ型秘密分散法）
ランプ型秘密分散法に対しては、鍵サーバの数ｈをｈ≦ｋ−１からｈ≦ｋ-Ｌとし、更新用の鍵の数をｋ−１からｋ-Ｌ、すなわちｋｅｙ２ｊ（ｔ） （ｊ＝ｎ-ｋ＋Ｌ＋１,・・・,ｎ）とし、秘密情報をｓｉからｓｉ０,・・・,ｓｉＬ-１として、式（１５）（１６）を以下とする（ａｉＬ（ｔ）,・・・,ａｉｋ−１（ｔ）は乱数）。
【０１０３】
Ｗｉｊ（ｔ）＝ｓｉ０＋ｓｉ１ｘｊ＋・・・＋ｓｉＬ-１ｘｊＬ-１＋ａｉＬ（ｔ）ｘｊＬ＋・・・＋ａｉｋ−１（ｔ）ｘｊｋ−１   （２１）
uｉｊ＝（ａｉＬ（ｔ）-ａｉＬ（０））ｘｊＬ＋・・・＋（ａｉｋ−１（ｔ）-ａｉｋ−１（０））ｘｊｋ−１      （２２）
復号においても記号の対応は同様である。
【０１０４】
また、式（７）の更新式は未知数の数がｋ−Ｌとなることから、データサーバの数をｋ-Ｌ未満とすれば全データサーバが解析されても安全性は維持できる。
【０１０５】
（復元時の検証）
Ｈｅｒｚｂｅｒｇらによる復元時の検証法では、分散値の生成時に分散値生成者は検証鍵
【０１０６】
【数１０】
2018005089.tif 000012
【０１０７】
をブロードキャストする。すなわち、各データサーバは
【０１０８】
【数１１】
2018005089.tif 000013
【０１０９】
を保存する。それに対して本実施の形態では、オーナの端末装置１２はｎをｎ＋１として鍵サーバとしての機能を１つ追加し、ｘｎ＋１に対する分散値（以降、「別サーバの分散値」と呼ぶ）をもつ。ただし、「別サーバの分散値」はオーナのみがアクセス可能とするので、他者は改ざんできないとする。検証時にオーナは以下の処理を行う。
【０１１０】
図７には、端末装置１２が実行する分散値検証プログラムを示すフローチャートが、図８には、データサーバが実行する分散値送信プログラムを示すフローチャートが示されている。
【０１１１】
図７のステップ９２で、端末装置１２は、全てのデータサーバの中から、分散値を送信するように指示する先のデータサーバ１４Ｎｊｊを指定し、指定したデータサーバ１４Ｎｊｊに、分散値を送信するように指示する指示信号を送信する。
【０１１２】
図８のステップ１１２で、データサーバ１４Ｎｊｊは、指示信号を受信し、ステップ１１４で、データサーバ１４Ｎｊｊは、分散値を端末装置１２に送信する。
【０１１３】
図７のステップ９４で、端末装置１２は、分散値を受信する。ステップ９６で、端末装置１２は、自ら生成した分散値（図５のステップ７０）と、ステップ９４で受信した分散値とを用いて上記復元プログラムにおける復元処理を行い、秘密情報ｓｉを復元する。なお、ステップ９６は、請求項７の第１の復元手段の復元、請求項１５の第１の復元工程の１例である。
【０１１４】
ステップ９８で、端末装置１２は、ステップ９４で受信した分散値の一つを、上記「別サーバの分散値」に置き換えて、上記復元処理を行い、秘密情報ｓ’ｉを復元する。なお、ステップ９６は、請求項７の第２の復元手段の復元、請求項１５の第２の復元工程の１例である。
【０１１５】
ステップ１００で、端末装置１２は、受信した全ての分散値について上記ステップ９６、９８を実行したか否かを判断する。受信した全ての分散値について上記ステップ９６、９８を実行していないと判断した場合には、本検証プログラムの検証処理はステップ９６に戻る。受信した全ての分散値について上記ステップ９６、９８を実行したと判断した場合には、ステップ１０２で、端末装置１２は、対応する秘密情報ｓｉとｓ’ｉとが一致しているか否かを判断する。なお、ステップ１０２は、請求項７の検証手段の検証、請求項１５の検証工程の１例である。
【０１１６】
対応する秘密情報ｓｉとｓ’ｉとが一致していれば、端末装置１２は、ステップ１０４で、秘密情報ｓｉが正しく復元されたことを記憶する。対応する秘密情報ｓｉとｓ’ｉとが一致しない場合には、ステップ１０６で、端末装置１２は、送られた分散値は不正であることを記憶する。
【０１１７】
上記において「別のサーバの分散値」を前記図５のステップ６０で生成される疑似乱数ｑｉｊまたはステップ７０で生成されるに示す復元処理中に生成されるＷｉｊ（ｔ）とすることができる。なぜなら、ｑｉｊ及びＷｉｊ（ｔ）はオーナも端末装置１２で生成されるため、その値の正当性が保証されるためである。
【０１１８】
例として簡単のためｎ＝ｋ＝２の場合を考える。この場合、ｈ＝１以外ないので、分散時においてオーナの端末装置１２は１つの非対称秘密分散用の鍵から１つの分散値を生成してデータサーバ１４Ｐｊに保存する。また、ｎをｎ＋１としてｘｎ＋１に対する分散値（別データサーバの分散値）を生成して保存する。ただし、「別のサーバの分散値」を鍵サーバによって生成される分散値とする場合保存は必要ない。
【０１１９】
復元時において、オーナの端末装置１２は、前記鍵から生成した分散値とデータサーバから受信した分散値を用いて秘密情報（第１の秘密情報に対応する）を復元する。このとき、検証処理として端末装置１２は前記鍵から生成した分散値と「別サーバの分散値」を用いて第２の秘密情報を復元する。ｋ＝２である場合、オーナが鍵から生成した分散値と「別サーバの分散値」は、全てオーナが管理する分散値であることから正当な値であることが保証される。よって、復元した第２の秘密情報は正しい。よって、第１の秘密情報と第２の秘密情報が一致すれば、受信した分散値は正しいと言える。データサーバ数が１である場合、上記は必ず言える。
【０１２０】
次に受信した分散値が複数ある場合、例えばｎ＝ｋ＝４,ｈ＝２の場合、データサーバは２個存在する。復元時には２つのデータサーバから分散値が送られ、それらを用いて復元が行われる。このとき、各分散値を「別サーバの分散値」に入れ替えて秘密情報を復元した場合、受信した分散値が２つとも正しければ分散値を入れ替えて行われた２回の復元での秘密情報は変わらない。しかし、どちらか１つが不正な分散値である場合、少なくとも不正な分散値を正しい分散値に入れ替えて復元した秘密情報は異なる。
【０１２１】
前述したように従来のＨｅｒｚｂｅｒｇらによる検証法では、
【０１２２】
【数１２】
2018005089.tif 000014
【０１２３】
を計算し、保存するため大きな計算量と記憶容量を必要とする（生成元ｇは離散対数問題において安全な１０００ｂｉｔ以上の数）。それに対して、本実施の形態による検証法ではｘｎ＋１に対する分散値（別サーバの分散値）を保存するだけであるので、比較的小さな記憶容量でよく、計算量も秘密情報の復元を数回行うだけであるので、
【０１２４】
【数１３】
2018005089.tif 000015
【０１２５】
の計算量よりはるかに小さい。
【０１２６】
＜ 第２の実施の形態＞
次に第２の実施の形態を説明する。なお、第２の実施の形態の構成は、第１の実施の形態構成と同様であるので、その説明を省略する。また、第２の実施の形態の作用は、第１の実施の形態の作用と同様な部分があるので、同様な部分は省略し、異なる部分を説明する。
【０１２７】
第２の実施の形態では、１つのデータサーバには複数のオーナの分散値が保存されている。
【０１２８】
データサーバがハッキングされた場合の対処法を以下に説明する。
【０１２９】
最も簡単な対処法は、オーナ毎に第１の実施の形態に示す手法で分散値の更新を行うことである。この場合、データサーバは秘密情報を識別するＩＤだけでなく、オーナを識別するＩＤもまた関連付けて分散値を保存している必要があり、オーナ毎に指定された更新用の鍵で分散値更新を行う。
【０１３０】
もう１つの方法はデータサーバが１つの更新鍵を定めて、その更新鍵と秘密情報を識別するＩＤとから全分散値に対する更新値を生成して、生成した更新値を各分散値に加算し、各オーナにその更新鍵を安全に送信する方法である。この場合、秘密情報のＩＤが異なっていればデータサーバはオーナの区別なく１つの鍵を用いて乱数を発生し、分散値更新できる。このとき、そのデータサーバを用いるオーナは同じ更新鍵を用いることになるが、更新鍵をもう１つ定めることができれば、それによってオーナ毎の独立性は回復する。
【０１３１】
例として、ｎ＝ｋ＝３の場合、ｈ＝２とでき、データサーバは１台になる。このとき、データサーバが定めた鍵をオーナの１つの更新用の鍵とし、オーナはもう１つの更新用の鍵を任意に定めることによって各オーナの更新鍵を個別化できる。
【０１３２】
＜ 第３の実施の形態＞
次に第３の実施の形態を説明する。なお、第３の実施の形態の構成は、第１の実施の形態構成と同様であるので、その説明を省略する。また、第３の実施の形態の作用は、第１の実施の形態の作用と同様な部分があるので、同様な部分は省略し、異なる部分を説明する。
【０１３３】
第３の実施の形態の非対称秘密分散法及び分散値更新法における擬似乱数生成関数が脆弱化した場合の例を説明する。
【０１３４】
非対称秘密分散法で用いた擬似乱数生成関数であるＥｎｃ（ａ,b）と、更新に用いる擬似乱数生成関数Ｅｎｃ（ａ,b）は同一である必要はなく、任意に変更することができる。
【０１３５】
よって、非対称秘密分散法または提案法において時点ｔ-１で用いた擬似乱数生成関数が脆弱化した場合、時点ｔで用いる擬似乱数生成関数を安全な関数とすれば、非対称秘密分散法で生成した分散値が脆弱化していたとしても、安全な擬似乱数生成関数を用いて新たに生成された分散値は安全な擬似乱数とできる。
【０１３６】
最後に、第１〜第３の実施の形態に示した分散値の更新は、非対称秘密分散法を対象として説明したが、Ｓｈａｍｉｒの秘密分散法など他の秘密分散法に対しても適用可能である。ただし、この場合、データサーバの数をｋ‐１未満にするなどの設定はできない。
【符号の説明】
【０１３７】
１２  端末装置
１４Ｐ１、１４Ｐ２、１４Ｐ３・・・  データサーバ
【図１】
2018005089.tif 000016
【図２】
2018005089.tif 000017
【図３】
2018005089.tif 000018
【図４】
2018005089.tif 000019
【図５】
2018005089.tif 000020
【図６】
2018005089.tif 000021
【図７】
2018005089.tif 000022
【図８】
2018005089.tif 000023