(57)【特許請求の範囲】
【請求項１】
n,kを2以上の整数とし、n>kとし、N=nCkとし、ρをn台のランダム置換装置から選択したk台のランダム置換装置の組とし、ρ0,…,ρN-1はi=0,…,N-2について|ρi＼ρi+1|=1となるように構成されており、≪a≫ρiをi番目のランダム置換装置の組ρiが保持する平文aの加法的秘密分散値とし、≪a≫ρipを加法的秘密分散値≪a≫ρiのうちランダム置換装置pが保持する加法的秘密分散値とし、πρiをi番目のランダム置換装置の組ρiに対応する置換データπのサブシェアとし、ランダム置換装置p0をi番目のランダム置換装置の組ρiに含まれi+1番目のランダム置換装置の組ρi+1に含まれないランダム置換装置とし、ランダム置換装置pkをi番目のランダム置換装置の組ρiに含まれずi+1番目のランダム置換装置の組ρi+1に含まれるランダム置換装置とし、ランダム置換装置pj（j=1,…,k-1）をi番目のランダム置換装置の組ρi及びi+1番目のランダム置換装置の組ρi+1のいずれにも含まれるk-1台のランダム置換装置とし、
上記ランダム置換装置p0,…,pk-1が、上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換する単位置換ステップと、
上記ランダム置換装置p0が、上記ランダム置換装置pjそれぞれと共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1pkを生成して上記ランダム置換装置pkへ送信し、上記ランダム置換装置pjそれぞれが上記乱数rjを用いて加法的秘密分散値≪a≫ρi+1pjを生成する再分散ステップと、
を含む秘密計算方法。
【請求項２】
請求項１に記載の秘密計算方法であって、
上記再分散ステップは、上記ランダム置換装置p0が次式により上記加法的秘密分散値≪a≫ρi+1pkを生成し、
【数８】
0006009698.tif 000009
上記ランダム置換装置pjそれぞれが次式により上記加法的秘密分散値≪a≫ρi+1pjを生成する
【数９】
0006009698.tif 000010
秘密計算方法。
【請求項３】
請求項２に記載の秘密計算方法であって、
ρ0,…,ρN-1は、0番目のランダム置換装置の組ρ0に含まれるk台のランダム置換装置からN-1番目のランダム置換装置の組ρN-1に含まれるk台のランダム置換装置への経路の通信段数が、最大値と最小値の差が最も小さくなるように構成されている
秘密計算方法。
【請求項４】
請求項１から３のいずれかに記載の秘密計算方法であって、
上記平文aの(k,n)-秘密分散による秘密分散値[a]を上記加法的秘密分散値≪a≫ρ0に変換する事前変換ステップと、
上記加法的秘密分散値≪a≫ρN-1を上記秘密分散値[a]に変換して出力する事後変換ステップと、
をさらに含む秘密計算方法。
【請求項５】
請求項１から３のいずれかに記載の秘密計算方法であって、
N=n-1Ckとし、ρをn台のランダム置換装置から所定のランダム置換装置qを除いて選択したk台のランダム置換装置の組とし、
上記平文aを上記加法的秘密分散値≪a≫ρ0に変換する事前変換ステップと、
上記加法的秘密分散値≪a≫ρN-1を(k,n)-秘密分散による秘密分散値[a]に変換して出力する事後変換ステップと、
をさらに含み、
上記単位置換ステップは、
i≦nCk-n-1Ckであれば、上記ランダム置換装置qが、上記平文aを上記サブシェアπρiにより置換し、
i>nCk-n-1Ckであれば、上記ランダム置換装置p1,…,pk-1が、上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換する
秘密計算方法。
【請求項６】
請求項１から３のいずれかに記載の秘密計算方法であって、
N=n-1Ckとし、ρをn台のランダム置換装置から所定のランダム置換装置qを除いて選択したk台のランダム置換装置の組とし、
上記平文aの(k,n)-秘密分散による秘密分散値[a]を上記加法的秘密分散値≪a≫ρ0に変換する事前変換ステップと、
上記加法的秘密分散値≪a≫ρN-1を復元して上記平文aを出力する事後変換ステップと、
をさらに含み、
上記単位置換ステップは、
i≦n-1Ckであれば、上記ランダム置換装置p1,…,pk-1が、上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換し、
i>n-1Ckであれば、上記ランダム置換装置qが、上記平文aを上記サブシェアπρiにより置換する
秘密計算方法。
【請求項７】
請求項１から６のいずれかに記載の秘密計算方法であって、
上記単位置換ステップにより置換された上記加法的秘密分散値≪a≫ρiを(k,n)-秘密分散による秘密分散値[a]に変換して記憶部に蓄積する単位変換ステップ
をさらに含む秘密計算方法。
【請求項８】
nを2以上の整数とし、n台のランダム置換装置を含む秘密計算システムであって、
kを2以上の整数とし、n>kとし、N=nCkとし、ρをn台のランダム置換装置から選択したk台のランダム置換装置の組とし、ρ0,…,ρN-1はi=0,…,N-2について|ρi＼ρi+1|=1となるように構成されており、≪a≫ρiをi番目のランダム置換装置の組ρiが保持する平文aの加法的秘密分散値とし、≪a≫ρipを加法的秘密分散値≪a≫ρiのうちランダム置換装置pが保持する加法的秘密分散値とし、πρiをi番目のランダム置換装置の組ρiに対応する置換データπのサブシェアとし、ランダム置換装置p0をi番目のランダム置換装置の組ρiに含まれi+1番目のランダム置換装置の組ρi+1に含まれないランダム置換装置とし、ランダム置換装置pkをi番目のランダム置換装置の組ρiに含まれずi+1番目のランダム置換装置の組ρi+1に含まれるランダム置換装置とし、ランダム置換装置pj（j=1,…,k-1）をi番目のランダム置換装置の組ρi及びi+1番目のランダム置換装置の組ρi+1のいずれにも含まれるk-1台のランダム置換装置とし、
上記ランダム置換装置は、
上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換する単位置換部と、
当該ランダム置換装置が上記ランダム置換装置p0であれば、上記ランダム置換装置pjそれぞれと共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1pkを生成して上記ランダム置換装置pkへ送信し、当該ランダム置換装置が上記ランダム置換装置pjのいずれかであれば、上記乱数rjを用いて加法的秘密分散値≪a≫ρi+1pjを生成する再分散部と、
を含む秘密計算システム。
【請求項９】
n,kを2以上の整数とし、n>kとし、N=nCkとし、ρをn台のランダム置換装置から選択したk台のランダム置換装置の組とし、ρ0,…,ρN-1はi=0,…,N-2について|ρi＼ρi+1|=1となるように構成されており、≪a≫ρiをi番目のランダム置換装置の組ρiが保持する平文aの加法的秘密分散値とし、≪a≫ρipを加法的秘密分散値≪a≫ρiのうちランダム置換装置pが保持する加法的秘密分散値とし、πρiをi番目のランダム置換装置の組ρiに対応する置換データπのサブシェアとし、ランダム置換装置p0をi番目のランダム置換装置の組ρiに含まれi+1番目のランダム置換装置の組ρi+1に含まれないランダム置換装置とし、ランダム置換装置pkをi番目のランダム置換装置の組ρiに含まれずi+1番目のランダム置換装置の組ρi+1に含まれるランダム置換装置とし、ランダム置換装置pj（j=1,…,k-1）をi番目のランダム置換装置の組ρi及びi+1番目のランダム置換装置の組ρi+1のいずれにも含まれるk-1台のランダム置換装置とし、
上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換する単位置換部と、
当該ランダム置換装置が上記ランダム置換装置p0であれば、上記ランダム置換装置pjそれぞれと共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1pkを生成して上記ランダム置換装置pkへ送信し、当該ランダム置換装置が上記ランダム置換装置pjのいずれかであれば、上記乱数rjを用いて加法的秘密分散値≪a≫ρi+1pjを生成する再分散部と、
を含むランダム置換装置。
【請求項１０】
請求項９に記載のランダム置換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密計算技術に関し、特に、秘密ランダム置換を行う技術に関する。
【背景技術】
【０００２】
秘密計算とは、秘密分散によりデータを秘匿しつつデータ処理を行う技術である。秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。秘密分散はいくつかの種類に分類でき、例えば、(k,n)-秘密分散、加法的秘密分散、置換データ秘密分散などがある。【０００３】
(k,n)-秘密分散とは、入力された平文をn個のシェアに分割し、n個のパーティP=(p0,…,pn-1)に分散しておき、任意のk個のシェアが揃えば平文を復元でき、k個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。(k,n)-秘密分散の具体的な方式には、例えば、Shamir秘密分散、複製秘密分散などがある。【０００４】
加法的秘密分散とは、複製秘密分散による(k,k)-秘密分散である。(k,k)-秘密分散とは、(k,n)-秘密分散において、n=kとした場合である。(k,k)-秘密分散では、全パーティのシェアが集まらない限り平文を復元することはできない。加法的秘密分散は、k個のシェアを加算するだけで平文が復元される最もシンプルな秘密分散である。【０００５】
置換データ秘密分散は、置換データを秘匿して行う秘密分散である。置換データとは、データ列を並び替えるときの並び替え方を表すデータである。m個のデータ列を並び替えるとき、大きさmの置換データπは全単射写像π:Nm→Nmを表すデータである。ただし、任意の整数mに対して、Nmはm未満の非負整数の集合である。例えば、ベクトルx→∈(Nm)mで各要素が互いに異なるデータは大きさmのランダム置換データと見なせる。【０００６】
より具体的には、ベクトルx→=(3,0,2,1)を大きさ4のランダム置換データと見なすことができる。例えば、データ列y→=(1,5,7,10)をベクトルx→によって並び替えるとする。データ列y→の0番目の要素である1を、ベクトルx→の0番目の要素が示す3番目に移動する。データ列y→の1番目の要素である5を、ベクトルx→の1番目の要素が示す0番目に移動する。同様に、7を2番目に移動し、10を1番目に移動する。結果として、置換後のデータ列z→=(5,10,7,1)が得られる。【０００７】
置換データ秘密分散は、以下の手順により置換データを秘匿する。N個のkパーティ組の列Ρ=ρ0,…,ρN-1があるとする。例えば、k=2のとき、各kパーティ組ρiは、パーティp0とパーティp1の組(p0,p1)や、パーティp0とパーティp2の組(p0,p2)などである。各kパーティ組ρi内の全パーティが互いに置換データπρiを共有し、補集合ρ￣iには知らさないものとする。そして、対応する平文をπ0(π1(…(πN-1(I))…))とする。ただし、Iは入力と同じ並びでそのまま出力する置換、つまり恒等置換である。このとき、kパーティ組の列Ρ=ρ0,…,ρN-1を、「（条件１）任意のk-1パーティ組ρに対して、いずれかの補集合ρ￣iがρ⊆ρ￣iを満たす」ように設定すれば、どのようにk-1パーティが結託しても、いずれかの置換データπρiを知らないことになる。【０００８】
例えば、パーティ数nがn≧2k-1を満たすとき、kパーティ組の列Ρをすべてのkパーティ組を含む集合とすれば上記の条件１を満たす。また、パーティ数nがn>2k-1を満たすときは、すべてのkパーティ組を含まなくても上記の条件１が実現されることがある。例えば、k=2, n=4のとき、{(p0,p1),(p2,p3)}はすべてのkパーティ組を含みはしないが条件１を満たす。【０００９】
秘密ランダム置換とは、どのような順番に置換したのかを処理実行者にもわからないように、入力されたデータ列をランダムに置換する技術である。秘密ランダム置換を行う従来技術として非特許文献１に記載の技術がある。【００１０】
非特許文献１に記載の秘密ランダム置換の基本形は、(k,n)-秘密分散値の列[a→]を入力とし、置換データ秘密分散値<π>を生成し、(k,n)-秘密分散値の列[b→]=([aπ(0)],…,[aπ(m-1)])を出力する。このとき、置換データ秘密分散値<π>の平文π、つまりデータ列をどのような順序で入れ替えたのかがいずれのパーティにもわからないことが特徴である。具体的な処理としては、置換データ秘密分散の各サブシェアπρiに対して、kパーティ集合ρiに属するパーティp∈ρiが秘密計算ではない通常の置換処理により、入力[a→]=([a0],…,[am-1])から([aπρi(0)],…,[aπρi(m-1)])を生成し、これを再分散と呼ばれる処理により秘密分散し直すことを繰り返す。【００１１】
秘密ランダム置換は入出力の型の違いから以下の三種類が考えられる。一つ目は、入力も出力も(k,n)-秘密分散値である場合である。二つ目は、入力が(k,n)-秘密分散値であり、出力は公開値の場合である。三つ目は、入力が公開値であり、出力は(k,n)-秘密分散値の場合である。入力が公開値の場合、公開値を秘密分散して秘密分散値としてから上記の基本形の処理を行う。また、出力が公開値の場合、上記の基本形の処理を行った後に公開処理を行う。公開値とは全パーティが知っている値である。公開処理とは、例えば、全パーティが自身のシェアを他の全パーティに送信し、全パーティが受信したシェアから秘密分散の復元を行うことである。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】濱田浩気、五十嵐大、千田浩司、高橋克巳、“3パーティ秘匿関数計算のランダム置換プロトコル”、コンピュータセキュリティシンポジウム2010、2010年
【発明の概要】
【発明が解決しようとする課題】
【００１３】
非特許文献１に記載の秘密ランダム置換は、(k,n)-秘密分散値を用いて置換と再分散の処理を繰り返す。(k,n)-秘密分散値を再分散するためには、各パーティが全パーティと相互に通信を行わなければならず、通信量及び通信段数が大きいという問題がある。【００１４】
この発明の目的は、秘密ランダム置換に要する通信量及び通信段数を低減し、秘密ランダム置換が含まれる秘密計算を高速に行うことである。
【課題を解決するための手段】
【００１５】
上記の課題を解決するために、この発明の秘密計算方法は、n,kを2以上の整数とし、n>kとし、N=nCkとし、ρをn台のランダム置換装置から選択したk台のランダム置換装置の組とし、ρ0,…,ρN-1はi=0,…,N-2について|ρi＼ρi+1|=1となるように構成されており、≪a≫ρiをi番目のランダム置換装置の組ρiが保持する平文aの加法的秘密分散値とし、≪a≫ρipを加法的秘密分散値≪a≫ρiのうちランダム置換装置pが保持する加法的秘密分散値とし、πρiをi番目のランダム置換装置の組ρiに対応する置換データπのサブシェアとし、ランダム置換装置p0をi番目のランダム置換装置の組ρiに含まれi+1番目のランダム置換装置の組ρi+1に含まれないランダム置換装置とし、ランダム置換装置pkをi番目のランダム置換装置の組ρiに含まれずi+1番目のランダム置換装置の組ρi+1に含まれるランダム置換装置とし、ランダム置換装置pj（j=1,…,k-1）をi番目のランダム置換装置の組ρi及びi+1番目のランダム置換装置の組ρi+1のいずれにも含まれるk-1台のランダム置換装置として、ランダム置換装置p0,…,pk-1が、加法的秘密分散値≪a≫ρiをサブシェアπρiにより置換する単位置換ステップと、ランダム置換装置p0が、ランダム置換装置p1,…,pk-1と共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1pkを生成してランダム置換装置pkへ送信し、ランダム置換装置pjそれぞれが乱数rjを用いて加法的秘密分散値≪a≫ρi+1pjを生成する再分散ステップと、を含む。
【発明の効果】
【００１６】
この発明の秘密計算技術によれば、秘密ランダム置換を行う際の通信量及び通信段数を低減することができる。したがって、秘密ランダム置換が含まれる秘密計算を高速に実行できる。
【図面の簡単な説明】
【００１７】
【図１】図１は、秘密計算システムの機能構成を例示する図である。
【図２】図２は、第一実施形態のランダム置換装置の機能構成を例示する図である。
【図３】図３は、第一実施形態の秘密計算方法の処理フローを例示する図である。
【図４】図４は、第二実施形態の秘密計算方法の処理フローを例示する図である。
【図５】図５は、第三実施形態の秘密計算方法の処理フローを例示する図である。
【図６】図６は、第四実施形態のランダム置換装置の機能構成を例示する図である。
【図７】図７は、第四実施形態の秘密計算方法の処理フローを例示する図である。
【図８】図８は、第一実施形態におけるk=2,n=3の具体例を示す図である。
【図９】図９は、第一実施形態におけるk=3,n=5の具体例を示す図である。
【図１０】図１０は、第二実施形態におけるk=2,n=3の具体例を示す図である。
【図１１】図１１は、第二実施形態におけるk=3,n=5の具体例を示す図である。
【図１２】図１２は、第三実施形態におけるk=2,n=3の具体例を示す図である。
【図１３】図１３は、第三実施形態におけるk=3,n=5の具体例を示す図である。
【発明を実施するための形態】
【００１８】
実施形態の説明に先立ち、この明細書で用いる表記方法及び用語を定義する。
［表記方法］
pは、シェアを所持するパーティを表す。
P=(p0,…,pn-1)は、シェアを所持するnパーティ全体の集合を表す。
ρ=(p0,…,pk-1)は、置換処理を実行するkパーティ組の集合を表す。
Ρ=(ρ0,…,ρN-1)は、各置換処理を実行するkパーティ組の順番を表す。ただし、N=nCkは、置換処理の実行回数であり、nパーティからkパーティを選択するすべての組み合わせの数である。
[x]は、平文x∈Gの(k,n)-秘密分散値を表す。ここで、Gは可換群である。(k,n)-秘密分散値とは、平文xを(k,n)-秘密分散で分散したシェアすべてを集めた組である。秘密分散値[x]は、普段はnパーティ集合Pに分散されて所持されているため、一か所ですべてを所持されることはなく、仮想的である。
[x]pは、(k,n)-秘密分散値[x]のうち、パーティp∈Pが所持するシェアを表す。
[x→]は、平文の列がx→となる(k,n)-秘密分散値の列を表す。
[G]は、可換群G上の(k,n)-秘密分散値全体の集合を表す。
≪x≫ρは、平文x∈Gの加法的秘密分散値で、kパーティ組ρがシェアを所持するものを表す。加法的秘密分散値とは、平文xを加法的秘密分散で分散したシェアすべてを集めた組を表す。
≪x≫ρpは、加法的秘密分散値≪x≫ρのうち、パーティp∈ρが所持するシェアを表す。
≪x→≫ρは、平文の列がx→となる加法的秘密分散値の列を表す。
≪G≫ρは、可換群G上の加法的秘密分散値全体の集合を表す。
<π>は、置換データπの置換データ秘密分散値を表す。
Πは、大きさmの置換データ全体の集合を表す。
<Π>は、大きさmの置換データ秘密分散値全体の集合を表す。
【００１９】
［発明のポイント］
この発明の秘密ランダム置換の概要は以下の通りである。
ステップ１．入力を(k,n)-秘密分散値または公開値から加法的秘密分散値に変換する。
ステップ２．加法的秘密分散値上で、シェアを持つkパーティ集合ρに属する各パーティが置換データ秘密分散値<π>のサブシェアπρによる通常の置換を行い、再分散することを繰り返す。ただし、最終回は再分散しない。以下、反復の一回を単位置換と呼び、繰り返す処理全体を反復置換と呼ぶ。
ステップ３．出力を加法的秘密分散値から(k,n)-秘密分散値または公開値に変換する。
【００２０】
ステップ１及びステップ３は、既存の手法を適用できる。以下では、ステップ２の処理におけるポイントについて説明する。
【００２１】
＜単位置換＞
単位置換におけるポイントは、i回目の単位置換で、|ρi＼ρi+1|=1となるようにkパーティ集合ρiを選択することである。つまり、i回目の単位置換を行うkパーティ集合ρiと、i+1回目の単位置換を行うkパーティ集合ρi+1とでは、1パーティだけが異なり残りのk-1パーティは同じパーティということである。このような単位置換を、パーティが一つしか異ならない場合であることから、1-加法的再分散プロトコルと呼ぶ。
【００２２】
非特許文献１に記載の秘密ランダム置換における再分散では、(n-1)(k-1)個のG要素の通信量を要する。一方、1-加法的再分散プロトコルでは、k-1個のG要素の通信量で済む。特に、シードを予め共有して疑似乱数を共有すれば、通信量は1個のG要素の通信量で済む。この場合は、通信量が定数となり、非常に効率的である。
【００２３】
1-加法的再分散プロトコルは、入力をkパーティ組ρ=p0,…,pk-1が所持する秘密分散値≪a≫ρ∈≪G≫ρとし、以下の手順でデータ処理を行い、他のkパーティ組ρ’=p1,…,pkが所持する秘密分散値≪a≫ρ’∈≪G≫ρ’を出力する。ただし、パーティの役割は適切に変更されるものとする。
【００２４】
まず、パーティp0は、i=1,…,k-1について、パーティpiと乱数ri∈Gを共有する。次に、パーティp0は、次式により秘密分散値≪a≫ρ'pkを計算して、パーティpkに送信する。パーティpkは、受信した≪a≫ρ'pkを出力する。
【数１】
0006009698.tif 000002
【００２５】
続いて、パーティpi（i=1,…,k-1）は、次式により秘密分散値≪a≫ρ'piを計算して出力する。
【数２】
0006009698.tif 000003
【００２６】
＜反復置換の中の単位置換の並列化＞
反復置換は、置換→再分散→置換→再分散→…→置換という繰り返しであり、置換をN回、再分散をN-1回実行する。これを単純に行うと、通信の段数はそのまま再分散の回数であり、N-1段となる。しかし、1-加法的再分散プロトコルによる単位置換は、通信に関して並列化することができる。データ受信を待つパーティが1パーティ、すなわち前回の単位置換に参加していないパーティだけだからであり、他のパーティは何らのデータ受信を待つことなく、オフライン処理だけを実行して次の単位置換処理に移行できるからである。加法的秘密分散のシェアはk個であるから、kパーティ組の順番Ρを適切に設定すれば、最大k回の単位置換を1段で実行することができる。これにより、通信段数を(N-1)/k段に低減することができる。
【００２７】
kパーティ組の順番Ρは、任意のi<kについて、パーティpiからの経路の通信段数が互いに等しいか、最大値と最小値の差が最も小さい順番にすることで、通信段数を効率化することができる。
【００２８】
パーティpiからの経路とは、長さLのkパーティ組の列Ρ=(ρ0,…,ρL-1)に対して、パーティの列(pj0,pj1,…,pjL-1)であって、次式により帰納的に定められる列である。
【数３】
0006009698.tif 000004
【００２９】
経路の通信段数とは、経路の中でパーティが変化することで通信が必要となるλの数、すなわち|{λ∈NL|pjλ≠pjλ+1}|である。1-加法的再分散プロトコルの通信では、パーティpkがパーティp0からの送信を待つ以外は乱数の通信であり、前段の再分散の結果に依存していない。経路の通信段数は、このパーティp0からパーティpkの通信のうち直列に並んでおり並列に実行できない段数を表している。反復置換全体の通信段数は、次式に示すとおりであるため、各経路の通信段数が均等になっていると効率的である。
【数４】
0006009698.tif 000005
【００３０】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
［第一実施形態］
図１を参照して、第一実施形態に係る秘密計算システムの構成例を説明する。秘密計算システムは、n（≧2）台のランダム置換装置１1,…,１nとネットワーク９を含む。ランダム置換装置１1,…,１nはネットワーク９にそれぞれ接続される。ネットワーク９はランダム置換装置１1,…,１nそれぞれが相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、ランダム置換装置１1,…,１nそれぞれは必ずしもネットワーク９を介してオンラインで通信可能である必要はない。例えば、あるランダム置換装置１i（1≦i≦n）が出力する情報をＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から異なるランダム置換装置１j（1≦j≦n、i≠j）へオフラインで入力するように構成してもよい。
【００３１】
図２を参照して、秘密計算システムに含まれるランダム置換装置１の構成例を説明する。ランダム置換装置１は、事前変換部１０、単位置換部１２、再分散部１４、事後変換部１６及び記憶部１８を含む。ランダム置換装置１は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。ランダム置換装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。ランダム置換装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。ランダム置換装置１が備える記憶部１８は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００３２】
パーティpに対応するランダム置換装置１pが備える記憶部１８には、平文aの(k,n)-秘密分散値[a]pもしくは公開値a、パーティpが含まれるkパーティの組ρに対応する置換データπのサブシェアπρ及びN×k個のシードs0,1,…,sN-1,kが記憶されている。なお、シードs0,1,…,sN-1,kは、後述する再分散部１４の処理において乱数を生成する際に通信無しで行うために予め記憶しておくものであるが、都度協調して乱数生成を行う場合には記憶していなくても構わない。
【００３３】
図３を参照しながら、第一実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００３４】
ステップＳ１０において、k台のランダム置換装置１ρ0が備える事前変換部１０は、記憶部１８に記憶されている(k,n)-秘密分散値[a]piもしくは公開値aを加法的秘密分散値≪a≫ρ0へ変換する。ρ0はkパーティ組の列Ρ=(ρ0,…,ρN-1)の0番目の要素であり、ランダム置換装置１ρ0は、ρ0=(p0,…,pk-1)に対応するk台のランダム置換装置１p0,…,１pk-1である。
【００３５】
(k,n)-秘密分散値もしくは公開値から加法的秘密分散値へ変換する方法は、既知の方法により行えばよい。
【００３６】
入力が公開値である場合、加法的秘密分散値への変換は、例えば以下のように行うことができる。ρをk台のランダム置換装置１p0,…,１pk-1の組とし、a∈Gを入力された公開値とし、ランダム置換装置１p0が公開値aを知っているとする。公開値aから加法的秘密分散値≪a≫ρへの変換は、i=0,…,k-1について、次式により行えばよい。
【数５】
0006009698.tif 000006
【００３７】
入力が(k,n)-秘密分散値である場合、加法的秘密分散値への変換は、例えば下記の参考文献１及び参考文献２に記載された方法により行うことができる。参考文献１には、Shamir秘密分散を含む線形秘密分散から加法的秘密分散へ通信無しで変換する方法が記述されている。参考文献２には、複製秘密分散から線形秘密分散へ通信無しで変換する方法が記述されているため、複製秘密分散から加法的秘密分散への変換は、参考文献２に記載の方法と参考文献１に記載の方法を組み合わせることで通信無しで実現される。
〔参考文献１〕五十嵐大、濱田浩気、菊池亮、千田浩司、“少パーティの秘密分散ベース秘密計算のためのO(l)ビット通信ビット分解およびO(|p'|)ビット通信Modulus変換法”、コンピュータセキュリティシンポジウム2013、2013年
〔参考文献２〕R. Cramer, I. Damgard, and Y. Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation”, TCC 2005, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362, 2005.
【００３８】
ステップＳ１ａにおいて、k台のランダム置換装置１ρ0は、置換処理の実行回数を表すカウンタiを0に初期化する。
【００３９】
ステップＳ１２において、k台のランダム置換装置１ρiが備える単位置換部１２は、記憶部１８に記憶されている置換データのサブシェアπρiを用いて加法的秘密分散値≪a≫ρiを置換する。ρiはkパーティ組の列Ρ=(ρ0,…,ρN-1)のi番目の要素であり、ランダム置換装置１ρiは、ρi=(p0,…,pk-1)に対応するk台のランダム置換装置１p0,…,１pk-1である。置換の方法は、従来の置換データ秘密分散の方法により行えばよい。
【００４０】
ステップＳ１ｂにおいて、k台のランダム置換装置１ρiは、所定回数の置換処理が実行されたか否かを判定する。具体的には、N=nCkを単位置換の総実行回数として、カウンタiの値がN-1に達したか否かを判定する。i<N-1であれば、ステップＳ１４へ処理を進める。i≧N-1であれば、ステップＳ１６へ処理を進める。
【００４１】
ステップＳ１４において、k台のランダム置換装置１ρi+1が備える再分散部１４は、1-加法的再分散プロトコルにより加法的秘密分散値≪a≫ρiの再分散を行う。以下、ランダム置換装置１p0を、ランダム置換装置１ρiに含まれてランダム置換装置１ρi+1には含まれないランダム置換装置とし、ランダム置換装置１pkを、ランダム置換装置１ρiに含まれずランダム置換装置１ρi+1に含まれるランダム置換装置とする。また、ランダム置換装置１pj（j=1,…,k-1）を、ランダム置換装置１pkを除くランダム置換装置１ρi+1に含まれるk-1台のランダム置換装置を表すものとする。
【００４２】
まず、ランダム置換装置１ρi+1が備える再分散部１４は、k個の乱数r1,…,rk∈Gを生成する。乱数r1,…,rkは、k台のランダム置換装置１ρi+1が協調して共有の乱数r1,…,rkを生成してもよいし、記憶部１８に記憶されているシードsi,1,…,si,kを用いて疑似乱数r1,…,rkを生成してもよい。予め共有したシードsi,1,…,si,kを用いて疑似乱数を生成すればランダム置換装置間の通信無く乱数生成ができるので非常に効率的である。
【００４３】
次に、ランダム置換装置１p0が備える再分散部１４は、ランダム置換装置１pkのための加法的秘密分散値≪a≫ρi+1pkを、加法的秘密分散値≪a≫ρip0及び乱数r0,…,rk-1を用いて次式により生成し、ランダム置換装置１pkへ送信する。
【数６】
0006009698.tif 000007
【００４４】
そして、ランダム置換装置１pjが備える再分散部１４は、加法的秘密分散値≪a≫ρipj及び乱数rjを用いて、加法的秘密分散値≪a≫ρi+1pjを、次式により生成する。
【数７】
0006009698.tif 000008
【００４５】
ステップＳ１ｃにおいて、k台のランダム置換装置１ρi+1は、置換処理の実行回数を表すカウンタiへ1を加算する。以降、ステップＳ１ｂにおいてカウンタiがN-1に達したと判定されるまで、ステップＳ１２の単位置換とステップＳ１４の再分散を繰り返す。
【００４６】
ステップＳ１６において、k台のランダム置換装置１ρN-1が備える事後変換部１６は、加法的秘密分散値を(k,n)-秘密分散値もしくは公開値へ変換する。加法的秘密分散値から他の形式へ変換する方法は、比較的軽量に行うことができる。なお、下記の変換方法は一例であり、他の変換方法では適用できないということを意味するものではない。
【００４７】
出力が公開値である場合、出力を得たいランダム置換装置１p（1≦p≦n）に対して、最後に置換処理を実行したk台のランダム置換装置１ρN-1が加法的秘密分散値≪a≫ρN-1pj（j=0,…,k-1）を送信し、ランダム置換装置１pが復元を行う方法がある。その他に、出力を得たい複数台のランダム置換装置１ρ（ρ⊆{1,…,n}）から選択した一台のランダム置換装置１p（p∈ρ）に対して、最後に置換処理を実行したk台のランダム置換装置１ρN-1が加法的秘密分散値≪a≫ρN-1pj(j=0,…,k-1）を送信し、ランダム置換装置１pが復元を行い、他のランダム置換装置１ρへ復元結果を送信する方法もある。
【００４８】
出力が(k,n)-秘密分散値である場合、線形秘密分散、複製秘密分散など加法準同型性を持つ、つまり秘密分散値上で通信無しで加法を行える秘密分散に対しては、例えば、以下の手順により変換することができる。まず、k台のランダム置換装置１ρN-1は変換先の(k,n)-秘密分散によって加法的秘密分散値≪a≫ρN-1pjを秘密分散し、n台のランダム置換装置１Pへ(k,n)-秘密分散値[≪a≫ρN-1pj]p（p=1,…,n）を配信する。そして、n台のランダム置換装置１Pは受信したk個の(k,n)-秘密分散値[≪a≫ρN-1pj]pをすべて加算する。
【００４９】
このように、第一実施形態の秘密計算システムは、入力を加法的秘密分散値に変換することで、再分散の処理における通信量を低減させることができ、従来のランダム置換よりも効率的に処理を行うことが可能である。
【００５０】
［第二実施形態］
秘密ランダム置換の入力が公開値である場合には第一実施形態よりもさらに効率化することができる。非特許文献１や第一実施形態の方法でランダム置換の置換データを秘密にするためには、任意のk-1パーティ組ρに対して、いずれかの補集合ρ￣iがρ⊆ρ￣iを満たすようなkパーティ組の列Ρの要素数だけ、単位置換を行う必要がある。しかし、あるパーティpがもつ公開値が入力の場合、もっと少ない回数の単位置換でよい。入力が公開値であるため、最初はパーティpが1パーティで置換を行うことができ、パーティpが知っている分の置換をすべてまとめて行うことができるからである。
【００５１】
少なくとも1台のランダム置換装置１p0が備える記憶部１８には、公開値aが記憶されている。公開値aは少なくとも1台が所持していればよく、何台のランダム置換装置が所持していても構わない。
【００５２】
ランダム置換装置１p0を除くn-1台のランダム置換装置１p1,…,１pn-1が備える記憶部１８には、パーティpiが含まれるkパーティの組ρiに対応する置換データπのサブシェアπρi及びN×k個のシードs0,1,…,sN-1,kが記憶されているものとする。ただし、Nはn-1Ckである。第一実施形態と同様に、シードs0,1,…,sN-1,kは必ずしも記憶していなくても構わない。
【００５３】
図４を参照しながら、第二実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００５４】
ステップＳ１２p0において、ランダム置換装置１p0が備える単位置換部１２は、ランダムな置換データπを生成し、置換データπにより公開値aを置換する。置換の方法は、従来の置換方法と同様である。
【００５５】
ステップＳ１０p0において、ランダム置換装置１p0が備える事前変換部１０は、置換後の公開値aを加法的秘密分散値≪a≫ρ-1へ変換する。変換の方法は、第一実施形態のステップＳ１０と同様である。加法的秘密分散値≪a≫ρ-1は、ランダム置換装置１ρ0のうち、任意に選択したk-1台に配信される。ここでは、ランダム置換装置１p1,…,１pk-1に配信されたものとする。
【００５６】
ステップＳ１４p0において、k台のランダム置換装置１ρ0が備える再分散部１４は、1-加法的再分散プロトコルにより加法的秘密分散値≪a≫ρ-1の再分散を行う。再分散の方法は、第一実施形態のステップＳ１４と同様である。
【００５７】
以降、ランダム置換装置１p0を除くn-1台のランダム置換装置１p1,…,１pn-1により、ステップＳ１ａからＳ１６までの処理を実行する。
【００５８】
このように、第二実施形態の秘密計算システムでは、1台のランダム置換装置によりまとめて置換を行った後にn-1台のランダム置換装置によりランダム置換を行うため、置換処理の回数がn-1Ck+1となり、第一実施形態の秘密計算システムよりも効率的に処理を行うことが可能である。
【００５９】
［第三実施形態］
秘密ランダム置換の入力が公開値の場合と同様に、秘密ランダム置換の出力が公開値の場合にも、第一実施形態よりもさらに効率化ができる。出力が公開値であるため、n-1パーティがランダム置換を行った後に、残りの1パーティに秘密分散値を送信し、復元した公開値に対してまとめて置換を行うことができるからである。
【００６０】
ランダム置換装置１p0を除くn-1台のランダム置換装置１p1,…,１pn-1が備える記憶部１８には、パーティpiが含まれるkパーティの組ρiに対応する置換データπのサブシェアπρi及びN×k個のシードs0,1,…,sN-1,kが記憶されているものとする。ただし、Nはn-1Ckである。第一実施形態と同様に、シードs0,1,…,sN-1,kは必ずしも記憶していなくても構わない。
【００６１】
図５を参照しながら、第三実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００６２】
ステップＳ１０からＳ１ｂにおいてi≧N-1と判定されるまでの処理を、ランダム置換装置１p0を除くn-1台のランダム置換装置１p1,…,１pn-1により実行する。
【００６３】
ステップＳ１６p0において、ランダム置換装置１p0が備える事後変換部１６は、加法的秘密分散値を公開値へ変換する。変換の方法は第一実施形態のステップＳ１６と同様である。具体的には、ランダム置換装置１p0に対して、最後に置換処理を実行したk台のランダム置換装置１ρN-1が加法的秘密分散値≪a≫ρN-1pj（j=0,…,k-1）を送信し、ランダム置換装置１p0が備える事後変換部１６が加法的秘密分散値≪a≫ρN-1を復元する。
【００６４】
ステップＳ１２p0において、ランダム置換装置１p0が備える単位置換部１２は、ランダムな置換データπを生成し、復元された公開値を置換する。置換の方法は、従来の置換方法と同様である。
【００６５】
このように、第三実施形態の秘密計算システムでは、n-1台のランダム置換装置によりランダム置換を行った後に1台のランダム置換装置によりまとめて置換を行うため、置換処理の回数がn-1Ck+1となり、第一実施形態の秘密計算システムよりも効率的に処理を行うことが可能である。
【００６６】
［第四実施形態］
第四実施形態は、この発明の秘密ランダム置換に対して秘密計算中の改ざんを検知することを可能とする実施形態である。秘密計算中の改ざんを検知する秘密改ざん検知方法として、下記参考文献３に記載の方法が提案されている。参考文献３では、３つのフェーズで秘密計算中の改ざん検知を行う。ランダム化フェーズでは、分散値を正当性検証可能なランダム化分散値へと変換する。計算フェーズでは、semi-honestの演算により構成されるランダム化分散値用の演算を用いて所望の秘密計算を実行する。このとき、後続の正当性証明フェーズでチェックサムを計算するために必要となるランダム化分散値を収集しながら計算が行われる。正当性証明フェーズでは、計算フェーズで収集されたランダム化分散値に対して、一括でチェックサムを計算し正当性証明を行う。チェックサムが正当であれば計算フェーズによる計算結果を出力し、正当でなければ計算結果は出力せずに正当でない旨のみを出力する。
〔参考文献３〕五十嵐大、千田浩司、濱田浩気、菊池亮、“非常に高効率なn≧2k-1 malicious モデル上秘密分散ベースマルチパーティ計算の構成法”、SCIS2013、2013年
しかしながら、参考文献３に記載の方法を適用するためには、秘密計算で実行する各演算がtamper-simulatableである必要がある（参考文献４）。
〔参考文献４〕D. Ikarashi, R. Kikuchi, K. Hamada, and K. Chida, “Actively Private and Correct MPC Scheme in t<n/2 from Passively Secure Schemes with Small Overhead”, IACR Cryptology ePrint Archive, vol. 2014, p. 304, 2014
【００６７】
そこで、第四実施形態では、参考文献３に記載の秘密改ざん検知方法を上記の条件を満たすように第一実施形態の秘密ランダム置換に適用した構成例を示す。なお、以下では第一実施形態に適用した例を示すが、同様の考え方により、第二実施形態及び第三実施形態に適用することも可能である。
【００６８】
図６を参照して、第四実施形態に係るランダム置換装置２の構成例を説明する。ランダム置換装置２は、上述の実施形態に係るランダム置換装置１と同様に、事前変換部１０、単位置換部１２、再分散部１４、事後変換部１６及び記憶部１８を含み、ランダム化部２０、単位変換部２２及び正当性証明部２４をさらに含む。
【００６９】
図７を参照しながら、第四実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００７０】
ステップＳ２０において、k台のランダム置換装置１ρ0が備えるランダム化部２０は、記憶されている(k,n)-秘密分散値[a]piをランダム化分散値へ変換する。記憶部１８に公開値aが記憶されている場合には、公開値aを(k,n)-秘密分散値[a]piへ変換した上で、ランダム化分散値へ変換する。ランダム化分散値とは、値a∈Rの分散値[a]piと、値a∈Rと乱数r∈Aとの積算値arの分散値[ar]piとの組([a]pi,[ar]pi)である。ここで、Rは環であり、Aは環R上の結合多元環である。結合多元環とは、結合的な環であって、かつそれと両立するような、何らかの体上の線型空間の構造を備えたものである。結合多元環は、ベクトル空間で扱う値が体ではなく環でよくなったものと言える。ランダム化分散値の第０成分（[a]pi）はR成分、第１成分（[ar]pi）はA成分とも呼ぶ。
【００７１】
ランダム化分散値を生成する際に用いる乱数は、同一の環上の秘密分散を複数利用する場合には、一方の秘密分散のための分散値を他方の秘密分散のための分散値に変換することで、乱数の値が同一となるように生成する。この形式変換においても、改ざん検知が可能もしくは改ざんが不可能でなければならない。例えば、複製型秘密分散（replicated secret sharing）から線形秘密分散（linear secret sharing）へ変換する改ざん不可能な方法は上記参考文献２に記載されている。
【００７２】
ステップＳ２２において、k台のランダム置換装置１ρiが備える単位変換部２２は、単位置換部１２により置換された加法的秘密分散値≪a≫ρiを(k,n)-秘密分散によるランダム化分散値に変換して記憶部１８に蓄積する。蓄積したランダム化分散値は後述の正当性証明部２４においてチェックサムを計算するために利用される。ランダム化分散値の蓄積は、すべての単位置換の後に必ず行わなくともよく、一部の単位置換の際にのみ行うようにしてもよい。
【００７３】
ステップＳ２４において、正当性証明部２４は、すべての秘密分散についてすべての秘密計算が終了するまで待機する同期処理（SYNC）を実行する。すべての秘密分散についてすべての秘密計算が終了したことを検知すると、ランダム化部２０で用いた乱数r0,…,rJ-1の分散値[r0],…,[rJ-1]を用いてチェックサムC0,…,CJ-1を検証し、秘密ランダム置換の結果として得られる(k,n)-秘密分散値もしくは公開値の正当性を検証する。チェックサムC0,…,CJ-1を検証した結果、改ざんがないと判定した場合はステップＳ１６へ処理を進める。改ざんがあったと判断した場合はその旨を示す情報（例えば、「⊥」など）を出力する。
【００７４】
チェックサムの検証は、j=0,…,J-1について、チェックサムCjに含まれるランダム化分散値のR成分の総和に分散値[rj]を乗じた分散値[φj]と、チェックサムCjに含まれるランダム化分散値のA成分の総和である分散値[ψj]とを計算し、分散値[φj]と分散値[ψj]を減算した分散値[δj]=[φj]-[ψj]を復元して、値δ0,…,δJ-1がすべて0であれば秘密ランダム置換全体を通して改ざんがなかったものと判定する。いずれかの値δjが0以外であれば、秘密ランダム置換のいずれかの演算において改ざんがあったものと判定する。
【００７５】
J個の秘密分散のうち同一の環上の秘密分散が存在する場合には、可能な限りまとめて正当性証明を行うと、公開される値の数が少なくなるため、より秘匿性を向上することができる。例えば、α（α=0,…,J-1）番目の秘密分散とβ（β=0,…,J-1、α≠β）番目の秘密分散が同一の環上の秘密分散である場合には、以下のように正当性証明を行う。まず、チェックサムCαから上述のように算出した分散値[φα]と、チェックサムCαから上述のように算出した分散値[ψα]とをそれぞれβ番目の秘密分散へ変換する。そして、変換後の分散値[φα]とチェックサムCβから同様に算出した分散値[φβ]とを合算した分散値[φα+φβ]と、変換後の分散値[ψα]とβ番目のチェックサムCβから同様に算出した分散値[ψβ]とを合算した分散値[ψα+ψβ]とを減算した分散値[δ]=([φα]+[φβ])-([ψα]+[ψβ])を復元し、復元値δが0であれば改ざんがなかったものと判定し、復元値δが0以外であれば改ざんがあったものと判定する。このようにして、すべての同一の環上の秘密分散の組み合わせについて検証し、秘密ランダム置換全体で改ざんがなかったことを検証する。本形態では２個の秘密分散が同一の環上の秘密分散である例を説明したが、３個以上の秘密分散が同一の環上の秘密分散である場合でも、同様の方法により正当性証明を行うことができる。
【００７６】
ステップＳ１６において、事後変換部１６は、加法的秘密分散値を(k,n)-秘密分散値もしくは公開値へ変換する。上述の実施形態では、出力が公開値の場合には、最後の置換処理を行った後の加法的秘密分散値≪a≫ρN-1をランダム置換装置１pへ送信し、そのランダム置換装置１pが加法的秘密分散の復元方法により公開値aを得るように構成した。本形態では、公開時の改ざんを検知するために、加法的秘密分散値を(k,n)-秘密分散値に一旦変換した上で、(k,n)-秘密分散の復元方法により公開値aを得るように構成する。
【００７７】
(k,n)-秘密分散値から公開値を得る際には、改ざん検知が可能な公開方法による必要がある。改ざん検知が可能な公開方法としては、上記参考文献４のappendixに記載の方法がある。もしくは、以下のようにして公開を行うことで改ざん検知が可能である。
【００７８】
ランダム置換装置１pは、任意のk-1台のランダム置換装置から、加法的秘密分散値≪a≫ρN-1を形式変換した(k,n)-秘密分散値を受信する。また、残りのn-k台のランダム置換装置からは、加法的秘密分散値≪a≫ρN-1を形式変換した(k,n)-秘密分散値のハッシュ値などのチェックサムを受信する。チェックサムはハッシュ値でなくてもよく、より安全な情報理論的なチェックサムを用いることもできる。情報理論的なチェックサムは、例えば、チェックサムの計算対象をaiとして、乱数rとairi+1の組である。ランダム置換装置１pは、自らの持つ(k,n)-秘密分散値を加えたk個の(k,n)-秘密分散値からn-k個の(k,n)-秘密分散値を復旧し、復旧した(k,n)-秘密分散値それぞれからチェックサムを計算する。なお、復旧とは、一部の分散値が失われた際に、利用可能なk個の分散値から利用不能となったn-k個の分散値を秘匿性を失わずに再構築する方法である。
【００７９】
続いて、ランダム置換装置１pは、n-k台のランダム置換装置から受信した(k,n)-秘密分散値のチェックサムと、復旧した(k,n)-秘密分散値のチェックサムとが一致するか否かを確認する。すべてのチェックサムが一致した場合には改ざんがなかったものと判定し、(k,n)-秘密分散値もしくは公開値を出力する。いずれかのチェックサムが異なっていた場合には改ざんがあったものと判定し、その旨を示す情報（例えば、「⊥」など）を出力する。
【００８０】
本形態のように構成すれば、この発明の秘密ランダム置換において、改ざん検知が可能となり、安全性が向上する。
【００８１】
［構成例の組み合わせ］
この発明は、上述の実施形態の他にも、四つの独立した観点の組み合わせにより、様々な構成とすることが可能である。
【００８２】
一つ目の観点は、入出力の型の観点である。この観点では、四つの構成方法が考えられる。一つ目の構成は、入力が線形秘密分散値であり出力が線形秘密分散値の場合である。二つ目の構成は、入力が線形秘密分散値であり出力が複製秘密分散値の場合、もしくはその逆に入力が複製秘密分散値であり出力が線形秘密分散値の場合である。三つ目の構成は、入力が公開値であり出力が秘密分散値の場合である。四つ目の構成は、入力が線形秘密分散値であり出力が公開値の場合である。
【００８３】
二つ目の観点は、乱数生成方法の観点である。この観点では、二つの構成方法が考えられる。一つ目の構成は、乱数があらかじめ共有されたシードから生成される疑似乱数の場合である。二つ目の構成は、乱数がプロトコル実行時に共有される場合である。
【００８４】
三つ目の観点は、ランダム置換の種類の観点である。この観点では、二つの構成方法が考えられる。一つ目の構成は、置換データが任意の場合であり、完全にランダムにシャッフルしたい場合である。二つ目の構成は、置換データがローテーションに制限される場合、つまり置換データがあるr∈Nmで表現され、π(i)=i+r mod mとなっており、絶対的な位置は秘匿したいが相対的な並び順は秘匿しなくてよい場合である。
【００８５】
四つ目の観点は、k,nを限定した反復置換の具体例の観点である。一つ目の構成は、k=2, n=3の構成である。二つ目の構成は、k=3, n=5の構成である。この観点では、各構成に対して、さらに入出力の観点を加えた計六つの具体例が考えられる。
【００８６】
一つ目の具体例は、k=2, n=3の構成において、入出力とも秘密分散値の場合である。図８を参照しながら、この具体例の反復置換について説明する。図８において、縦軸はパーティを表し、横軸は単位置換の回数を表している。丸印は単位置換において処理を行うパーティを示している。実線の矢印は再分散において秘密分散値が送信されるパーティの方向を示している。点線の矢印は再分散において同一のパーティが引き続き秘密分散値を保持することを示している。図８の例では、kパーティ組の順番Ρ=(ρ0,ρ1,ρ2)は、ρ0=(p0,p1)、ρ1=(p1,p2)、ρ2=(p0,p2)と設定される。一回目の単位置換ではパーティp0,p1が処理を行い、一回目の再分散ではパーティp0からパーティp2へ秘密分散値が送信される。二回目の単位置換ではパーティp1,p2が処理を行い、二回目の再分散ではパーティp1からパーティp0へ秘密分散値が送信される。三回目の単位置換でパーティp0,p2が処理を行い、反復置換が完了する。
【００８７】
二つ目の具体例は、k=3, n=5の構成において、入出力とも秘密分散値の場合である。図９を参照しながら、この具体例の反復置換について説明する。図の記法は、図８と同様である。図９の例では、kパーティ組の順番Ρ=(ρ0,…,ρ9)は、ρ0=(p0,p1,p2)、ρ1=(p1,p2,p3)、ρ2=(p2,p3,p4)、ρ3=(p0,p3,p4)、ρ4=(p0,p1,p4)、ρ5=(p1,p3,p4)、ρ6=(p0,p1,p3)、ρ7=(p0,p2,p3)、ρ8=(p0,p2,p4)、ρ9=(p1,p2,p4)と設定される。一回目の単位置換ではパーティp0,p1,p2が処理を行い、一回目の再分散ではパーティp0からパーティp3へ秘密分散値が送信される。二回目の単位置換ではパーティp1,p2,p3が処理を行い、二回目の再分散ではパーティp1からパーティp4へ秘密分散値が送信される。三回目の単位置換ではパーティp2,p3,p4が処理を行い、三回目の再分散ではパーティp2からパーティp0へ秘密分散値が送信される。四回目の単位置換ではパーティp0,p3,p4が処理を行い、四回目の再分散ではパーティp3からパーティp1へ秘密分散値が送信される。ここで、パーティp3からパーティp1へ送信される秘密分散値は、一回目の再分散でパーティp0からパーティp3へ送信された秘密分散値であるから、五回目の再分散の前にパーティp1は受信待ちが発生する。したがって、四回目の再分散までは通信の一段目となる。以降、同様に置換と再分散を繰り返すことで、この具体例では三段の通信段数で反復置換が完了する。
【００８８】
三つ目の具体例は、k=2, n=3の構成において、入力が公開値であり出力が秘密分散値の場合である。図１０を参照しながら、この具体例の反復置換について説明する。図の記法は、図８と同様である。図１０の例では、kパーティ組の順番Ρ=(ρ0,ρ1,ρ2)は、ρ0=ρ1=(p0)、ρ2=(p1,p2)と設定される。一回目と二回目の単位置換ではパーティp0のみが処理を行う。この単位置換は単純に二回繰り返してもよいし、二回分の置換をまとめて行うこともできる。二回目の再分散ではパーティp0からパーティp1,p2へ秘密分散値が送信される。三回目の単位置換でパーティp1,p2が処理を行い、反復置換が完了する。
【００８９】
四つ目の具体例は、k=3, n=5の構成において、入力が公開値であり出力が秘密分散値の場合である。図１１を参照しながら、この具体例の反復置換について説明する。図の記法は、図８と同様である。図１１の例では、kパーティ組の順番Ρ=(ρ0,…,ρ9)は、ρ0=ρ1=ρ2=ρ3=ρ4=ρ5=(p0)、ρ6=(p2,p3,p4)、ρ7=(p1,p3,p4)、ρ8=(p1,p2,p4)、ρ9=(p1,p2,p3)と設定される。一回目から六回目の単位置換ではパーティp0のみが処理を行う。この単位置換は単純に六回繰り返してもよいし、六回分の置換をまとめて行うこともできる。六回目の再分散ではパーティp0からパーティp2,p3,p4へ秘密分散値が送信される。七回目の単位置換ではパーティp2,p3,p4が処理を行い、七回目の再分散ではパーティp2からパーティp1へ秘密分散値が送信される。八回目の単位置換ではパーティp1,p3,p4が処理を行い、八回目の再分散ではパーティp3からパーティp2へ秘密分散値が送信される。九回目の単位置換ではパーティp1,p2,p4が処理を行い、九回目の再分散ではパーティp4からパーティp3へ秘密分散値が送信される。十回目の単位置換ではパーティp1,p2,p3が処理を行い、反復置換が完了する。図９に示すとおり、この具体例では二段の通信段数で反復置換が完了する。
【００９０】
五つ目の具体例は、k=2, n=3の構成において、入力が秘密分散値であり出力が公開値の場合である。図１２を参照しながら、この具体例の反復置換について説明する。図の記法は、図８と同様である。図１２の例では、kパーティ組の順番Ρ=(ρ0,ρ1,ρ2)は、ρ0=(p1,p2)、ρ1=ρ2=(p0)と設定される。一回目の単位置換ではパーティp1,p2が処理を行い、パーティp1,p2からパーティp0へ秘密分散値が送信される。パーティp0は秘密分散値の復元を行い、二回目と三回目の単位置換を行う。この単位置換は単純に二回繰り返してもよいし、二回分の置換をまとめて行うこともできる。以上で反復置換が完了する。
【００９１】
六つ目の具体例は、k=3, n=5の構成において、入力が秘密分散値であり出力が公開値の場合である。図１３を参照しながら、この具体例の反復置換について説明する。図の記法は、図８と同様である。図１３の例では、kパーティ組の順番Ρ=(ρ0,…,ρ9)は、ρ0=(p2,p3,p4)、ρ1=(p1,p3,p4)、ρ2=(p1,p2,p4)、ρ3=(p1,p2,p3)、ρ4=ρ5=ρ6=ρ7=ρ8=ρ9=(p0)と設定される。一回目の単位置換ではパーティp2,p3,p4が処理を行い、一回目の再分散ではパーティp2からパーティp1へ秘密分散値が送信される。以降、パーティp1,p2,p3,p4により置換と再分散を繰り返し、N（=4C3=4）回目の置換が完了した後、パーティp1,p2,p3からパーティp0へ秘密分散値が送信される。パーティp0は秘密分散値の復元を行い、五回目から十回目の単位置換を行う。この単位置換は単純に六回繰り返してもよいし、六回分の置換をまとめて行うこともできる。以上で反復置換が完了する。
【００９２】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００９３】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００９４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００９７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0006009698.tif 000011
【図２】
0006009698.tif 000012
【図３】
0006009698.tif 000013
【図４】
0006009698.tif 000014
【図５】
0006009698.tif 000015
【図６】
0006009698.tif 000016
【図７】
0006009698.tif 000017
【図８】
0006009698.tif 000018
【図９】
0006009698.tif 000019
【図１０】
0006009698.tif 000020
【図１１】
0006009698.tif 000021
【図１２】
0006009698.tif 000022
【図１３】
0006009698.tif 000023