(57)【要約】【課題】線型秘密分散から五十嵐方式にシェアを変換することができるシェア変換システムを提供する。【解決手段】ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、ｎ台の装置のうち任意のｎ−ｋ＋１台の装置の集合の中に必ず１台以上含まれるｍ台のシェア変換分散装置と、ｎ−ｍ台のシェア変換装置からなるシェア変換システムであって、シェア変換分散装置およびシェア変換装置は、線形秘密分散の平文のシェアを入力とし、五十嵐型の平文のシェアを出力する。【選択図】図２
2015135381.tif 000002
【特許請求の範囲】
【請求項１】
ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、ｎ台の装置のうち任意のｎ−ｋ＋１台の装置の集合の中に必ず１台以上含まれるｍ台のシェア変換分散装置と、ｎ−ｍ台のシェア変換装置からなるシェア変換システムであって、
前記シェア変換分散装置は、
線形秘密分散の平文のシェアを入力とし、
不正な装置の候補である不正装置候補のインデクスｔ個を不正装置候補集合とし、当該不正装置候補集合がｎＣｔ個含まれる集合から、自装置のインデクスを含まないように選択された不正装置候補集合それぞれについて、シード空間から初期シードを選択する初期シード選択部と、
前記初期シードを、当該初期シードに対応する不正装置候補集合に含まれない装置に送信する初期シード送信部と、
自装置のインデクスを含まないように選択された不正装置候補集合それぞれについて、不正装置候補集合に含まれない装置が生成した初期シードを足し合わせて変換用シードを生成する変換用シード生成部と、
疑似乱数生成器を用いて、前記変換用シードを疑似乱数に変換する疑似乱数生成部と、
前記疑似乱数に、線形秘密分散のシェアを生成するアルゴリズムを実行して、線形秘密分散の疑似乱数のシェアを生成する線形秘密分散疑似乱数シェア生成部と、
前記線形秘密分散の疑似乱数のシェアを他の装置に送信する第１線形秘密分散疑似乱数シェア送信部と、
全ての前記不正装置候補集合について、前記線形秘密分散の疑似乱数のシェアを不正装置候補集合に含まれない装置であって、対応する装置に送信する第２線形秘密分散疑似乱数シェア送信部と、
前記線形秘密分散の疑似乱数のシェアのコンシステンシーを検証し、受信した前記線形秘密分散の疑似乱数のシェアを復元し、前記検証が失敗であった場合、または前記復元の結果が自身が生成した対応する疑似乱数と等しくなかった場合にリジェクトシンボルを出力して処理を停止し、それ以外の場合にサクセスシンボルを他の装置に送信するコンシステンシー復元結果検証部と、
前記サクセスシンボルをｎ−１個受信した場合に、前記線形秘密分散の平文のシェアから前記線形秘密分散の疑似乱数のシェアを差し引いて、乱数でマスクされた平文の線形秘密分散のシェアを生成する被マスク平文線形シェア生成部と、
前記乱数でマスクされた平文の線形秘密分散のシェアを復元するプロトコルを実行して乱数でマスクされた平文を取得する被マスク平文線形シェア復元部と、
前記乱数でマスクされた平文に情報伝播アルゴリズムを実行して、前記乱数でマスクされた平文のｎ個の分割値を取得する被マスク平文分割部と、
自装置を含まない不正装置候補集合に対応する前記変換用シードと、自装置に対応する前記分割値とからなる組を五十嵐型の平文のシェアとして生成して出力する五十嵐型平文シェア生成部とを含み、
前記シェア変換装置は、
線形秘密分散の平文のシェアを入力とし、
前記初期シード選択部と、前記初期シード送信部と、前記変換用シード生成部と、前記疑似乱数生成部と、前記第２線形秘密分散疑似乱数シェア送信部と、前記コンシステンシー復元結果検証部と、前記被マスク平文線形シェア生成部と、前記被マスク平文線形シェア復元部と、前記被マスク平文分割部と、前記五十嵐型平文シェア生成部とを含む
シェア変換システム。
【請求項２】
ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、ｎ台の装置のうち任意のｎ−ｋ＋１台の装置の集合の中に必ず１台以上含まれるｍ台のシェア変換分散装置と、ｎ−ｍ台のシェア変換装置が実行するシェア変換方法であって、
前記シェア変換分散装置は、
線形秘密分散の平文のシェアを入力とし、
不正な装置の候補である不正装置候補のインデクスｔ個を不正装置候補集合とし、当該不正装置候補集合がｎＣｔ個含まれる集合から、自装置のインデクスを含まないように選択された不正装置候補集合それぞれについて、シード空間から初期シードを選択する初期シード選択ステップと、
前記初期シードを、当該初期シードに対応する不正装置候補集合に含まれない装置に送信する初期シード送信ステップと、
自装置のインデクスを含まないように選択された不正装置候補集合それぞれについて、不正装置候補集合に含まれない装置が生成した初期シードを足し合わせて変換用シードを生成する変換用シード生成ステップと、
疑似乱数生成器を用いて、前記変換用シードを疑似乱数に変換する疑似乱数生成ステップと、
前記疑似乱数に、線形秘密分散のシェアを生成するアルゴリズムを実行して、線形秘密分散の疑似乱数のシェアを生成する線形秘密分散疑似乱数シェア生成ステップと、
前記線形秘密分散の疑似乱数のシェアを他の装置に送信する第１線形秘密分散疑似乱数シェア送信ステップと、
全ての前記不正装置候補集合について、前記線形秘密分散の疑似乱数のシェアを不正装置候補集合に含まれない装置であって、対応する装置に送信する第２線形秘密分散疑似乱数シェア送信ステップと、
前記線形秘密分散の疑似乱数のシェアのコンシステンシーを検証し、受信した前記線形秘密分散の疑似乱数のシェアを復元し、前記検証が失敗であった場合、または前記復元の結果が自身が生成した対応する疑似乱数と等しくなかった場合にリジェクトシンボルを出力して処理を停止し、それ以外の場合にサクセスシンボルを他の装置に送信するコンシステンシー復元結果検証ステップと、
前記サクセスシンボルをｎ−１個受信した場合に、前記線形秘密分散の平文のシェアから前記線形秘密分散の疑似乱数のシェアを差し引いて、乱数でマスクされた平文の線形秘密分散のシェアを生成する被マスク平文線形シェア生成ステップと、
前記乱数でマスクされた平文の線形秘密分散のシェアを復元するプロトコルを実行して乱数でマスクされた平文を取得する被マスク平文線形シェア復元ステップと、
前記乱数でマスクされた平文に情報伝播アルゴリズムを実行して、前記乱数でマスクされた平文のｎ個の分割値を取得する被マスク平文分割ステップと、
自装置を含まない不正装置候補集合に対応する前記変換用シードと、自装置に対応する前記分割値とからなる組を五十嵐型の平文のシェアとして生成して出力する五十嵐型平文シェア生成ステップとを実行し、
前記シェア変換装置は、
線形秘密分散の平文のシェアを入力とし、
前記初期シード選択ステップと、前記初期シード送信ステップと、前記変換用シード生成ステップと、前記疑似乱数生成ステップと、前記第２線形秘密分散疑似乱数シェア送信ステップと、前記コンシステンシー復元結果検証ステップと、前記被マスク平文線形シェア生成ステップと、前記被マスク平文線形シェア復元ステップと、前記被マスク平文分割ステップと、前記五十嵐型平文シェア生成ステップとを実行する
シェア変換方法。
【請求項３】
コンピュータを、請求項１に記載のシェア変換システムに含まれるシェア変換分散装置として機能させるためのプログラム。
【請求項４】
コンピュータを、請求項１に記載のシェア変換システムに含まれるシェア変換装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は安全に分散したデータの形式を、元の情報を復元することなく変換する技術に関する。
【背景技術】
【０００２】
非特許文献１では、ある特定の計算量的安全な秘密分散方式（これを五十嵐方式と呼ぶ）を線型秘密分散のシェアに変形する方法を提案している。本技術において、登場人物は秘密分散を使って分散されたデータを保持するパーティPi(0≦i≦n-1)である。データaは秘密分散を用いてn個のシェアと呼ばれる断片([a]0,…,[a]n-1)に分割され、パーティPiがそれぞれ[a]iを持っている。秘密分散には多くの実現方法があり、本発明では非特許文献１で提案された計算量型（五十嵐方式）と線型秘密分散と呼ばれるものを扱う（定義は非特許文献２を参照）。これら2つの秘密分散方式は、互いに異なる特徴を持つ。五十嵐方式は分散する総データ量が小さく、線型秘密分散は秘密計算と呼ばれる応用が可能である。そのため、相互に変換できれば、その時々の状況によってどちらを使うか選択できる。この変換を実現するため、非特許文献３では、五十嵐方式から線型秘密分散への変換方法が開示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】五十嵐大、菊池亮、濱田浩気、千田浩司「マルチパーティ計算可能な秘密分散におけるデータ改ざん検知方法」、2013年暗号と情報セキュリティシンポジウム、プログラム3C3、暗号プロトコル(2)、平成25年1月
【非特許文献２】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.
【非特許文献３】五十嵐大、千田浩司、濱田浩気、菊池亮、「非常に高効率な n≧2k-1 maliciousモデル上秘密分散ベースマルチパーティ計算の構成法」、2013年暗号と情報セキュリティシンポジウム、プログラム3C3、暗号プロトコル(2)、平成25年1月
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献３には、五十嵐方式から線型秘密分散への変換方法のみが開示されており、線型秘密分散から五十嵐方式への変換は示されていない。そこで本発明では、線型秘密分散から五十嵐方式にシェアを変換することができるシェア変換システムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明のシェア変換システムは、ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、ｎ台の装置のうち任意のｎ−ｋ＋１台の装置の集合の中に必ず１台以上含まれるｍ台のシェア変換分散装置と、ｎ−ｍ台のシェア変換装置からなる。
【０００６】
シェア変換分散装置は、線形秘密分散の平文のシェアを入力とする。シェア変換分散装置は、初期シード選択部と、初期シード送信部と、変換用シード生成部と、疑似乱数生成部と、線形秘密分散疑似乱数シェア生成部と、第１線形秘密分散疑似乱数シェア送信部と、第２線形秘密分散疑似乱数シェア送信部と、コンシステンシー復元結果検証部と、被マスク平文線形シェア生成部と、被マスク平文線形シェア復元部と、被マスク平文分割部と、五十嵐型平文シェア生成部とを含む。
【０００７】
初期シード選択部は、不正な装置の候補である不正装置候補のインデクスｔ個を不正装置候補集合とし、当該不正装置候補集合がｎＣｔ個含まれる集合から、自装置のインデクスを含まないように選択された不正装置候補集合それぞれについて、シード空間から初期シードを選択する。初期シード送信部は、初期シードを、当該初期シードに対応する不正装置候補集合に含まれない装置に送信する。変換用シード生成部は、自装置のインデクスを含まないように選択された不正装置候補集合それぞれについて、不正装置候補集合に含まれない装置が生成した初期シードを足し合わせて変換用シードを生成する。疑似乱数生成部は、疑似乱数生成器を用いて、変換用シードを疑似乱数に変換する。線形秘密分散疑似乱数シェア生成部は、疑似乱数に、線形秘密分散のシェアを生成するアルゴリズムを実行して、線形秘密分散の疑似乱数のシェアを生成する。第１線形秘密分散疑似乱数シェア送信部は、線形秘密分散の疑似乱数のシェアを他の装置に送信する。第２線形秘密分散疑似乱数シェア送信部は、全ての不正装置候補集合について、線形秘密分散の疑似乱数のシェアを不正装置候補集合に含まれない装置であって、対応する装置に送信する。コンシステンシー復元結果検証部は、線形秘密分散の疑似乱数のシェアのコンシステンシーを検証し、受信した線形秘密分散の疑似乱数のシェアを復元し、検証が失敗であった場合、または復元の結果が自身が生成した対応する疑似乱数と等しくなかった場合にリジェクトシンボルを出力して処理を停止し、それ以外の場合にサクセスシンボルを他の装置に送信する。被マスク平文線形シェア生成部は、サクセスシンボルをｎ−１個受信した場合に、線形秘密分散の平文のシェアから線形秘密分散の疑似乱数のシェアを差し引いて、乱数でマスクされた平文の線形秘密分散のシェアを生成する。被マスク平文線形シェア復元部は、乱数でマスクされた平文の線形秘密分散のシェアを復元するプロトコルを実行して乱数でマスクされた平文を取得する。被マスク平文分割部は、乱数でマスクされた平文に情報伝播アルゴリズムを実行して、乱数でマスクされた平文のｎ個の分割値を取得する。五十嵐型平文シェア生成部は、自装置を含まない不正装置候補集合に対応する変換用シードと、自装置に対応する分割値とからなる組を五十嵐型の平文のシェアとして生成して出力する。シェア変換装置は、線形秘密分散の平文のシェアを入力とする。
【０００８】
シェア変換装置は、初期シード選択部と、初期シード送信部と、変換用シード生成部と、疑似乱数生成部と、第２線形秘密分散疑似乱数シェア送信部と、コンシステンシー復元結果検証部と、被マスク平文線形シェア生成部と、被マスク平文線形シェア復元部と、被マスク平文分割部と、五十嵐型平文シェア生成部とを含む。
【発明の効果】
【０００９】
本発明のシェア変換システムによれば、線型秘密分散から五十嵐方式にシェアを変換することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施例１のシェア変換システムの概要を示すブロック図。
【図２】本発明の実施例１のシェア変換分散装置の構成を示すブロック図。
【図３】本発明の実施例１のシェア変換分散装置の動作を示すフローチャート。
【図４】本発明の実施例１のシェア変換装置の構成を示すブロック図。
【図５】本発明の実施例１のシェア変換装置の動作を示すフローチャート。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１２】
≪アルゴリズム、プロトコル≫
以下、本発明で用いられるアルゴリズム、プロトコルについて説明する。本明細書では、通信手順を含まない一連の動作をアルゴリズム、通信手順を含む一連の動作をプロトコルと呼ぶ。秘密分散のパラメータとしてデータがn個のシェアに分割され、任意のk個のシェアを集めることで復元が可能であり、t台までのパーティの結託に対し安全であるとする。kを復元しきい値、tを安全しきい値とも呼ぶ。この3変数の間にはt<k≦nが成り立つ。特に本発明で扱う秘密分散は全てk=t+1であるため、以後kは適宜省略する。
五十嵐方式(t,n)-Comp2は以下の2つのアルゴリズムの組である。ただし、φは疑似乱数生成器、
【００１３】
【数１】
2015135381.tif 000003
【００１４】
は疑似乱数生成器のシードの空間、
【００１５】
【数２】
2015135381.tif 000004
【００１６】
を任意の群、IDA=(IDA.Split,IDA.Recは(t,n)-IDA（詳細は参考非特許文献１参照）、
【００１７】
【数３】
2015135381.tif 000005
【００１８】
は{0,…,n}からt個取り出した組み合わせである。なお、
【００１９】
【数４】
2015135381.tif 000006
【００２０】
である。
（参考非特許文献１：Michael O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, Vol. 36, No. 2, pp. 335-348, 1989.）
【００２１】
＜Comp2.Shareアルゴリズム＞
平文
【００２２】
【数５】
2015135381.tif 000007
【００２３】
を入力とし、疑似乱数生成器のシードの空間から初期シード
【００２４】
【数６】
2015135381.tif 000008
【００２５】
を選び、
【００２６】
【数７】
2015135381.tif 000009
【００２７】
について疑似乱数ti=φ(si)を計算し、乱数でマスクされた平文
【００２８】
【数８】
2015135381.tif 000010
【００２９】
とし、乱数でマスクされた平文の分割値
【００３０】
【数９】
2015135381.tif 000011
【００３１】
を計算し（ただしIDA.Splitは情報伝播アルゴリズム）、0≦i≦n-1について、五十嵐型の平文のシェア
【００３２】
【数１０】
2015135381.tif 000012
【００３３】
として[a]Compを出力する。
【００３４】
＜Comp2.Recアルゴリズム＞
Comp2.Recアルゴリズムでは、任意のt個の五十嵐型の平文のシェアである
【００３５】
【数１１】
2015135381.tif 000013
【００３６】
を入力とし、
【００３７】
【数１２】
2015135381.tif 000014
【００３８】
について、
【００３９】
【数１３】
2015135381.tif 000015
【００４０】
であるような、
【００４１】
【数１４】
2015135381.tif 000016
【００４２】
を選び、疑似乱数tj=φ(sj)を計算し、乱数でマスクされた平文の分割値から乱数でマスクされた平文
【００４３】
【数１５】
2015135381.tif 000017
【００４４】
を計算し（ただしIDA.Recは分割値復元アルゴリズム）、平文
【００４５】
【数１６】
2015135381.tif 000018
【００４６】
を出力する。(t,n)-Comp2はt人の結託に対して計算量的安全である。
【００４７】
線型秘密分散は2つのアルゴリズム(Lin.Share,Lin.Rec)の組であり、復元が線形式で記述可能な秘密分散のことである。特に本明細書では閾値を持つような線形秘密分散であり、(t,n)-Linearとかく。線型秘密分散であれば、任意のデータa、任意の
【００４８】
【数１７】
2015135381.tif 000019
【００４９】
であるようなパーティのインデクス集合
【００５０】
【数１８】
2015135381.tif 000020
【００５１】
について、線形秘密分散の復元係数と任意のデータaの線形秘密分散のシェアの線形結合がaと等しくなる、つまり
【００５２】
【数１９】
2015135381.tif 000021
【００５３】
であるような公知の線形秘密分散の復元係数
【００５４】
【数２０】
2015135381.tif 000022
【００５５】
が存在する。特に区別するとき、(t,n)-Comp2および(t,n)-Linearのシェアをそれぞれ[a]Comp2,[a]Linと書く。
【００５６】
＜SeedRandアルゴリズム＞
SeedRandアルゴリズムとは、入力(s0,…,sk)のうち一つでもランダムな要素があれば、出力もランダムになるようなものである。例えば、siがビット列である場合は、
【００５７】
【数２１】
2015135381.tif 000023
【００５８】
を排他的論理和とし、
【００５９】
【数２２】
2015135381.tif 000024
【００６０】
で良いし、siが0からn-1までの整数の集合である
【００６１】
【数２３】
2015135381.tif 000025
【００６２】
の値であったら、Σisi mod nで良い。ただしmod nとはnで割った際の剰余をあらわす。
【００６３】
＜CheckConsistencyアルゴリズム＞
本発明で用いられるCheckConsistencyアルゴリズムとはコンシステンシー（consistency）と呼ばれる「n個のシェアのうちどのk個のシェアを用いても同じ値が復元される」性質が満たされているかチェックするものであり、例えばn個のシェアのうち全てのk個のシェアの組に対して復元を行い、同じ値が復元されるかどうかチェックするという方法がある。また、(t,n)-Linearであれば後述するalgorithm2でもCheckConsistencyが可能である。
【００６４】
＜RevealProtocol、Revealプロトコル＞
RevealProtocolは復元できるプロトコルであればよく、単純には全員に全員のシェアを渡し、各人がCheckConsistencyを行ったあと復元するという方法で実現できる。
【実施例１】
【００６５】
以下、図１を参照して実施例１のシェア変換システムの概要について説明する。図１は本実施例のシェア変換システム１の概要を示すブロック図である。図１に示すように、本実施例のシェア変換システム１は、ｎを装置の台数とし、ｋを復元しきい値とし、ｔを安全しきい値とし、ｎ台の装置のうち任意のｎ−ｋ＋１台の装置の集合の中に必ず１台以上含まれるｍ台のシェア変換分散装置１３−１，１３−２，…，１３−ｍと、ｎ−ｍ台のシェア変換装置１４−１，１４−２，…，１４−（ｎ−ｍ）からなる。ｍ台のシェア変換分散装置１３−１，１３−２，…，１３−ｍと、ｎ−ｍ台のシェア変換装置１４−１，１４−２，…，１４−（ｎ−ｍ）は、ＮＷ９を介して通信可能に接続されている。ｍ台のシェア変換分散装置１３−１，１３−２，…，１３−ｍは全て同じ機能を備えるため、これらの代表として、シェア変換検証装置１３について述べる。同様に、ｎ−ｍ台のシェア変換装置１４−１，１４−２，…，１４−（ｎ−ｍ）は全て同じ機能を備えるため、これらの代表として、シェア変換装置１４について述べる。
【００６６】
以下、図２、図３を参照してシェア変換分散装置について説明する。図２は、本実施例のシェア変換分散装置１３の構成を示すブロック図である。図３は、本実施例のシェア変換分散装置１３の動作を示すフローチャートである。
【００６７】
シェア変換分散装置１３は、線形秘密分散の平文のシェアを入力とする。図２に示すように、シェア変換分散装置１３は、初期シード選択部１３１と、初期シード送信部１３２と、変換用シード生成部１３３と、疑似乱数生成部１３４と、線形秘密分散疑似乱数シェア生成部１３５と、第１線形秘密分散疑似乱数シェア送信部１３６と、第２線形秘密分散疑似乱数シェア送信部１３７と、コンシステンシー復元結果検証部１３８と、被マスク平文線形シェア生成部１３９と、被マスク平文線形シェア復元部１３Ａと、被マスク平文分割部１３Ｂと、五十嵐型平文シェア生成部１３Ｃとを含む。なお、シェア変換分散装置１３が実行する一連の通信手順（プロトコル）をprotocol1と呼ぶ。
【００６８】
初期シード選択部１３１は、不正な装置の候補である不正装置候補のインデクスｔ個を不正装置候補集合
【００６９】
【数２４】
2015135381.tif 000026
【００７０】
とし、当該不正装置候補集合がｎＣｔ個含まれる集合
【００７１】
【数２５】
2015135381.tif 000027
【００７２】
から、自装置のインデクスを含まないように選択された不正装置候補集合それぞれについて、シード空間から初期シードを選択する（Ｓ１３１）。自装置のインデクスを含まないように選択された不正装置候補集合は、
【００７３】
【数２６】
2015135381.tif 000028
【００７４】
と表せるため、ステップＳ１３１は以下のように表される。
【００７５】
【数２７】
2015135381.tif 000029
【００７６】
なお、
【００７７】
【数２８】
2015135381.tif 000030
【００７８】
は、シード空間
【００７９】
【数２９】
2015135381.tif 000031
【００８０】
は、初期シードである。s.t.はsuch thatの略である。初期シード送信部１３２は、初期シードを、当該初期シードに対応する不正装置候補集合に含まれない装置に送信する（Ｓ１３２）。lを不正装置候補集合に含まれない装置のインデクスとし、i番目のインデクスに該当する装置をPiと表すこととすると、ステップＳ１３２は以下のように表される。
【００８１】
【数３０】
2015135381.tif 000032
【００８２】
変換用シード生成部１３３は、自装置のインデクスを含まないように選択された不正装置候補集合それぞれについて、不正装置候補集合に含まれない装置が生成した初期シードを足し合わせて（SeedRandアルゴリズム）変換用シードを生成する（Ｓ１３３）。つまり、ステップＳ１３３は、
【００８３】
【数３１】
2015135381.tif 000033
【００８４】
と表される。疑似乱数生成部１３４は、疑似乱数生成器を用いて、変換用シードを疑似乱数に変換する（Ｓ１３４）。つまり、
【００８５】
【数３２】
2015135381.tif 000034
【００８６】
である。線形秘密分散疑似乱数シェア生成部１３５は、疑似乱数に、線形秘密分散のシェアを生成するLin.Shareアルゴリズムを実行して、線形秘密分散の疑似乱数のシェアを生成する（Ｓ１３５）。つまり、
【００８７】
【数３３】
2015135381.tif 000035
【００８８】
である。第１線形秘密分散疑似乱数シェア送信部１３６は、線形秘密分散の疑似乱数のシェアを他の装置に送信する（Ｓ１３６）。インデクスl=0,1,…,n-1（他の全ての装置）とし、ステップＳ１３６は、
【００８９】
【数３４】
2015135381.tif 000036
【００９０】
と表される。第２線形秘密分散疑似乱数シェア送信部１３７は、全ての不正装置候補集合について、線形秘密分散の疑似乱数のシェアを不正装置候補集合に含まれない装置であって、対応する装置に送信する（Ｓ１３７）。つまり、ステップＳ１３７は、
【００９１】
【数３５】
2015135381.tif 000037
【００９２】
と表すことができる。コンシステンシー復元結果検証部１３８は、線形秘密分散の疑似乱数のシェアのコンシステンシーを検証し（CheckConsistencyアルゴリズム、例えば後述するalgorithm2）、受信した線形秘密分散の疑似乱数のシェアを復元し（Lin.Recアルゴリズム）、検証が失敗であった場合(if false=CheckConsistency([tj]Lin))、または復元の結果が自身が生成した対応する疑似乱数と等しくなかった場合(tj≠lin.Rec([tj]Lin))にリジェクトシンボル（┴）を出力して処理を停止し、それ以外の場合にサクセスシンボル(success)を他の装置に送信する（Ｓ１３８）。すなわち、ステップＳ１３８は、
【００９３】
【数３６】
2015135381.tif 000038
【００９４】
と表される。被マスク平文線形シェア生成部１３９は、サクセスシンボルをｎ−１個受信した場合に（サクセスシンボルをｎ−１個受信するまで処理を一時停止し）、線形秘密分散の平文のシェアから線形秘密分散の疑似乱数のシェアを差し引いて、乱数でマスクされた平文の線形秘密分散のシェアを生成する（Ｓ１３９）。すなわち、ステップＳ１３９は、
【００９５】
【数３７】
2015135381.tif 000039
【００９６】
と表すことができる。なお、
【００９７】
【数３８】
2015135381.tif 000040
【００９８】
は、乱数でマスクされた平文の線形秘密分散のシェアである。被マスク平文線形シェア復元部１３Ａは、乱数でマスクされた平文の線形秘密分散のシェアを復元するプロトコル(RevealProtocol)を実行して乱数でマスクされた平文を取得する（Ｓ１３Ａ）。すなわち、ステップＳ１３Ａは、
【００９９】
【数３９】
2015135381.tif 000041
【０１００】
と表される。被マスク平文分割部１３Ｂは、乱数でマスクされた平文に情報伝播アルゴリズム(IDA.Split)を実行して、乱数でマスクされた平文のｎ個の分割値
【０１０１】
【数４０】
2015135381.tif 000042
【０１０２】
を取得する（Ｓ１３Ｂ）。五十嵐型平文シェア生成部１３Ｃは、自装置を含まない不正装置候補集合に対応する変換用シード
【０１０３】
【数４１】
2015135381.tif 000043
【０１０４】
と、自装置に対応する分割値
【０１０５】
【数４２】
2015135381.tif 000044
【０１０６】
とからなる組を五十嵐型の平文のシェアとして生成して出力する（Ｓ１３Ｃ）。すなわち、ステップＳ１３Ｃは、
【０１０７】
【数４３】
2015135381.tif 000045
【０１０８】
と表される。シェア変換分散装置１３は、五十嵐型の平文のシェア
【０１０９】
【数４４】
2015135381.tif 000046
【０１１０】
を出力する。
【０１１１】
＜algorithm2:CheckConsistency for (t,n)-Linear＞
以下、線形秘密分散のシェアのコンシステンシーを検証するalgorithm2について説明する。algorithm2は、前述のステップＳ１３８において、コンシステンシー復元結果検証部１３８が実行するアルゴリズムである。このアルゴリズムでは、任意のｎ個の線形秘密分散の平文のシェア
【０１１２】
【数４５】
2015135381.tif 000047
【０１１３】
を入力とし、true信号、またはfalse信号を出力する。具体的には、パラメータ用のインデクスの集合が
【０１１４】
【数４６】
2015135381.tif 000048
【０１１５】
かつ
【０１１６】
【数４７】
2015135381.tif 000049
【０１１７】
であるものとし、
Vに含まれるインデクスｌを選び，
検証用インデクスの集合を
【０１１８】
【数４８】
2015135381.tif 000050
【０１１９】
とし、インデクスの集合Vに含まれない各iについて、
【０１２０】
【数４９】
2015135381.tif 000051
【０１２１】
である場合には、false信号を出力し、そうでなければtrue信号を出力する。
【０１２２】
以下、図４、図５を参照してシェア変換装置について説明する。図４は、本実施例のシェア変換装置１４の構成を示すブロック図である。図５は、本実施例のシェア変換装置１４の動作を示すフローチャートである。
【０１２３】
シェア変換装置１４は、線形秘密分散の平文のシェアを入力とする。シェア変換装置１４は、初期シード選択部１３１と、初期シード送信部１３２と、変換用シード生成部１３３と、疑似乱数生成部１３４と、第２線形秘密分散疑似乱数シェア送信部１３７と、コンシステンシー復元結果検証部１３８と、被マスク平文線形シェア生成部１３９と、被マスク平文線形シェア復元部１３Ａと、被マスク平文分割部１３Ｂと、五十嵐型平文シェア生成部１３Ｃとを含む。シェア変換装置１４が備える各構成要件は、シェア変換分散装置１３において同一番号を付した各構成要件と同じ動作をするため、これらの説明は略する。
【０１２４】
本実施例のシェア変換システム１によれば、線型秘密分散から五十嵐方式にシェアを変換することができる。これにより、従来技術の五十嵐方式から線型秘密分散への変換方法と組み合わせることで、互いに利点・欠点がある2つの秘密分散を相互に変換することが可能となり、場合によって使い分けることができるようになる。例えば、秘密計算において、分散時は総データ量が小さい五十嵐型を用いストレージコストを抑えておきながら、秘密計算を行う際にのみ秘密計算に拡張可能な線型秘密分散に変更することや、秘密計算に用いたデータをバックアップする際に、総データ量の大きい線型秘密分散から、総データ量の小さい五十嵐型秘密分散に変換することができる。すなわち、秘密計算への拡張性を持たせつつ保持するデータ量を削減することが可能となる。本発明のポイントは、攻撃者がｋ−１人（台）しかいないため、ｋ人（台）の攻撃者が同じ動作を実行して、正しく結果が一致していることを確認することで、攻撃者が不正をしたときにチェックできるように構成した点にある。
【０１２５】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１２６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１２７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１３０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2015135381.tif 000052
【図２】
2015135381.tif 000053
【図３】
2015135381.tif 000054
【図４】
2015135381.tif 000055
【図５】
2015135381.tif 000056