(57)【要約】【課題】線形秘密分散からRamp型にシェアを変換することができるシェア変換システムを提供する。【解決手段】シェア変換検証装置は、第１乱数生成部、線形Ｒａｍｐ変換部、Ｒａｍｐ線形変換部を含む。シェア変換装置は、第２乱数生成部、線形Ｒａｍｐ変換部、Ｒａｍｐ線形変換部を含む。第１、第２乱数生成部はハイパーインバーティブル行列を入力とし、Ｒａｍｐ型の変換用乱数のシェアと線形秘密分散の変換用乱数のシェア群を出力する。線形Ｒａｍｐ変換部はＲａｍｐ型の変換用乱数のシェアと線形秘密分散の変換用乱数のシェア群と線形秘密分散の平文のシェア群を入力とし、Ｒａｍｐ型の平文のシェアを出力する。Ｒａｍｐ線形変換部はＲａｍｐ型の変換用乱数のシェアと線形秘密分散の変換用乱数のシェア群とＲａｍｐ型の平文のシェアを入力とし、線形秘密分散の平文のシェア群を出力する。【選択図】図２
2015135382.tif 000002
【特許請求の範囲】
【請求項１】
ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、２ｔ台のシェア変換検証装置と、ｎ−２ｔ台のシェア変換装置からなるシェア変換システムであって、
前記シェア変換検証装置と前記シェア変換装置は、線形Ｒａｍｐ変換部を含むものとし、
Ｒａｍｐ型の変換用乱数と線形秘密分散の変換用乱数とが等しくなるものとし、
前記線形Ｒａｍｐ変換部は、
ｋ−ｔ個の線形秘密分散の平文のシェア群と、前記Ｒａｍｐ型の変換用乱数のシェアと、前記線形秘密分散の変換用乱数のシェア群を入力とし、
前記線形秘密分散の平文のシェア群の各シェアと、前記各シェアに対応する前記線形秘密分散の変換用乱数のシェア群の各シェアの差分に基づいて、乱数でマスクされた平文の線形秘密分散のシェア群を生成する被マスク平文線形シェア群生成部と、
乱数でマスクされた平文を復元するアルゴリズムを実行して前記乱数でマスクされた平文の線形秘密分散のシェア群を復元する被マスク平文線形シェア群復元部と、
前記Ｒａｍｐ型の変換用乱数のシェアと前記乱数でマスクされた平文の多項式の加算値からＲａｍｐ型の平文のシェアを生成して出力するＲａｍｐ型平文シェア生成部とを含む
シェア変換システム。
【請求項２】
ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、２ｔ台のシェア変換検証装置と、ｎ−２ｔ台のシェア変換装置からなるシェア変換システムであって、
前記シェア変換検証装置と前記シェア変換装置は、Ｒａｍｐ線形変換部を含むものとし、
Ｒａｍｐ型の変換用乱数と線形秘密分散の変換用乱数とが等しくなるものとし、
前記Ｒａｍｐ線形変換部は、
Ｒａｍｐ型の平文のシェアと、前記Ｒａｍｐ型の変換用乱数のシェアと、前記線形秘密分散の変換用乱数のシェア群を入力とし、
前記Ｒａｍｐ型の平文のシェアと、前記Ｒａｍｐ型の変換用乱数のシェアの差分に基づいて、乱数でマスクされた平文のＲａｍｐ型のシェアを生成する被マスク平文Ｒａｍｐシェア生成部と、
乱数でマスクされた平文を復元するアルゴリズムを実行して前記乱数でマスクされた平文のＲａｍｐ型のシェアを復元する被マスク平文Ｒａｍｐシェア復元部と、
前記線形秘密分散の変換用乱数のシェア群と前記乱数でマスクされた平文群の加算値から線形秘密分散の平文のシェア群を生成して出力する線形秘密分散平文シェア群生成部とを含む
シェア変換システム。
【請求項３】
請求項１に記載のシェア変換システムであって、
前記シェア変換検証装置と、前記シェア変換装置がさらに、
Ｒａｍｐ線形変換部を含み、
前記Ｒａｍｐ線形変換部は、
前記Ｒａｍｐ型の平文のシェアと、前記Ｒａｍｐ型の変換用乱数のシェアと、前記線形秘密分散の変換用乱数のシェア群を入力とし、
前記Ｒａｍｐ型の平文のシェアと、前記Ｒａｍｐ型の変換用乱数のシェアの差分に基づいて、乱数でマスクされた平文のＲａｍｐ型のシェアを生成する被マスク平文Ｒａｍｐシェア生成部と、
乱数でマスクされた平文を復元するアルゴリズムを実行して前記乱数でマスクされた平文のＲａｍｐ型のシェアを復元する被マスク平文Ｒａｍｐシェア復元部と、
前記線形秘密分散の変換用乱数のシェア群と前記乱数でマスクされた平文群の加算値から前記線形秘密分散の平文のシェア群を生成して出力する線形秘密分散平文シェア群生成部とを含む
シェア変換システム。
【請求項４】
ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、２ｔ台のシェア変換検証装置と、ｎ−２ｔ台のシェア変換装置が実行するシェア変換方法であって、
前記シェア変換検証装置と前記シェア変換装置は、線形Ｒａｍｐ変換ステップを実行し、  Ｒａｍｐ型の変換用乱数と線形秘密分散の変換用乱数とが等しくなるものとし、
前記線形Ｒａｍｐ変換ステップは、
ｋ−ｔ個の線形秘密分散の平文のシェア群と、前記Ｒａｍｐ型の変換用乱数のシェアと、前記線形秘密分散の変換用乱数のシェア群を入力とし、
前記線形秘密分散の平文のシェア群の各シェアと、前記各シェアに対応する前記線形秘密分散の変換用乱数のシェア群の各シェアの差分に基づいて、乱数でマスクされた平文の線形秘密分散のシェア群を生成する被マスク平文線形シェア群生成ステップと、
乱数でマスクされた平文を復元するアルゴリズムを実行して前記乱数でマスクされた平文の線形秘密分散のシェア群を復元する被マスク平文線形シェア群復元ステップと、
前記Ｒａｍｐ型の変換用乱数のシェアと前記乱数でマスクされた平文の多項式の加算値からＲａｍｐ型の平文のシェアを生成して出力するＲａｍｐ型平文シェア生成ステップとを含む
シェア変換方法。
【請求項５】
ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、２ｔ台のシェア変換検証装置と、ｎ−２ｔ台のシェア変換装置が実行するシェア変換方法であって、
前記シェア変換検証装置と前記シェア変換装置は、Ｒａｍｐ線形変換ステップを実行し、
Ｒａｍｐ型の変換用乱数と線形秘密分散の変換用乱数とが等しくなるものとし、
前記Ｒａｍｐ線形変換ステップは、
Ｒａｍｐ型の平文のシェアと、前記Ｒａｍｐ型の変換用乱数のシェアと、前記線形秘密分散の変換用乱数のシェア群を入力とし、
前記Ｒａｍｐ型の平文のシェアと、前記Ｒａｍｐ型の変換用乱数のシェアの差分に基づいて、乱数でマスクされた平文のＲａｍｐ型のシェアを生成する被マスク平文Ｒａｍｐシェア生成ステップと、
乱数でマスクされた平文を復元するアルゴリズムを実行して前記乱数でマスクされた平文のＲａｍｐ型のシェアを復元する被マスク平文Ｒａｍｐシェア復元ステップと、
前記線形秘密分散の変換用乱数のシェア群と前記乱数でマスクされた平文群の加算値から線形秘密分散の平文のシェア群を生成して出力する線形秘密分散平文シェア群生成ステップとを含む
シェア変換方法。
【請求項６】
請求項４に記載のシェア変換方法であって、
前記シェア変換検証装置と、前記シェア変換装置がさらに、
Ｒａｍｐ線形変換ステップを実行し、
前記Ｒａｍｐ線形変換ステップは、
前記Ｒａｍｐ型の平文のシェアと、前記Ｒａｍｐ型の変換用乱数のシェアと、前記線形秘密分散の変換用乱数のシェア群を入力とし、
前記Ｒａｍｐ型の平文のシェアと、前記Ｒａｍｐ型の変換用乱数のシェアの差分に基づいて、乱数でマスクされた平文のＲａｍｐ型のシェアを生成する被マスク平文Ｒａｍｐシェア生成ステップと、
乱数でマスクされた平文を復元するアルゴリズムを実行して前記乱数でマスクされた平文のＲａｍｐ型のシェアを復元する被マスク平文Ｒａｍｐシェア復元ステップと、
前記線形秘密分散の変換用乱数のシェア群と前記乱数でマスクされた平文群の加算値から前記線形秘密分散の平文のシェア群を生成して出力する線形秘密分散平文シェア群生成ステップとを含む
シェア変換方法。
【請求項７】
コンピュータを、請求項１から３のいずれかに記載のシェア変換システムに含まれるシェア変換検証装置として機能させるためのプログラム。
【請求項８】
コンピュータを、請求項１から３のいずれかに記載のシェア変換システムに含まれるシェア変換装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は安全に分散したデータの形式を、元の情報を復元することなく秘密計算できるデータの形式に変換し、またはその逆の変換を行うシェア変換システム、シェア変換方法、プログラムに関する。
【背景技術】
【０００２】
非特許文献１では、Ramp型のシェアを線形秘密分散のシェアに変形する方法を提案している。非特許文献１では、本発明と同様に、登場人物は秘密分散を使って分散されたデータを保持するパーティPi(0≦i≦n-1)である。データaは秘密分散を用いてn個のシェアと呼ばれる断片([a]0,…,[a]n-1)に分割され、パーティPiがそれぞれ[a]iを持っている。秘密分散には多くの実現方法があり、非特許文献１では、本発明と同様にRamp型と線型秘密分散と呼ばれる秘密分散方式を扱っている（それぞれの定義は非特許文献１を参照）。これら2つの秘密分散方式は、互いに異なる特徴を持つ。Ramp型は分散する総データ量が小さく、線型秘密分散は秘密計算と呼ばれる応用が可能である。そのため、Ramp型から線形秘密分散に、線形秘密分散からRamp型に、双方向にデータを変換できれば、その時々の状況によってどちらの方式を使うか選択できる。この変換を実現するため、非特許文献１では、Ramp型から線型秘密分散への変換方法が開示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ryo Kikuchi, Koji Chida, Dai Ikarashi, Koki Hamada, and Katsumi Takahashi. Secret sharing schemes with conversion protocol to achieve short share-size and extendibility to multiparty computation. In Colin Boyd and Leonie Simpson, editors, ACISP, Vol. 7959 of Lecture Notes in Computer Science, pp. 419-434. Springer, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１にはRamp型から線型秘密分散への変換方法が開示されるのみで、線型秘密分散からRamp型への変換方法は示されていない。そこで本発明では、線形秘密分散からRamp型にシェアを変換することができるシェア変換システムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明のシェア変換システムは、ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、２ｔ台のシェア変換検証装置と、ｎ−２ｔ台のシェア変換装置からなる。シェア変換検証装置とシェア変換装置は、線形Ｒａｍｐ変換部を含む。
【０００６】
Ｒａｍｐ型の変換用乱数と線形秘密分散の変換用乱数とが等しくなるものとし、線形Ｒａｍｐ変換部は、ｋ−ｔ個の線形秘密分散の平文のシェア群と、Ｒａｍｐ型の変換用乱数のシェアと、線形秘密分散の変換用乱数のシェア群を入力とする。線形Ｒａｍｐ変換部は、被マスク平文線形シェア群生成部と、被マスク平文線形シェア群復元部と、Ｒａｍｐ型平文シェア生成部を含む。
【０００７】
被マスク平文線形シェア群生成部は、線形秘密分散の平文のシェア群の各シェアと、各シェアに対応する線形秘密分散の変換用乱数のシェア群の各シェアの差分に基づいて、乱数でマスクされた平文の線形秘密分散のシェア群を生成する。被マスク平文線形シェア群復元部は、乱数でマスクされた平文を復元するアルゴリズムを実行して乱数でマスクされた平文の線形秘密分散のシェア群を復元する。Ｒａｍｐ型平文シェア生成部は、Ｒａｍｐ型の変換用乱数のシェアと乱数でマスクされた平文の多項式の加算値からＲａｍｐ型の平文のシェアを生成して出力する。
【発明の効果】
【０００８】
本発明のシェア変換システムによれば、線形秘密分散からRamp型にシェアを変換することができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施例１のシェア変換システムの概要を示すブロック図。
【図２】本発明の実施例１のシェア変換検証装置の構成を示すブロック図。
【図３】本発明の実施例１のシェア変換装置の構成を示すブロック図。
【図４】本発明の実施例１の第１乱数生成部の構成を示すブロック図。
【図５】本発明の実施例１の第１乱数生成部の動作を示すフローチャート。
【図６】本発明の実施例１の第２乱数生成部の構成を示すブロック図。
【図７】本発明の実施例１の第２乱数生成部の動作を示すフローチャート。
【図８】本発明の実施例１の線形Ｒａｍｐ変換部の構成を示すブロック図。
【図９】本発明の実施例１の線形Ｒａｍｐ変換部の動作を示すフローチャート。
【図１０】本発明の実施例１のＲａｍｐ線形変換部の構成を示すブロック図。
【図１１】本発明の実施例１のＲａｍｐ線形変換部の動作を示すフローチャート。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１１】
≪アルゴリズム、プロトコル≫
以下、本発明で用いられるアルゴリズム、プロトコルについて説明する。本明細書では、通信手順を含まない一連の動作をアルゴリズム、通信手順を含む一連の動作をプロトコルと呼ぶ。秘密分散のパラメータとしてデータがn個のシェアに分割され、任意のk個のシェアを集めることで復元が可能であり、t台までのパーティの結託に対し安全であるとする。kを復元しきい値、tを安全しきい値とも呼ぶ。この3変数の間にはt<k≦nが成り立つ。ランプ型（(k,t,n)-Ramp）を以下の2つのアルゴリズムの組(Ramp.Share,Ramp.Rec)とする。
【００１２】
＜Ramp.Shareアルゴリズム＞
Ramp.Shareアルゴリズムでは、Ramp型の平文空間である
【００１３】
【数１】
2015135382.tif 000003
【００１４】
からランダムに選択したk-t個のRamp型の平文
【００１５】
【数２】
2015135382.tif 000004
【００１６】
を入力とし、Ramp型の平文空間から決定する体
【００１７】
【数３】
2015135382.tif 000005
【００１８】
からランダムに選択されたｔ個の乱数
【００１９】
【数４】
2015135382.tif 000006
【００２０】
を用いて、Ramp型の平文のシェア
【００２１】
【数５】
2015135382.tif 000007
【００２２】
を計算し、ｎ個のRamp型の平文のシェア
【００２３】
【数６】
2015135382.tif 000008
【００２４】
を出力する。
【００２５】
＜Ramp.Recアルゴリズム＞
Ramp.Recアルゴリズムでは、n個のインデクス(0,1,…,n-1)のうち任意のk個のインデクスを(i1,i2,…,ik)とし、任意のk個のRamp型の平文のシェアである
【００２６】
【数７】
2015135382.tif 000009
【００２７】
を入力とし、x座標を前述のインデクス(i1,i2,…,ik)とし、y座標を対応するRamp型の平文のシェアとしたk個の座標群である
【００２８】
【数８】
2015135382.tif 000010
【００２９】
のk個の座標点を通るk-1次多項式
【００３０】
【数９】
2015135382.tif 000011
【００３１】
を計算し、当該多項式の0次〜k-1次の項である
【００３２】
【数１０】
2015135382.tif 000012
【００３３】
を復号結果として出力する。
【００３４】
線型秘密分散は2つのアルゴリズム(Lin.Share,Lin.Rec)の組であり、復元が線形式で記述可能な秘密分散のことである。特に本明細書では閾値を持つような線形秘密分散であり、(t,n)-Linearとかく。ここで、線型秘密分散ではk=t+1なので、kを省略する。線型秘密分散であれば、任意のデータa、任意の
【００３５】
【数１１】
2015135382.tif 000013
【００３６】
であるようなパーティのインデクス集合
【００３７】
【数１２】
2015135382.tif 000014
【００３８】
について、線形秘密分散の復元係数と任意のデータaの線形秘密分散のシェアの線形結合がaと等しくなる、つまり
【００３９】
【数１３】
2015135382.tif 000015
【００４０】
であるような公知の線形秘密分散の復元係数
【００４１】
【数１４】
2015135382.tif 000016
【００４２】
が存在する。特に区別するとき、(k,t,n)-Rampおよび(t,n)-Linearのシェアをそれぞれ[a]Ramp,[a]Linと書く。
【００４３】
＜CheckConsistencyアルゴリズム＞
本発明で用いられるCheckConsistencyアルゴリズムとはコンシステンシー（consistency）と呼ばれる「n個のシェアのうちどのk個のシェアを用いても同じ値が復元される」性質が満たされているかチェックするものであり、例えばn個のシェアのうち全てのk個のシェアの組に対して復元を行い、同じ値が復元されるかどうかチェックするという方法がある。また、(k,t,n)-Rampであれば後述するalgorithm2、(t,n)-Linearであれば後述するalgorithm3でもよい。
【００４４】
≪ハイパーインバーティブル行列≫
Beerliova-TrubiniovaとHirt（詳細は参考非特許文献１を参照）は、Hyper-invertible matricesと呼ばれる、任意の小行列が逆行列を持つような行列を定義した。
（参考非特許文献１：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.）
【００４５】
＜ハイパーインバーティブル行列の定義＞
あるn行m列の行列Mがhyper-invertibleであるとは、任意のインデックス集合R⊆{0,…,m-1},C⊆{0,…,n-1},|r|=|C|について、MCRが逆行列を持つことを言う。ただし、MRとはMのi∈Rであるようなi列を持ってきたものであり、MCとはMのi∈Cであるようなi行を持ってきたものであり、MCR=(MR)Cである。Hyper-invertibleな行列Mは、例えば以下のように構成できる。
【００４６】
＜ハイパーインバーティブル行列の構成例＞
α0,…, αn-1,β0,…,βn-1を、任意の体
【００４７】
【数１５】
2015135382.tif 000017
【００４８】
上の相異なる要素とする。関数
【００４９】
【数１６】
2015135382.tif 000018
【００５０】
を、(x0,…,xn-1)を入力としたとき、((α0,x0),…,(αn-1,xn-1))を通るユニークなn-1次多項式g(・)について、((β0,y0),…,(βn-1,yn-1))がg(・)上に乗るような(y0,…,yn-1)を出力とする関数とする。このとき、関数fは行列の要素をλi,jとし、
【００５１】
【数１７】
2015135382.tif 000019
【００５２】
として、行列Mi,j=λi,jを用いた線形変換と見做すことができ、このようなMは、ハイパーインバーティブル（hyper-invertible）である。
【実施例１】
【００５３】
以下、図１を参照して実施例１のシェア変換システムの概要について説明する。図１は本実施例のシェア変換システム１の概要を示すブロック図である。図１に示すように、本実施例のシェア変換システム１は、ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、２ｔ台のシェア変換検証装置１１−１，１１−２，…，１１−２ｔと、ｎ−２ｔ台のシェア変換装置１２−１，１２−２，…，１２−（ｎ−２ｔ）からなる。２ｔ台のシェア変換検証装置１１−１，１１−２，…，１１−２ｔと、ｎ−２ｔ台のシェア変換装置１２−１，１２−２，…，１２−（ｎ−２ｔ）は、ＮＷ９を介して通信可能に接続されている。２ｔ台のシェア変換検証装置１１−１，１１−２，…，１１−２ｔは全て同じ機能を備えるため、これらの代表として、以下シェア変換検証装置１１について述べる。同様に、ｎ−２ｔ台のシェア変換装置１２−１，１２−２，…，１２−（ｎ−２ｔ）は全て同じ機能を備えるため、これらの代表として、以下シェア変換装置１２について述べる。
【００５４】
以下、図２、図３を参照してシェア変換検証装置１１、シェア変換装置１２の構成を説明する。図２は本実施例のシェア変換検証装置１１の構成を示すブロック図である。図３は、本実施例のシェア変換装置１２の構成を示すブロック図である。図２に示すように、シェア変換検証装置１１は、第１乱数生成部１１１と、線形Ｒａｍｐ変換部１１２と、Ｒａｍｐ線形変換部１１３を含む。図３に示すように、シェア変換装置１２は、第２乱数生成部２１１と、線形Ｒａｍｐ変換部１１２と、Ｒａｍｐ線形変換部１１３を含む。シェア変換検証装置１１における第１乱数生成部１１１が、シェア変換装置１２において第２乱数生成部２１１に変更されており、それ以外の点では、シェア変換検証装置１１とシェア変換装置１２は同じである。第１、第２乱数生成部１１１、２１１は、ハイパーインバーティブル行列を入力とし、Ｒａｍｐ型の変換用乱数のシェアと、線形秘密分散の変換用乱数のシェア群を出力する。線形Ｒａｍｐ変換部１１２は、Ｒａｍｐ型の変換用乱数のシェアと、線形秘密分散の変換用乱数のシェア群と、線形秘密分散の平文のシェア群を入力とし、Ｒａｍｐ型の平文のシェアを出力する。Ｒａｍｐ線形変換部１１３は、Ｒａｍｐ型の変換用乱数のシェアと、線形秘密分散の変換用乱数のシェア群と、Ｒａｍｐ型の平文のシェアを入力とし、線形秘密分散の平文のシェア群を出力する。
【００５５】
≪第１乱数生成部１１１≫
以下、図４、図５を参照して第１乱数生成部１１１について説明する。図４は、本実施例の第１乱数生成部１１１の構成を示すブロック図である。図５は、本実施例の第１乱数生成部１１１の動作を示すフローチャートである。第１乱数生成部１１１が実行する一連の通信手順（プロトコル）をprotocol1と呼ぶ。
【００５６】
第１乱数生成部１１１は、ｎ行ｎ列のハイパーインバーティブル行列Ｍ（Hyper-invertible matrix M）を入力とする。図４に示すように、第１乱数生成部１１１は、初期乱数選択部１１１１と、Ｒａｍｐ型初期乱数シェア生成部１１１２と、線形秘密分散初期乱数シェア群生成部１１１３と、初期乱数シェア送信部１１１４と、Ｒａｍｐ型変換用乱数シェア生成部１１１５と、線形秘密分散変換用乱数シェア生成部１１１６と、変換用乱数シェア送信部１１１７と、Ｒａｍｐ型コンシステンシー検証部１１１８と、Ｒａｍｐ型変換用乱数復元部１１１９と、線形秘密分散コンシステンシー検証部１１１Ａと、線形秘密分散変換用乱数群復元部１１１Ｂと、乱数比較部１１１Ｃと、シェア出力部１１１Ｄとを含む。
【００５７】
初期乱数選択部１１１１は、Ｒａｍｐ型の平文空間
【００５８】
【数１８】
2015135382.tif 000020
【００５９】
からｋ−ｔ個の初期乱数
【００６０】
【数１９】
2015135382.tif 000021
【００６１】
をランダムに選択する（Ｓ１１１１）。Ｒａｍｐ型初期乱数シェア生成部１１１２は、ｋ−ｔ個の初期乱数にＲａｍｐ型のシェアを生成するRamp.Shareアルゴリズムを実行してＲａｍｐ型の初期乱数のシェア
【００６２】
【数２０】
2015135382.tif 000022
【００６３】
を生成する（Ｓ１１１２）。線形秘密分散初期乱数シェア群生成部１１１３は、ｋ−ｔ個の初期乱数それぞれについて、線形秘密分散のシェアを生成するLin.Shareアルゴリズムを実行して線形秘密分散の初期乱数のシェア群
【００６４】
【数２１】
2015135382.tif 000023
【００６５】
を生成する（Ｓ１１１３）。ただし、ステップＳ１１１３において、インデクスj=0,1,2,…,k-t-1である。初期乱数シェア送信部１１１４は、Ｒａｍｐ型の初期乱数のシェアと、線形秘密分散の初期乱数のシェア群を自装置を除く他の全装置に送信する（Ｓ１１１４）。ステップＳ１１１４において、装置を文字Pで表すこととし、装置のインデクスj=0,1,2,…,n-1（全ての装置）かつj≠i（自装置を除く）とし、Pjをインデクスj番目の装置とすると、ステップＳ１１１４は、以下のように表すことができる。
【００６６】
【数２２】
2015135382.tif 000024
【００６７】
Ｒａｍｐ型変換用乱数シェア生成部１１１５は、i,j=0,1,2,…,n-1とし、Ｒａｍｐ型の初期乱数のシェアと、ハイパーインバーティブル行列Mに基づいてＲａｍｐ型の変換用乱数のシェア
【００６８】
【数２３】
2015135382.tif 000025
【００６９】
を生成する（Ｓ１１１５）。線形秘密分散変換用乱数シェア生成部１１１６は、i,j=0,1,2,…,n-1とし、m=0,1,…,k-t-1とし、線形秘密分散の初期乱数のシェア群と、ハイパーインバーティブル行列Mに基づいて線形秘密分散の変換用乱数のシェア群
【００７０】
【数２４】
2015135382.tif 000026
【００７１】
を生成する（Ｓ１１１６）。変換用乱数シェア送信部１１１７は、インデクスj=0,1,…,2tとし、Ｒａｍｐ型の変換用乱数のシェアと、線形秘密分散の変換用乱数のシェア群の一部（j=0,1,…,2tに限られる）である
【００７２】
【数２５】
2015135382.tif 000027
【００７３】
を他のシェア変換検証装置に送信する（Ｓ１１１７）。本ステップにおいてインデクスj=0,1,…,2tであるため、Pjは、シェア変換検証装置を表す。従って、ステップＳ１１１７は、
【００７４】
【数２６】
2015135382.tif 000028
【００７５】
と表すことができる。Ｒａｍｐ型コンシステンシー検証部１１１８は、コンシステンシーを検証するCheckConsistencyアルゴリズム（例えば、後述するalgorithm2）を実行してＲａｍｐ型の変換用乱数のシェアのコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボル（┴）を出力して処理を停止する（Ｓ１１１８）。つまり、ステップＳ１１１８は、
【００７６】
【数２７】
2015135382.tif 000029
【００７７】
と表すことができる。Ｒａｍｐ型変換用乱数復元部１１１９は、Ｒａｍｐ型のシェアを復元するRamp.Recアルゴリズムを実行して、Ｒａｍｐ型の変換用乱数のシェアを復元して復元済みＲａｍｐ型変換用乱数
【００７８】
【数２８】
2015135382.tif 000030
【００７９】
を生成する（Ｓ１１１９）。線形秘密分散コンシステンシー検証部１１１Ａは、コンシステンシーを検証するCheckConsistencyアルゴリズム（例えば、後述するalgorithm3）を実行して線形秘密分散の変換用乱数のシェア群のコンシステンシーを検証して、検証が失敗である場合にリジェクトシンボル（┴）を出力して処理を停止する（Ｓ１１１Ａ）。つまり、ステップＳ１１１Ａは、j=0,1,…,k-t-1として、
【００８０】
【数２９】
2015135382.tif 000031
【００８１】
と表すことができる。線形秘密分散変換用乱数群復元部１１１Ｂは、線形秘密分散のシェア群を復元するLin.Recアルゴリズムを実行して、線形秘密分散の変換用乱数のシェアを復元して復元済み線形秘密分散変換用乱数群
【００８２】
【数３０】
2015135382.tif 000032
【００８３】
を生成する（Ｓ１１１Ｂ）。乱数比較部１１１Ｃは、復元済みＲａｍｐ型変換用乱数と復元済み線形秘密分散変換用乱数群とが等しい場合にはアクセプトシンボル（┬）を他の装置に送信し、等しくない場合にはリジェクトシンボル（┴）を出力して処理を停止する（Ｓ１１１Ｃ）。つまり、
【００８４】
【数３１】
2015135382.tif 000033
【００８５】
である。シェア出力部１１１Ｄは、アクセプトシンボル（┬）を２ｔ個（つまり、全てのシェア変換検証装置１１−１，１１−２，…，１１−２ｔから）受信した場合に、Ｒａｍｐ型の変換用乱数のシェアと線形秘密分散の変換用乱数のシェア群のうち、コンシステンシーの検証に用いなかったもの(すなわち、i=2t,…,n-1)
【００８６】
【数３２】
2015135382.tif 000034
【００８７】
を出力する（Ｓ１１１Ｄ）。つまり、
【００８８】
【数３３】
2015135382.tif 000035
【００８９】
である。
【００９０】
＜algorithml2:CheckConsistency for (k,t,n)-Ramp＞
以下、Ramp型のシェアのコンシステンシーを検証するalgorithm2について説明する。algorithm2は、前述のステップＳ１１１８において、Ｒａｍｐ型コンシステンシー検証部１１１８が実行するアルゴリズムである。このアルゴリズムでは、任意のｎ個のRamp型の平文のシェア
【００９１】
【数３４】
2015135382.tif 000036
【００９２】
を入力とし、true信号、またはfalse信号を出力する。具体的には、インデクスi=k,k+1,…,n-1について、
【００９３】
【数３５】
2015135382.tif 000037
【００９４】
であれば、false信号を出力し、そうでなければtrue信号を出力する。ここで、
【００９５】
【数３６】
2015135382.tif 000038
【００９６】
は、あるｋ個のRamp型の平文のシェアから計算されるそれ以外のシェアを意味する。
【００９７】
＜algorithm3:CheckConsistency for (t,n)-Linear＞
以下、線形秘密分散のシェアのコンシステンシーを検証するalgorithm3について説明する。algorithm3は、前述のステップＳ１１１Ａにおいて、線形秘密分散コンシステンシー検証部１１１Ａが実行するアルゴリズムである。このアルゴリズムでは、任意のｎ個の線形秘密分散の平文のシェア
【００９８】
【数３７】
2015135382.tif 000039
【００９９】
を入力とし、true信号、またはfalse信号を出力する。具体的には、パラメータ用のインデクスの集合が
【０１００】
【数３８】
2015135382.tif 000040
【０１０１】
かつ
【０１０２】
【数３９】
2015135382.tif 000041
【０１０３】
であるものとし、
Vに含まれるインデクスｌを選び，
検証用インデクスの集合を
【０１０４】
【数４０】
2015135382.tif 000042
【０１０５】
とし、インデクスの集合Vに含まれない各iについて、
【０１０６】
【数４１】
2015135382.tif 000043
【０１０７】
である場合には、false信号を出力し、そうでなければtrue信号を出力する。
【０１０８】
≪第２乱数生成部２１１≫
次に、図６、図７を参照して第２乱数生成部２１１について説明する。図６は本実施例の第２乱数生成部２１１の構成を示すブロック図である。図７は、本実施例の第２乱数生成部２１１の動作を示すフローチャートである。
【０１０９】
第２乱数生成部２１１は、ハイパーインバーティブル行列Mを入力とする。第２乱数生成部は、初期乱数選択部１１１１と、Ｒａｍｐ型初期乱数シェア生成部１１１２と、線形秘密分散初期乱数シェア群生成部１１１３と、初期乱数シェア送信部１１１４と、Ｒａｍｐ型変換用乱数シェア生成部１１１５と、線形秘密分散変換用乱数シェア生成部１１１６と、変換用乱数シェア送信部１１１７と、シェア出力部１１１Ｄとを含む。第１乱数生成部１１１と第２乱数生成部２１１の違いは、第２乱数生成部２１１が、検証機能を司るＲａｍｐ型コンシステンシー検証部１１１８、Ｒａｍｐ型変換用乱数復元部１１１９、線形秘密分散コンシステンシー検証部１１１Ａ、線形秘密分散変換用乱数群復元部１１１Ｂ、乱数比較部１１１Ｃを含まない点である。他の各構成要件については、第１乱数生成部１１１において同一番号を付した各構成要件の動作と同じであるため、説明を略する。
【０１１０】
以上に述べた第１乱数生成部１１１、第２乱数生成部２１１は、必須の構成ではない。例えば、前述したＲａｍｐ型の変換用乱数と線形秘密分散の変換用乱数とが等しくなるようにして、予めＲａｍｐ型の変換用乱数のシェアと、線形秘密分散の変換用乱数のシェア群とを生成しておけば、第１乱数生成部１１１、第２乱数生成部２１１がなくても、シェア変換検証装置やシェア変換装置を実現することができる。
【０１１１】
≪線形Ｒａｍｐ変換部１１２≫
次に、図８、図９を参照して線形Ｒａｍｐ変換部１１２について説明する。図８は、本実施例の線形Ｒａｍｐ変換部１１２の構成を示すブロック図である。図９は、本実施例の線形Ｒａｍｐ変換部１１２の動作を示すフローチャートである。線形Ｒａｍｐ変換部１１２が実行する一連の通信手順（プロトコル）をprotocol5と呼ぶ。
【０１１２】
線形Ｒａｍｐ変換部１１２は、ｋ−ｔ個の線形秘密分散の平文のシェア群
【０１１３】
【数４２】
2015135382.tif 000044
【０１１４】
と、Ｒａｍｐ型の変換用乱数のシェアと線形秘密分散の変換用乱数のシェア群
【０１１５】
【数４３】
2015135382.tif 000045
【０１１６】
を入力とする。図８に示すように、線形Ｒａｍｐ変換部１１２は、被マスク平文線形シェア群生成部１１２１と、被マスク平文線形シェア群復元部１１２２と、Ｒａｍｐ型平文シェア生成部１１２３を含む。
【０１１７】
被マスク平文線形シェア群生成部１１２１は、線形秘密分散の平文のシェア群の各シェアと、各シェアに対応する線形秘密分散の変換用乱数のシェア群の各シェアの差分に基づいて、乱数でマスクされた平文の線形秘密分散のシェア群を生成する（Ｓ１１２１）。すなわち、i=0,1,…,k-t-1について、乱数でマスクされた平文の線形秘密分散のシェア群
【０１１８】
【数４４】
2015135382.tif 000046
【０１１９】
を生成する。被マスク平文線形シェア群復元部１１２２は、乱数でマスクされた平文を復元するプロトコル(RevealProtocol)を実行して乱数でマスクされた平文の線形秘密分散のシェア群を復元する（Ｓ１１２２）。すなわち、i=0,1,…,k-t-1について、乱数でマスクされた平文
【０１２０】
【数４５】
2015135382.tif 000047
【０１２１】
を生成する。RevealProtocolは復元できるプロトコルであればよく、単純には全員に全員のシェアを渡し、各人がCheckConsistencyを行ったあと復元するという方法で実現できる。Ｒａｍｐ型平文シェア生成部１１２３は、Ｒａｍｐ型の変換用乱数のシェアと乱数でマスクされた平文の多項式
【０１２２】
【数４６】
2015135382.tif 000048
【０１２３】
の加算値からＲａｍｐ型の平文のシェアを生成して出力する（Ｓ１１２３）。すなわち、Ｒａｍｐ型平文シェア生成部１１２３は、i=0,1,…,n-1について、Ｒａｍｐ型の平文のシェア
【０１２４】
【数４７】
2015135382.tif 000049
【０１２５】
を生成して出力する。従って、線形Ｒａｍｐ変換部１１２は、Ｒａｍｐ型の平文のシェア
【０１２６】
【数４８】
2015135382.tif 000050
【０１２７】
を出力する。
【０１２８】
≪Ｒａｍｐ線形変換部１１３≫
次に、図１０、図１１を参照してＲａｍｐ線形変換部１１３について説明する。図１０は、本実施例のＲａｍｐ線形変換部１１３の構成を示すブロック図である。図１１は、本実施例のＲａｍｐ線形変換部１１３の動作を示すフローチャートである。Ｒａｍｐ線形変換部１１３が実行する一連の通信手順（プロトコル）をprotocol4と呼ぶ。
【０１２９】
Ｒａｍｐ線形変換部１１３は、Ｒａｍｐ型の平文のシェアと、Ｒａｍｐ型の変換用乱数のシェアと、線形秘密分散の変換用乱数のシェア群、すなわち
【０１３０】
【数４９】
2015135382.tif 000051
【０１３１】
を入力とする。図１０に示すように、Ｒａｍｐ線形変換部１１３は、被マスク平文Ｒａｍｐシェア生成部１１３１と、被マスク平文Ｒａｍｐシェア復元部１１３２と、線形秘密分散平文シェア群生成部１１３３を含む。
【０１３２】
被マスク平文Ｒａｍｐシェア生成部１１３１は、Ｒａｍｐ型の平文のシェアと、Ｒａｍｐ型の変換用乱数のシェアの差分に基づいて、乱数でマスクされた平文のＲａｍｐ型のシェアを生成する（Ｓ１１３１）。すなわち、
【０１３３】
【数５０】
2015135382.tif 000052
【０１３４】
である。被マスク平文Ｒａｍｐシェア復元部１１３２は、乱数でマスクされた平文を復元するプロトコル(RevealProtocol)を実行して乱数でマスクされた平文のＲａｍｐ型のシェアを復元する（Ｓ１１３２）。すなわち、
【０１３５】
【数５１】
2015135382.tif 000053
【０１３６】
である。
【０１３７】
線形秘密分散平文シェア群生成部１１３３は、線形秘密分散の変換用乱数のシェア群と乱数でマスクされた平文群の加算値から線形秘密分散の平文のシェア群を生成して出力する（Ｓ１１３３）。すなわち、線形秘密分散平文シェア群生成部１１３３は、i=0,1,…,k-t-1について、線形秘密分散の平文のシェア群
【０１３８】
【数５２】
2015135382.tif 000054
【０１３９】
を生成して出力する（Ｓ１１３３）。従って、Ｒａｍｐ線形変換部１１３は、線形秘密分散の平文のシェア群
【０１４０】
【数５３】
2015135382.tif 000055
【０１４１】
を出力する。
【０１４２】
安全性のレベルは、passiveとactiveの2段階存在する。passive安全とは、攻撃者があらかじめ決められた手続き（プロトコル）を逸脱しない場合にのみ安全であることを示す。一方、active安全とは、攻撃者がどのような挙動をしたとしても安全であることを示す。従って、active安全である方がより望ましいといえる。前述の非特許文献１に開示されたRamp型から線型秘密分散への変換方法は、passive安全であるため、安全性が弱いという問題があった。線形秘密分散はその応用として秘密計算への拡張があるが、変換方法がpassiveである場合、秘密計算がactive安全であったとしても、全体としてはpassive安全となってしまう。本実施例のＲａｍｐ線形変換部１１３が実行する変換は、active安全であるるため、従来のRamp型から線型秘密分散への変換方法と比較して安全性が高い。
【０１４３】
本実施例のシェア変換システム１によれば、Ramp型から線形秘密分散に、線形秘密分散からRamp型に、双方向にシェアを変換することができる。すなわち、本実施例のシェア変換システム１によれば、互いに利点・欠点がある2つの秘密分散を相互に変換することが可能となり、場合によって使い分けることができるようになる。例えば、秘密計算において、分散時は総データ量が小さいRamp型を用いストレージコストを抑えておきながら、秘密計算を行う際にのみ秘密計算に拡張可能な線型秘密分散に変更することや、秘密計算に用いたデータをバックアップする際に、総データ量の大きい線型秘密分散から、総データ量の小さいRamp 型秘密分散に変換することができる。すなわち、秘密計算への拡張性を持たせつつ保持するデータ量を削減することが可能となる。本実施例のポイントは、Hyper-invertible matrix Mを用いて、(k,t,n)-Rampと(t,n)-Linearで生成した乱数が正しく同じ乱数を生成しているのかチェックしたことにある。
【０１４４】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１４５】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１４６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１４７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１４８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１４９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2015135382.tif 000056
【図２】
2015135382.tif 000057
【図３】
2015135382.tif 000058
【図４】
2015135382.tif 000059
【図５】
2015135382.tif 000060
【図６】
2015135382.tif 000061
【図７】
2015135382.tif 000062
【図８】
2015135382.tif 000063
【図９】
2015135382.tif 000064
【図１０】
2015135382.tif 000065
【図１１】
2015135382.tif 000066