(57)【要約】【課題】従来よりも少ない通信量でシェアを復元することができるシェア復元システムを提供する。【解決手段】ｎ台のシェア復元装置からなるシェア復元システムであって、シェア復元装置は、シェア列を生成する第１シェア列生成部と、分割値を生成する分割値生成部と、分割値を他のシェア復元装置に送信する第１分割値送信部と、コンシステンシーを検証する第１コンシステンシー検証部と、分割値を他のシェア復元装置に送信する第２分割値送信部と、コンシステンシーを検証する第２コンシステンシー検証部と、シェア列を生成する第２シェア列生成部と、ｋ個の平文を取得して出力する復元部とを含む。【選択図】図２
2015135383.tif 000002
【特許請求の範囲】
【請求項１】
ｎ台のシェア復元装置からなるシェア復元システムであって、
ｋを復元しきい値とし、
前記シェア復元装置はｋ個のＲａｍｐ型の平文のシェアを入力とし、
前記ｋ個のＲａｍｐ型の平文のシェアから自装置を生成元とするシェア列を生成する第１シェア列生成部と、
前記シェア列にＲａｍｐ情報伝播アルゴリズムを実行して、各シェア復元装置を送信先とするｎ個の分割値を生成する分割値生成部と、
前記ｎ個の分割値を送信先である他のシェア復元装置のそれぞれに送信する第１分割値送信部と、
コンシステンシーを検証するアルゴリズムを実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第１コンシステンシー検証部と、
受信および生成した全ての分割値のうち自装置を送信先とするｎ個の分割値を他の全てのシェア復元装置に送信する第２分割値送信部と、
所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列、合計ｋ列の各列についてコンシステンシーを検証し、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第２コンシステンシー検証部と、
前記所定のｋ台のシェア復元装置を生成元とする各ｋ個の分割値の列、合計ｋ列の各列にＲａｍｐ情報伝播アルゴリズムによる分割値を復元するアルゴリズムを実行して、前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列を生成する第２シェア列生成部と、
前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個のＲａｍｐ型の平文のシェアにＲａｍｐ型のシェアを復元するアルゴリズムを実行して、ｋ個の平文を取得して出力する復元部と、
を含むシェア復元システム。
【請求項２】
ｎ台のシェア復元装置からなるシェア復元システムであって、
ｋを復元しきい値とし、
前記シェア復元装置はｋ個の線形秘密分散の平文のシェアを入力とし、
前記ｋ個の線形秘密分散の平文のシェアから自装置を生成元とするシェア列を生成する第１シェア列生成部と、
前記シェア列にＲａｍｐ情報伝播アルゴリズムを実行して、各シェア復元装置を送信先とするｎ個の分割値を生成する分割値生成部と、
前記ｎ個の分割値を送信先である他のシェア復元装置のそれぞれに送信する第１分割値送信部と、
コンシステンシーを検証するアルゴリズムを実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第１コンシステンシー検証部と、
受信および生成した全ての分割値のうち自装置を送信先とするｎ個の分割値を他の全てのシェア復元装置に送信する第２分割値送信部と、
所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列、合計ｋ列の各列についてコンシステンシーを検証し、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第２コンシステンシー検証部と、
前記所定のｋ台のシェア復元装置を生成元とする各ｋ個の分割値の列、合計ｋ列の各列にＲａｍｐ情報伝播アルゴリズムによる分割値を復元するアルゴリズムを実行して、前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列を生成する第２シェア列生成部と、
前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個の線形秘密分散の平文のシェアに線形秘密分散のシェアを復元するアルゴリズムを実行して、ｋ個の平文を取得して出力する復元部と、
を含むシェア復元システム。
【請求項３】
ｋを復元しきい値とし、
ｋ個のＲａｍｐ型の平文のシェアを入力とし、
前記ｋ個のＲａｍｐ型の平文のシェアから自装置を生成元とするシェア列を生成する第１シェア列生成部と、
前記シェア列にＲａｍｐ情報伝播アルゴリズムを実行して、各シェア復元装置を送信先とするｎ個の分割値を生成する分割値生成部と、
前記ｎ個の分割値を送信先である他のシェア復元装置のそれぞれに送信する第１分割値送信部と、
コンシステンシーを検証するアルゴリズムを実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第１コンシステンシー検証部と、
受信および生成した全ての分割値のうち自装置を送信先とするｎ個の分割値を他の全てのシェア復元装置に送信する第２分割値送信部と、
所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列、合計ｋ列の各列についてコンシステンシーを検証し、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第２コンシステンシー検証部と、
前記所定のｋ台のシェア復元装置を生成元とする各ｋ個の分割値の列、合計ｋ列の各列にＲａｍｐ情報伝播アルゴリズムによる分割値を復元するアルゴリズムを実行して、前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列を生成する第２シェア列生成部と、
前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個のＲａｍｐ型の平文のシェアにＲａｍｐ型のシェアを復元するアルゴリズムを実行して、ｋ個の平文を取得して出力する復元部と、
を含むシェア復元装置。
【請求項４】
ｋを復元しきい値とし、
ｋ個の線形秘密分散の平文のシェアを入力とし、
前記ｋ個の線形秘密分散の平文のシェアから自装置を生成元とするシェア列を生成する第１シェア列生成部と、
前記シェア列にＲａｍｐ情報伝播アルゴリズムを実行して、各シェア復元装置を送信先とするｎ個の分割値を生成する分割値生成部と、
前記ｎ個の分割値を送信先である他のシェア復元装置のそれぞれに送信する第１分割値送信部と、
コンシステンシーを検証するアルゴリズムを実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第１コンシステンシー検証部と、
受信および生成した全ての分割値のうち自装置を送信先とするｎ個の分割値を他の全てのシェア復元装置に送信する第２分割値送信部と、
所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列、合計ｋ列の各列についてコンシステンシーを検証し、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第２コンシステンシー検証部と、
前記所定のｋ台のシェア復元装置を生成元とする各ｋ個の分割値の列、合計ｋ列の各列にＲａｍｐ情報伝播アルゴリズムによる分割値を復元するアルゴリズムを実行して、前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列を生成する第２シェア列生成部と、
前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個の線形秘密分散の平文のシェアに線形秘密分散のシェアを復元するアルゴリズムを実行して、ｋ個の平文を取得して出力する復元部と、
を含むシェア復元装置。
【請求項５】
ｎ台のシェア復元装置が実行するシェア復元方法であって、
ｋを復元しきい値とし、
前記シェア復元装置はｋ個のＲａｍｐ型の平文のシェアを入力とし、
前記ｋ個のＲａｍｐ型の平文のシェアから自装置を生成元とするシェア列を生成する第１シェア列生成ステップと、
前記シェア列にＲａｍｐ情報伝播アルゴリズムを実行して、各シェア復元装置を送信先とするｎ個の分割値を生成する分割値生成ステップと、
前記ｎ個の分割値を送信先である他のシェア復元装置のそれぞれに送信する第１分割値送信ステップと、
コンシステンシーを検証するアルゴリズムを実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第１コンシステンシー検証ステップと、
受信および生成した全ての分割値のうち自装置を送信先とするｎ個の分割値を他の全てのシェア復元装置に送信する第２分割値送信ステップと、
所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列、合計ｋ列の各列についてコンシステンシーを検証し、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第２コンシステンシー検証ステップと、
前記所定のｋ台のシェア復元装置を生成元とする各ｋ個の分割値の列、合計ｋ列の各列にＲａｍｐ情報伝播アルゴリズムによる分割値を復元するアルゴリズムを実行して、前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列を生成する第２シェア列生成ステップと、
前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個のＲａｍｐ型の平文のシェアにＲａｍｐ型のシェアを復元するアルゴリズムを実行して、ｋ個の平文を取得して出力する復元ステップと、
を実行するシェア復元方法。
【請求項６】
ｎ台のシェア復元装置が実行するシェア復元方法であって、
ｋを復元しきい値とし、
前記シェア復元装置はｋ個の線形秘密分散の平文のシェアを入力とし、
前記ｋ個の線形秘密分散の平文のシェアから自装置を生成元とするシェア列を生成する第１シェア列生成ステップと、
前記シェア列にＲａｍｐ情報伝播アルゴリズムを実行して、各シェア復元装置を送信先とするｎ個の分割値を生成する分割値生成ステップと、
前記ｎ個の分割値を送信先である他のシェア復元装置のそれぞれに送信する第１分割値送信ステップと、
コンシステンシーを検証するアルゴリズムを実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第１コンシステンシー検証ステップと、
受信および生成した全ての分割値のうち自装置を送信先とするｎ個の分割値を他の全てのシェア復元装置に送信する第２分割値送信ステップと、
所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列、合計ｋ列の各列についてコンシステンシーを検証し、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する第２コンシステンシー検証ステップと、
前記所定のｋ台のシェア復元装置を生成元とする各ｋ個の分割値の列、合計ｋ列の各列にＲａｍｐ情報伝播アルゴリズムによる分割値を復元するアルゴリズムを実行して、前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列を生成する第２シェア列生成ステップと、
前記所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個の線形秘密分散の平文のシェアに線形秘密分散のシェアを復元するアルゴリズムを実行して、ｋ個の平文を取得して出力する復元ステップと、
を実行するシェア復元方法。
【請求項７】
コンピュータを、請求項３または４に記載のシェア復元装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、安全に分散されたシェアを一貫性を保ち、不正を検知しつつ復元するシェア復元システム、シェア復元装置、シェア復元方法、プログラムに関する。
【背景技術】
【０００２】
非特許文献１では、Shamirの秘密分散を、一貫性を保ちつつ復元する方法を提案している。本発明が属する技術において、登場人物は秘密分散を使って分散されたデータを保持するパーティPi(0≦i≦n-1)である。データaは秘密分散を用いてn個のシェアと呼ばれる断片([a]0,…,[a]n-1)に分割され、パーティPiがそれぞれ[a]iを持っている。秘密分散のパラメータとしてデータがn個のシェアに分割され、任意のk個のシェアを集めることで復元が可能であり、t台までのパーティの結託に対し安全であるとする。kを復元しきい値、tを安全しきい値とも呼ぶ。この3変数の間にはt<k≦nが成り立つ。
【０００３】
秘密分散を用いる際考慮すべき安全性として、分散されているデータがaのとき、少なくともk個のシェアが正しいシェアならば、攻撃者が不正をしたとしてもa以外の値に復元されることがない、すなわち復元の値が改ざんされることがないというものがある。この性質は、n人が参加すれば自明に満たすことができるが、その際の通信量はO(n2)かかる。非特許文献１において、Beerliova-TrubiniovaとHirtは、復元する秘密分散がShamir秘密分散且つ3t<nのとき、O(n)個の秘密分散値をO(n2)の通信量で復元でき、結果として1つあたりO(n)の通信量で復元できることを示した。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Zuzana Beerliova-Trubiniova and Martin Hirt. Perfectly-secure MPC with linear communication complexity. In Ran Canetti, editor, TCC, Vol. 4948 of Lecture Notes in Computer Science, pp. 213-230. Springer, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
Beerliova-TrubiniovaとHirtの復元方法（非特許文献１の方法）は、復元する秘密分散がShamir秘密分散限定であり、かつ3t<nを充たさなければ、通信量がO(n)とならない問題があった。そこで本発明では、従来よりも少ない通信量でシェアを復元することができるシェア復元システムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のシェア復元システムは、ｎ台のシェア復元装置からなる。ｋを復元しきい値とする。シェア復元装置はｋ個のＲａｍｐ型の平文のシェアを入力とし、第１シェア列生成部と、分割値生成部と、第１分割値送信部と、第１コンシステンシー検証部と、第２分割値送信部と、第２コンシステンシー検証部と、第２シェア列生成部と、復元部を含む。
【０００７】
第１シェア列生成部は、ｋ個のＲａｍｐ型の平文のシェアから自装置を生成元とするシェア列を生成する。分割値生成部は、シェア列にＲａｍｐ情報伝播アルゴリズムを実行して、各シェア復元装置を送信先とするｎ個の分割値を生成する。第１分割値送信部は、ｎ個の分割値を送信先である他のシェア復元装置のそれぞれに送信する。第１コンシステンシー検証部は、コンシステンシーを検証するアルゴリズムを実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する。第２分割値送信部は、受信および生成した全ての分割値のうち自装置を送信先とするｎ個の分割値を他の全てのシェア復元装置に送信する。第２コンシステンシー検証部は、所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列、合計ｋ列の各列についてコンシステンシーを検証し、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する。第２シェア列生成部は、所定のｋ台のシェア復元装置を生成元とする各ｋ個の分割値の列、合計ｋ列の各列にＲａｍｐ情報伝播アルゴリズムによる分割値を復元するアルゴリズムを実行して、所定のｋ台のシェア復元装置それぞれを生成元とするシェア列を生成する。復元部は、所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個のＲａｍｐ型の平文のシェアにＲａｍｐ型のシェアを復元するアルゴリズムを実行して、ｋ個の平文を取得して出力する。
【発明の効果】
【０００８】
本発明のシェア復元システムによれば、従来よりも少ない通信量でシェアを復元することができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施例１のシェア復元システムの概要を示すブロック図。
【図２】本発明の実施例１のシェア復元装置の構成を示すブロック図。
【図３】本発明の実施例１のシェア復元装置の動作を示すフローチャート。
【図４】本発明の実施例２のシェア復元システムの概要を示すブロック図。
【図５】本発明の実施例２のシェア復元装置の構成を示すブロック図。
【図６】本発明の実施例２のシェア復元装置の動作を示すフローチャート。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１１】
≪アルゴリズム、プロトコル≫
以下、本発明で用いられるアルゴリズム、プロトコルについて説明する。本明細書では、通信手順を含まない一連の動作をアルゴリズム、通信手順を含む一連の動作をプロトコルと呼ぶ。秘密分散のパラメータとしてデータがn個のシェアに分割され、任意のk個のシェアを集めることで復元が可能であり、t台までのパーティの結託に対し安全であるとする。kを復元しきい値、tを安全しきい値とも呼ぶ。この3変数の間にはt<k≦nが成り立つ。Ｒａｍｐ情報伝播アルゴリズム(k,n)-RIDAを以下の２つのアルゴリズムの組(RIDA.Split,RIDA.Rec)とする。
【００１２】
＜RIDA.Splitアルゴリズム＞
RIDA.Splitアルゴリズムでは、
【００１３】
【数１】
2015135383.tif 000003
【００１４】
を入力とし、分割値
【００１５】
【数２】
2015135383.tif 000004
【００１６】
をi=0,1,…,n-1について計算し、ｎ個の分割値
【００１７】
【数３】
2015135383.tif 000005
【００１８】
を出力する。
【００１９】
＜RIDA.Recアルゴリズム＞
RIDA.Recアルゴリズムでは、n個のインデクス(0,1,…,n-1)のうち任意のk個のインデクスを(i0,i2,…,ik-1)とし、任意のk個の分割値である
【００２０】
【数４】
2015135383.tif 000006
【００２１】
を入力とし、x座標を前述のインデクス(i0,i2,…,ik-1)とし、y座標を対応する分割値としたk個の座標群である
【００２２】
【数５】
2015135383.tif 000007
【００２３】
のk個の座標点を通るk-1次多項式
【００２４】
【数６】
2015135383.tif 000008
【００２５】
を計算し、当該多項式の0次〜k-1次の項である
【００２６】
【数７】
2015135383.tif 000009
【００２７】
を復号結果として出力する。ランプ型（(k,t,n)-Ramp）を以下の2つのアルゴリズムの組(Ramp.Share,Ramp.Rec)とする。
【００２８】
＜Ramp.Shareアルゴリズム＞
Ramp.Shareアルゴリズムでは、Ramp型の平文空間である
【００２９】
【数８】
2015135383.tif 000010
【００３０】
からランダムに選択したk-t個のRamp型の平文
【００３１】
【数９】
2015135383.tif 000011
【００３２】
を入力とし、Ramp型の平文空間から決定する体
【００３３】
【数１０】
2015135383.tif 000012
【００３４】
からランダムに選択されたｔ個の乱数
【００３５】
【数１１】
2015135383.tif 000013
【００３６】
を用いて、Ramp型の平文のシェア
【００３７】
【数１２】
2015135383.tif 000014
【００３８】
を計算し、ｎ個のRamp型の平文のシェア
【００３９】
【数１３】
2015135383.tif 000015
【００４０】
を出力する。
【００４１】
＜Ramp.Recアルゴリズム＞
Ramp.Recアルゴリズムでは、n個のインデクス(0,1,…,n-1)のうち任意のk個のインデクスを(i1,i2,…,ik)とし、任意のk個のRamp型の平文のシェアである
【００４２】
【数１４】
2015135383.tif 000016
【００４３】
を入力とし、x座標を前述のインデクス(i1,i2,…,ik)とし、y座標を対応するRamp型の平文のシェアとしたk個の座標群である
【００４４】
【数１５】
2015135383.tif 000017
【００４５】
のk個の座標点を通るk-1次多項式
【００４６】
【数１６】
2015135383.tif 000018
【００４７】
を計算し、当該多項式の0次〜k-1次の項である
【００４８】
【数１７】
2015135383.tif 000019
【００４９】
を復号結果として出力する。
【００５０】
線型秘密分散は2つのアルゴリズム(Lin.Share,Lin.Rec)の組であり、復元が線形式で記述可能な秘密分散のことである。特に本明細書では閾値を持つような線形秘密分散であり、(t,n)-Linearとかく。ここで、線型秘密分散ではk=t+1なので、kを省略する。線型秘密分散であれば、任意のデータa、任意の
【００５１】
【数１８】
2015135383.tif 000020
【００５２】
であるようなパーティのインデクス集合
【００５３】
【数１９】
2015135383.tif 000021
【００５４】
について、線形秘密分散の復元係数と任意のデータaの線形秘密分散のシェアの線形結合がaと等しくなる、つまり
【００５５】
【数２０】
2015135383.tif 000022
【００５６】
であるような公知の線形秘密分散の復元係数
【００５７】
【数２１】
2015135383.tif 000023
【００５８】
が存在する。特に区別するとき、(k,t,n)-Rampおよび(t,n)-Linearのシェアをそれぞれ[a]Ramp,[a]Linと書く。(k,t,n)-Rampに対する復元方法は後述するprotocol1であり、(t,n)-Linearに対する復元方法は後述するprotocol2である。
【００５９】
＜CheckConsistencyアルゴリズム＞
本発明で用いられるCheckConsistencyアルゴリズムとはコンシステンシー（consistency）と呼ばれる「n個のシェアのうちどのk個のシェアを用いても同じ値が復元される」性質が満たされているかチェックするものであり、例えば、n個のシェアのうち全てのk個のシェアの組に対して復元を行い、同じ値が復元されるかどうかチェックするという方法がある。また、(k,n)-RIDAであれば後述するalgorithm3でもよいし、(t,n)-Linearであれば後述するalgorithm4でもよい。［algorithm3:CheckConsistency for (k,n)-RIDA］
【００６０】
以下、Ramp情報伝播アルゴリズムにおける分割値のコンシステンシーを検証するalgorithm3について説明する。algorithm3は、後述する実施例１および２のステップＳ１１６において、第２コンシステンシー検証部１１６が実行するアルゴリズムである。このアルゴリズムでは、任意のｎ個の分割値
【００６１】
【数２２】
2015135383.tif 000024
【００６２】
を入力とし、true信号、またはfalse信号を出力する。具体的には、k≦i≦n-1(i=k,k+1,…,n-1)について、
【００６３】
【数２３】
2015135383.tif 000025
【００６４】
であれば、false信号を出力し、そうでなければtrue信号を出力する。
［algorithm4:CheckConsistency for (t,n)-Linear］
【００６５】
以下、線形秘密分散のシェアのコンシステンシーを検証するalgorithm4について説明する。algorithm4は、後述する実施例２のステップＳ２１４において、第１コンシステンシー検証部２１４が実行するアルゴリズムである。このアルゴリズムでは、任意のｎ個の線形秘密分散の平文のシェア
【００６６】
【数２４】
2015135383.tif 000026
【００６７】
を入力とし、true信号、またはfalse信号を出力する。具体的には、パラメータ用のインデクスの集合が
【００６８】
【数２５】
2015135383.tif 000027
【００６９】
かつ
【００７０】
【数２６】
2015135383.tif 000028
【００７１】
であるものとし、
Vに含まれるインデクスｌを選び，
検証用インデクスの集合を
【００７２】
【数２７】
2015135383.tif 000029
【００７３】
とし、
インデクスの集合Vに含まれない各iについて、
【００７４】
【数２８】
2015135383.tif 000030
【００７５】
である場合には、false信号を出力し、そうでなければtrue信号を出力する。
【実施例１】
【００７６】
以下、図１を参照して実施例１のシェア復元システムの概要について説明する。図１は本実施例のシェア復元システム１の概要を示すブロック図である。図１に示すように、本実施例のシェア復元システム１は、ｎ台のシェア復元装置１１−１，１１−２，…，１１−ｎからなる。ｎ台のシェア復元装置１１−１，１１−２，…，１１−ｎは、ＮＷ９を介して通信可能に接続されている。ｎ台のシェア復元装置１１−１，１１−２，…，１１−ｎは全て同じ機能を備えるため、これらの代表として、以下シェア復元装置１１について述べる。なお、シェア復元装置１１が実行する一連の通信手順（プロトコル）をprotocol1と呼ぶ。
【００７７】
以下、図２を参照してシェア復元装置１１の構成を説明する。図２は本実施例のシェア復元装置１１の構成を示すブロック図である。図２に示すように、シェア復元装置１１は第１シェア列生成部１１１と、分割値生成部１１２と、第１分割値送信部１１３と、第１コンシステンシー検証部１１４と、第２分割値送信部１１５と、第２コンシステンシー検証部１１６と、第２シェア列生成部１１７と、復元部１１８を含む。シェア復元装置１１はｋ個のＲａｍｐ型の平文のシェアを入力とする。シェア復元装置１１への入力は、
【００７８】
【数２９】
2015135383.tif 000031
【００７９】
と表す。なお、ｋを復元しきい値とする。
【００８０】
以下、図３を参照してシェア復元装置１１の動作を説明する。図３は、本実施例のシェア復元装置１１の動作を示すフローチャートである。なお、ｎ台のシェア復元装置のインデクスをi=0,1,2,…,n-1と表すものとし、し、Piをインデクスi番目のシェア復元装置を表すものとする。図３に示すように、第１シェア列生成部１１１は、ｋ個のＲａｍｐ型の平文のシェアから自装置を生成元とするシェア列を生成する（Ｓ１１１）。本ステップで生成されるシェア列を
【００８１】
【数３０】
2015135383.tif 000032
【００８２】
と表し、各文字の右下に付与した下付き文字は、生成元の装置のインデックスを意味するものとする。従って、
【００８３】
【数３１】
2015135383.tif 000033
【００８４】
は、インデクスiのシェア復元装置Piで生成されたシェア列を意味する。なお、以下ではインデクスiを自装置を表すインデクスとする。本発明において、シェア復元装置はｎ台であるため、ステップＳ１１１が実行されることにより、システム全体でシェア列は合計ｎ個生成される。分割値生成部１１２は、シェア列にＲａｍｐ情報伝播アルゴリズム（前述したRIDA.Splitアルゴリズム）を実行して、各シェア復元装置を送信先とするｎ個の分割値を生成する（Ｓ１１２）。本ステップで生成されるｎ個の分割値を、
【００８５】
【数３２】
2015135383.tif 000034
【００８６】
と表すこととし、ステップＳ１１２を、
【００８７】
【数３３】
2015135383.tif 000035
【００８８】
と表す。なお、ｎ個の各分割値の右肩に示したカッコつきの上付き文字(0),…,(n-1)は、それぞれ、送信先のシェア復元装置のインデクスを示している。第１分割値送信部１１３は、ｎ個の分割値を送信先である他のシェア復元装置のそれぞれに送信する（Ｓ１１３）。つまりステップＳ１１３は、インデクスjを0≦j≦n-1（j=0,1,…,n-1，全装置のインデクス）かつ、j≠i（自装置を含まないインデクス）とし、
【００８９】
【数３４】
2015135383.tif 000036
【００９０】
と表現できる。第１コンシステンシー検証部１１４は、コンシステンシーを検証するアルゴリズムを実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する（Ｓ１１４）。より詳細には、第１コンシステンシー検証部１１４は、あるｋ個のシェア復元装置を生成元とし自装置を送信先とするｋ個の分割値から計算される分割値が、計算に用いられなかったｎ−ｋ個のシェア復元装置を生成元とし自装置を送信先とする分割値のそれぞれと等しくない場合に、リジェクトシンボル（┴）を出力して処理を停止する（Ｓ１１４）。あるｋ個のシェア復元装置を生成元とし自装置を送信先とするｋ個の分割値から計算される分割値は、あるｋ個のシェア復元装置のインデクスをm=0,1,…,k-1と表現すれば、
【００９１】
【数３５】
2015135383.tif 000037
【００９２】
と計算できる。ここでインデクスjをk≦j≦n-1（j=k,k+1,…,n-1）として、前述のｋ個の装置以外のｎ−ｋ個のシェア復元装置のインデクスを表すものとすると、計算に用いられなかったｎ−ｋ個のシェア復元装置を生成元とし自装置を送信先とする分割値は、
【００９３】
【数３６】
2015135383.tif 000038
【００９４】
と表せる。従ってステップＳ１１４は、
【００９５】
【数３７】
2015135383.tif 000039
【００９６】
と表される。第２分割値送信部１１５は、受信および生成した全ての分割値のうち自装置を送信先とするｎ個の分割値を他の全てのシェア復元装置に送信する（Ｓ１１５）。前述のように自装置のインデクスをiで表すため、自装置を送信先とするｎ個の分割値は、右肩に送信先である自装置のインデクス(i)、右下に生成元である各装置のインデクス0,1,…,n-1を付与して
【００９７】
【数３８】
2015135383.tif 000040
【００９８】
と表される。従って、ステップＳ１１５は、0≦j≦n-1(j=0,1,…,n-1，全装置のインデクス)かつ、j≠i（自装置を含まないインデクス）とし、
【００９９】
【数３９】
2015135383.tif 000041
【０１００】
と表される。第２コンシステンシー検証部１１６は、所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列、合計ｋ列の各列についてコンシステンシーを検証するCheckConsistencyアルゴリズム（例えば、前述したalgorithm3）を実行してコンシステンシーを検証し、検証が失敗である場合にリジェクトシンボル（┴）を出力して処理を停止する（Ｓ１１６）。0≦j≦k-1(j=0,1,…,k-1)とすれば、所定のｋ台のシェア復元装置を生成元とする各ｎ個の分割値の列は、
【０１０１】
【数４０】
2015135383.tif 000042
【０１０２】
と表される。すなわちステップＳ１１６は、0≦j≦k-1(j=0,1,…,k-1)として、
【０１０３】
【数４１】
2015135383.tif 000043
【０１０４】
と表される。第２シェア列生成部１１７は、所定のｋ台のシェア復元装置を生成元とする各ｋ個の分割値の列、合計ｋ列の各列にＲａｍｐ情報伝播アルゴリズムによる分割値を復元するアルゴリズム（前述したRIDA.Recアルゴリズム）を実行して、所定のｋ台のシェア復元装置それぞれを生成元とするシェア列を生成する（Ｓ１１７）。すなわち、ステップＳ１１７は、0≦j≦k-1(j=0,1,…,k-1)として、
【０１０５】
【数４２】
2015135383.tif 000044
【０１０６】
と表される。復元部１１８は、所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個のＲａｍｐ型の平文のシェアにＲａｍｐ型のシェアを復元するアルゴリズム（前述のRamp.Recアルゴリズム）を実行して、ｋ個の平文を取得して出力する（Ｓ１１８）。すなわち、ステップＳ１１８は、0≦j≦k-1(j=0,1,…,k-1)として、
【０１０７】
【数４３】
2015135383.tif 000045
【０１０８】
と表される。このように、シェア復元装置１１はｋ個の平文
【０１０９】
【数４４】
2015135383.tif 000046
【０１１０】
を出力する。本実施例のシェア復元システム１（シェア復元装置１１）によれば、n≧2t+1（ただしtは安全しきい値）の場合であっても、シェア１つあたりO(n)の通信量で復元可能となる。また、Shamir秘密分散だけでなく、Ramp型にも適応可能である。本実施例のシェア復元システム１（シェア復元装置１１）は、RIDAに埋め込んだ後、a(0),…,a(k-1)からa(k)が線形式で記述可能であることを用いてステップＳ１１４のように、復元せずにコンシステンシーの検証を可能とした点がポイントである。
【実施例２】
【０１１１】
以下、図４を参照して線形秘密分散のシェアを復元する実施例２のシェア復元システムの概要について説明する。図４は本実施例のシェア復元システム２の概要を示すブロック図である。図４に示すように、本実施例のシェア復元システム２は、ｎ台のシェア復元装置２１−１，２１−２，…，２１−ｎからなる。ｎ台のシェア復元装置２１−１，２１−２，…，２１−ｎは、ＮＷ９を介して通信可能に接続されている。ｎ台のシェア復元装置２１−１，２１−２，…，２１−ｎは全て同じ機能を備えるため、これらの代表として、以下シェア復元装置２１について述べる。なお、シェア復元装置２１が実行する一連の通信手順（プロトコル）をprotocol2と呼ぶ。
【０１１２】
以下、図５を参照してシェア復元装置２１の構成を説明する。図５は本実施例のシェア復元装置２１の構成を示すブロック図である。図５に示すように、シェア復元装置２１は第１シェア列生成部２１１と、分割値生成部１１２と、第１分割値送信部１１３と、第１コンシステンシー検証部２１４と、第２分割値送信部１１５と、第２コンシステンシー検証部１１６と、第２シェア列生成部１１７と、復元部２１８を含む。実施例１との違いは、第１シェア列生成部２１１、第１コンシステンシー検証部２１４、復元部２１８のみである。従って、実施例１と同一番号を付した各構成要件については説明を略する。
【０１１３】
シェア復元装置２１はｋ個の線形秘密分散の平文のシェアを入力とする。シェア復元装置２１への入力は、
【０１１４】
【数４５】
2015135383.tif 000047
【０１１５】
と表す。
【０１１６】
第１シェア列生成部２１１は、ｋ個の線形秘密分散の平文のシェアから自装置を生成元とするシェア列を生成する（Ｓ２１１）。すなわち、ステップＳ２１１は、
【０１１７】
【数４６】
2015135383.tif 000048
【０１１８】
と表される。第１コンシステンシー検証部２１４は、コンシステンシーを検証するアルゴリズム（前述のalgorithm4）を実行して分割値のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボルを出力して処理を停止する（Ｓ２１４）。従って、ステップＳ２１４は、
【０１１９】
【数４７】
2015135383.tif 000049
【０１２０】
と表される。復元部２１８は、所定のｋ台のシェア復元装置それぞれを生成元とするシェア列から取得したｋ個の線形秘密分散の平文のシェアに線形秘密分散のシェアを復元するアルゴリズム（前述したLin.Recアルゴリズム）を実行して、ｋ個の平文を取得して出力する（Ｓ２１８）。0≦j≦k-1(j=0,1,…,k-1)とし、ステップＳ２１８は、
【０１２１】
【数４８】
2015135383.tif 000050
【０１２２】
と表される。このように、シェア復元装置１１はｋ個の平文
【０１２３】
【数４９】
2015135383.tif 000051
【０１２４】
を出力する。本実施例のシェア復元システム２（シェア復元装置２１）によれば、n≧2t+1（ただしtは安全しきい値）の場合であっても、シェア１つあたりO(n)の通信量で復元可能となる。また、Shamir秘密分散だけでなく、線形秘密分散にも適応可能である。本実施例のシェア復元システム２（シェア復元装置２１）は、RIDAに埋め込んだ後、a(0),…,a(k-1)からa(k)が線形式で記述可能であることを用いてステップＳ２１４のように、復元せずにコンシステンシーの検証を可能とした点がポイントである。
【０１２５】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１２６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１２７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１３０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2015135383.tif 000052
【図２】
2015135383.tif 000053
【図３】
2015135383.tif 000054
【図４】
2015135383.tif 000055
【図５】
2015135383.tif 000056
【図６】
2015135383.tif 000057