(57)【特許請求の範囲】
【請求項１】
Lビットのm個のキーk0,…,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,…,vm-1の列v→の秘密分散値[v→]の組を入力とし、バリュー列v→を整列するためのソート置換σπ-1Lを生成する秘密計算方法であって、
置換データ生成部が、i=1,…,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成ステップと、
ランダムＩＤ列生成部が、i=1,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]を生成し、互いに重複した値を含まないランダムＩＤ列[r→L]を生成するランダムＩＤ列生成ステップと、
秘密ランダム置換部が、i=1,…,L-1について、ランダムＩＤ列[r→i-1]、キー列[k→i]及びランダムＩＤ列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]及び置換後ランダムＩＤ列[πir→i]の組を生成し、ランダムＩＤ列[r→L-1]を置換データ<πL>により秘密ランダム置換して置換後ランダムＩＤ列πLr→L-1を生成する秘密ランダム置換ステップと、
フラグ作成部が、j=0,…,m-1及びh=0,…,L-1について、キー[kj]=([kj,0],…,[kj,L-1])に対して、kj=hであるか否かを判定してフラグ[fj,h]を設定するフラグ作成ステップと、
順位表作成部が、フラグ[fj,h]を用いてキーk0,…,km-1それぞれの昇順の順位が設定された順位表[s→:=(s0,…,sm-1)]を作成する順位表作成ステップと、
ソート置換生成部が、i=0,…,L-1について、ランダムＩＤ列[r→i]を置換関数σiにより置換して置換後ランダムＩＤ列[σir→i]を生成し、順位表[s→]及び置換後ランダムＩＤ列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列して整列後ランダムＩＤ列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムＩＤ列[πi+1r→i+1]の組と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムＩＤ列[σi+1r→i+1]の組を生成し、置換後ランダムＩＤ列πLr→L-1と整列後ランダムＩＤ列σLr→L-1とを等結合してソート置換σπ-1Lを生成するソート置換生成ステップと、
を含む秘密計算方法。
【請求項２】
Lビットのm個のキーk0,…,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,…,vm-1の列v→の秘密分散値[v→]の組を入力とし、バリュー列v→を整列した整列後バリュー列[σv→]Vを生成する秘密計算方法であって、
置換データ生成部が、i=1,…,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成ステップと、
ランダムＩＤ列生成部が、i=1,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]を生成し、互いに重複した値を含まないランダムＩＤ列[r→L]を生成するランダムＩＤ列生成ステップと、
秘密ランダム置換部が、i=1,…,L-1について、ランダムＩＤ列[r→i-1]、キー列[k→i]及びランダムＩＤ列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]及び置換後ランダムＩＤ列[πir→i]の組を生成し、ランダムＩＤ列[r→L-1]及びバリュー列[v→]Vの組を置換データ<πL>により秘密ランダム置換して置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vの組を生成する秘密ランダム置換ステップと、
フラグ作成部が、j=0,…,m-1及びh=0,…,L-1について、キー[kj]=([kj,0],…,[kj,L-1])に対して、kj=hであるか否かを判定してフラグ[fj,h]を設定するフラグ作成ステップと、
順位表作成部が、フラグ[fj,h]を用いてキーk0,…,km-1それぞれの昇順の順位が設定された順位表[s→:=(s0,…,sm-1)]を作成する順位表作成ステップと、
整列部が、i=0,…,L-1について、ランダムＩＤ列[r→i]を置換関数σiにより置換して置換後ランダムＩＤ列[σir→i]を生成し、順位表[s→]及び置換後ランダムＩＤ列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列して整列後ランダムＩＤ列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムＩＤ列[πi+1r→i+1]の組と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムＩＤ列[σi+1r→i+1]の組を生成し、置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vの組と、整列後ランダムＩＤ列σLr→L-1とを、置換後ランダムＩＤ列πLr→L-1をキーとして等結合して整列後バリュー列[σv→]Vを生成する整列ステップと、
を含む秘密計算方法。
【請求項３】
請求項１に記載の秘密計算方法であって、
バリュー整列部が、バリュー列[v→]を置換データ<πL>により秘密ランダム置換して置換後バリュー列[πLv→]を生成し、置換後バリュー列[πLv→]をソート置換σπ-1Lに基づいて整列して整列後バリュー列[σv→]を生成するバリュー整列ステップ
をさらに含む秘密計算方法。
【請求項４】
複数のソート装置を含み、Lビットのm個のキーk0,…,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,…,vm-1の列v→の秘密分散値[v→]の組を入力とし、バリュー列v→を整列するためのソート置換σπ-1Lを生成する秘密計算システムであって、
上記ソート装置は、
i=1,…,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成部と、
i=1,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]を生成し、互いに重複した値を含まないランダムＩＤ列[r→L]を生成するランダムＩＤ列生成部と、
i=1,…,L-1について、ランダムＩＤ列[r→i-1]、キー列[k→i]及びランダムＩＤ列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]及び置換後ランダムＩＤ列[πir→i]の組を生成し、ランダムＩＤ列[r→L-1]を置換データ<πL>により秘密ランダム置換して置換後ランダムＩＤ列πLr→L-1を生成する秘密ランダム置換部と、
j=0,…,m-1及びh=0,…,L-1について、キー[kj]=([kj,0],…,[kj,L-1])に対して、kj=hであるか否かを判定してフラグ[fj,h]を設定するフラグ作成部と、
フラグ[fj,h]を用いてキーk0,…,km-1それぞれの昇順の順位が設定された順位表[s→:=(s0,…,sm-1)]を作成する順位表作成部と、
i=0,…,L-1について、ランダムＩＤ列[r→i]を置換関数σiにより置換して置換後ランダムＩＤ列[σir→i]を生成し、順位表[s→]及び置換後ランダムＩＤ列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列して整列後ランダムＩＤ列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムＩＤ列[πi+1r→i+1]の組と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムＩＤ列[σi+1r→i+1]の組を生成し、置換後ランダムＩＤ列πLr→L-1と整列後ランダムＩＤ列σLr→L-1とを等結合してソート置換σπ-1Lを生成するソート置換生成部と、
を含む秘密計算システム。
【請求項５】
複数のソート装置を含み、Lビットのm個のキーk0,…,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,…,vm-1の列v→の秘密分散値[v→]の組を入力とし、バリュー列v→を整列した整列後バリュー列[σv→]を生成する秘密計算システムであって、
上記ソート装置は、
i=1,…,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成部と、
i=1,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]を生成し、互いに重複した値を含まないランダムＩＤ列[r→L]を生成するランダムＩＤ列生成部と、
i=1,…,L-1について、ランダムＩＤ列[r→i-1]、キー列[k→i]及びランダムＩＤ列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]及び置換後ランダムＩＤ列[πir→i]の組を生成し、ランダムＩＤ列[r→L-1]及びバリュー列[v→]Vを置換データ<πL>により秘密ランダム置換して置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vを生成する秘密ランダム置換部と、
j=0,…,m-1及びh=0,…,L-1について、キー[kj]=([kj,0],…,[kj,L-1])に対して、kj=hであるか否かを判定してフラグ[fj,h]を設定するフラグ作成部と、
フラグ[fj,h]を用いてキーk0,…,km-1それぞれの昇順の順位が設定された順位表[s→:=(s0,…,sm-1)]を作成する順位表作成部と、
i=0,…,L-1について、ランダムＩＤ列[r→i]を置換関数σiにより置換して置換後ランダムＩＤ列[σir→i]を生成し、順位表[s→]及び置換後ランダムＩＤ列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列して整列後ランダムＩＤ列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムＩＤ列[πi+1r→i+1]の組と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムＩＤ列[σi+1r→i+1]の組を生成し、置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vの組と、整列後ランダムＩＤ列σLr→L-1とを、置換後ランダムＩＤ列πLr→L-1をキーとして等結合して整列後バリュー列[σv→]Vを生成する整列部と、
を含む秘密計算システム。
【請求項６】
Lビットのm個のキーk0,…,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,…,vm-1の列v→の秘密分散値[v→]の組を入力とし、バリュー列v→を整列するためのソート置換σπ-1Lを生成するソート装置であって、
i=1,…,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成部と、
i=1,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]を生成し、互いに重複した値を含まないランダムＩＤ列[r→L]を生成するランダムＩＤ列生成部と、
i=1,…,L-1について、ランダムＩＤ列[r→i-1]、キー列[k→i]及びランダムＩＤ列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]及び置換後ランダムＩＤ列[πir→i]の組を生成し、ランダムＩＤ列[r→L-1]を置換データ<πL>により秘密ランダム置換して置換後ランダムＩＤ列πLr→L-1を生成する秘密ランダム置換部と、
j=0,…,m-1及びh=0,…,L-1について、キー[kj]=([kj,0],…,[kj,L-1])に対して、kj=hであるか否かを判定してフラグ[fj,h]を設定するフラグ作成部と、
フラグ[fj,h]を用いてキーk0,…,km-1それぞれの昇順の順位が設定された順位表[s→:=(s0,…,sm-1)]を作成する順位表作成部と、
i=0,…,L-1について、ランダムＩＤ列[r→i]を置換関数σiにより置換して置換後ランダムＩＤ列[σir→i]を生成し、順位表[s→]及び置換後ランダムＩＤ列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列して整列後ランダムＩＤ列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムＩＤ列[πi+1r→i+1]の組と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムＩＤ列[σi+1r→i+1]の組を生成し、置換後ランダムＩＤ列πLr→L-1と整列後ランダムＩＤ列σLr→L-1とを等結合してソート置換σπ-1Lを生成するソート置換生成部と、
を含むソート装置。
【請求項７】
Lビットのm個のキーk0,…,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,…,vm-1の列v→の秘密分散値[v→]の組を入力とし、バリュー列v→を整列した整列後バリュー列[σv→]Vを生成するソート装置であって、
i=1,…,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成部と、
i=1,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]を生成し、互いに重複した値を含まないランダムＩＤ列[r→L]を生成するランダムＩＤ列生成部と、
i=1,…,L-1について、ランダムＩＤ列[r→i-1]、キー列[k→i]及びランダムＩＤ列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]及び置換後ランダムＩＤ列[πir→i]の組を生成し、ランダムＩＤ列[r→L-1]及びバリュー列[v→]Vを置換データ<πL>により秘密ランダム置換して置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vを生成する秘密ランダム置換部と、
j=0,…,m-1及びh=0,…,L-1について、キー[kj]=([kj,0],…,[kj,L-1])に対して、kj=hであるか否かを判定してフラグ[fj,h]を設定するフラグ作成部と、
フラグ[fj,h]を用いてキーk0,…,km-1それぞれの昇順の順位が設定された順位表[s→:=(s0,…,sm-1)]を作成する順位表作成部と、
i=0,…,L-1について、ランダムＩＤ列[r→i]を置換関数σiにより置換して置換後ランダムＩＤ列[σir→i]を生成し、順位表[s→]及び置換後ランダムＩＤ列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列して整列後ランダムＩＤ列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムＩＤ列[πi+1r→i+1]の組と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムＩＤ列[σi+1r→i+1]の組を生成し、置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vの組と、整列後ランダムＩＤ列σLr→L-1とを、置換後ランダムＩＤ列πLr→L-1をキーとして等結合して整列後バリュー列[σv→]Vを生成する整列部と、
を含むソート装置。
【請求項８】
請求項６または７に記載のソート装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密計算技術に関し、特に、秘密ソートを行う技術に関する。
【背景技術】
【０００２】
秘密計算とは、秘密分散によりデータを秘匿しつつデータ処理を行う技術である。秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。秘密分散はいくつかの種類に分類でき、例えば、(k,n)-秘密分散、置換データ秘密分散などがある。【０００３】
(k,n)-秘密分散とは、入力された平文をn個のシェアに分割し、n個のパーティP=(p0,…,pn-1)に分散しておき、任意のk個のシェアが揃えば平文を復元でき、k個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。(k,n)-秘密分散の具体的な方式には、例えば、Shamir秘密分散、複製秘密分散などがある。
【０００４】
置換データ秘密分散は、置換データを秘匿して行う秘密分散である。置換データとは、データ列を並び替えるときの並び替え方を表すデータである。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パーティ組を含みはしないが条件１を満たす。
【０００８】
秘密ソートとは、秘密分散されたキーとバリューを秘匿したままキーの順序関係に基づいて一定の規則に従ってバリューを並び替える処理である。秘密ソートを行う従来技術として非特許文献１に記載の技術がある。【０００９】
非特許文献１に記載の秘密ソートは、バリュー列v→の秘密分散値[v→]とキー列k→の秘密分散値[k→L-1],…,[k→0]を入力とし、整列されたバリュー列σv→の秘密分散値[σv→]を出力する。ここで、σはソートを表す置換関数である。まず、(1)置換関数σ0をZm上の恒等写像とする。ここで、Zmは0以上m未満の整数の集合である。(2)ランダムＩＤ列[h→]:=[I]とする。ここで、Iは恒等置換である。(3)i=0,…,L-1について、下記の(4)から(14)までの処理を実行する。(4)置換データ<π0>,<π1>,<π2>を生成する。(5)[σi-1k→i]を1ビット安定ソートして順位表[s→]を生成する。(6)([σih→],[s→])を置換データ<π0>により秘密ランダム置換して([π0σih→],[π0s→])を生成する。(7)i=Lであれば下記の(15)へ進む。(8)([h→],[k→i+1])を置換データ<π1>により秘密ランダム置換して([π1h→],[π1k→i+1])を生成する。(9)[π1h→],[π0σih→]を復元する。(10)[π0σik→i+1]:=π0σih→(π1h→)-1[π1k→i+1]を計算する。(11)([π0σih→],[π0s→],[π0σik→i+1])を置換データ<π2>により秘密ランダム置換して([π20σih→],[π20s→],[π20σik→i+1])を生成する。ただし、π20=π2π0である。(12)[π20s→]を復元する。(13)([s→-1σih→],[s→-1σik→i+1]):=(π20s→)-1([π20σih→],[π20σik→i+1])を計算する。(14)置換関数σi+1:=s→-1σiとおく。(15)[π0s→],[s→-1σih→]を復元する。(16)置換関数σL:=s→-1σL-1とおく。(17)置換データ<π3>を生成する。(18)[h→],[v→]を置換データ<π3>により置換して([π3h→],[π3v→])を生成する。(19)[π3h→],[σLh→]を復元し、[σv→]:=σLh→(π3h→)-1[π3v→]を出力する。ここで、置換関数σ=σLである。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】濱田浩気、五十嵐大、千田浩司、高橋克巳、“秘匿関数計算上の線形時間ソート”、コンピュータセキュリティシンポジウム2011、2011年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
非特許文献１に記載の秘密ソート技術は、ランダムＩＤ列の作成と秘密ランダム置換を逐次的に繰り返し実行するため通信段数が大きいという問題がある。【００１２】
この発明の目的は、秘密ソートに要する通信段数を低減し、秘密ソートが含まれる秘密計算を高速に行うことである。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、この発明の一態様の秘密計算方法は、Lビットのm個のキーk0,…,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,…,vm-1の列v→の秘密分散値[v→]の組を入力とし、バリュー列v→を整列するためのソート置換σπ-1Lを生成する秘密計算方法であって、置換データ生成部が、i=1,…,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成ステップと、ランダムＩＤ列生成部が、i=1,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]を生成し、互いに重複した値を含まないランダムＩＤ列[r→L]を生成するランダムＩＤ列生成ステップと、秘密ランダム置換部が、i=1,…,L-1について、ランダムＩＤ列[r→i-1]、キー列[k→i]及びランダムＩＤ列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]及び置換後ランダムＩＤ列[πir→i]の組を生成し、ランダムＩＤ列[r→L-1]を置換データ<πL>により秘密ランダム置換して置換後ランダムＩＤ列πLr→L-1を生成する秘密ランダム置換ステップと、フラグ作成部が、j=0,…,m-1及びh=0,…,L-1について、キー[kj]=([kj,0],…,[kj,L-1])に対して、kj=hであるか否かを判定してフラグ[fj,h]を設定するフラグ作成ステップと、順位表作成部が、フラグ[fj,h]を用いてキーk0,…,km-1それぞれの昇順の順位が設定された順位表[s→:=(s0,…,sm-1)]を作成する順位表作成ステップと、ソート置換生成部が、i=0,…,L-1について、ランダムＩＤ列[r→i]を置換関数σiにより置換して置換後ランダムＩＤ列[σir→i]を生成し、順位表[s→]及び置換後ランダムＩＤ列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列して整列後ランダムＩＤ列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムＩＤ列[πi+1r→i+1]の組と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムＩＤ列[σi+1r→i+1]の組を生成し、置換後ランダムＩＤ列πLr→L-1と整列後ランダムＩＤ列σLr→L-1とを等結合してソート置換σπ-1Lを生成するソート置換生成ステップと、を含む。【００１４】
この発明の他の態様の秘密計算方法は、Lビットのm個のキーk0,…,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,…,vm-1の列v→の秘密分散値[v→]の組を入力とし、整列後バリュー列[σv→]Vを生成する秘密計算方法であって、置換データ生成部が、i=1,…,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成ステップと、ランダムＩＤ列生成部が、i=1,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]を生成し、互いに重複した値を含まないランダムＩＤ列[r→L]を生成するランダムＩＤ列生成ステップと、秘密ランダム置換部が、i=1,…,L-1について、ランダムＩＤ列[r→i-1]、キー列[k→i]及びランダムＩＤ列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]及び置換後ランダムＩＤ列[πir→i]の組を生成し、ランダムＩＤ列[r→L-1]及びバリュー列[v→]Vを置換データ<πL>により秘密ランダム置換して置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vを生成する秘密ランダム置換ステップと、フラグ作成部が、j=0,…,m-1及びh=0,…,L-1について、キー[kj]=([kj,0],…,[kj,L-1])に対して、kj=hであるか否かを判定してフラグ[fj,h]を設定するフラグ作成ステップと、順位表作成部が、フラグ[fj,h]を用いてキーk0,…,km-1それぞれの昇順の順位が設定された順位表[s→:=(s0,…,sm-1)]を作成する順位表作成ステップと、整列部が、i=0,…,L-1について、ランダムＩＤ列[r→i]を置換関数σiにより置換して置換後ランダムＩＤ列[σir→i]を生成し、順位表[s→]及び置換後ランダムＩＤ列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列して整列後ランダムＩＤ列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムＩＤ列[πi+1r→i+1]の組と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムＩＤ列[σi+1r→i+1]の組を生成し、置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vの組と、整列後ランダムＩＤ列σLr→L-1とを、置換後ランダムＩＤ列πLr→L-1をキーとして等結合して整列後バリュー列[σv→]Vを生成する整列ステップと、を含む。
【発明の効果】
【００１５】
この発明の秘密計算技術によれば、秘密ソートを行う際の通信段数を低減することができる。したがって、秘密ソートが含まれる秘密計算を高速に実行できる。
【図面の簡単な説明】
【００１６】
【図１】図１は、秘密計算システムの機能構成を例示する図である。
【図２】図２は、第一実施形態のソート装置の機能構成を例示する図である。
【図３】図３は、第一実施形態の秘密計算方法の処理フローを例示する図である。
【図４】図４は、第二実施形態のソート装置の機能構成を例示する図である。
【図５】図５は、第二実施形態の秘密計算方法の処理フローを例示する図である。
【図６】図６は、第三実施形態のソート装置の機能構成を例示する図である。
【図７】図７は、第三実施形態の秘密計算方法の処理フローを例示する図である。
【図８】図８は、第四実施形態のソート装置の機能構成を例示する図である。
【図９】図９は、第四実施形態の秘密計算方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１７】
実施形態の説明に先立ち、この明細書で用いる表記方法及び用語を定義する。
［表記方法］
pは、シェアを所持するパーティを表す。
P=(p0,…,pn-1)は、シェアを所持するnパーティ全体の集合を表す。
ρ=(p0,…,pk-1)は、置換処理を実行するkパーティ組の集合を表す。
[x]は、平文x∈Gの(k,n)-秘密分散値を表す。ここで、Gは可換群である。(k,n)-秘密分散値は、平文xを(k,n)-秘密分散で分散したシェアすべてを集めた組である。秘密分散値[x]は、普段はnパーティ集合Pに分散されて所持されているため、一か所ですべてを所持されることはなく、仮想的である。
[x]IDは、m種類のＩＤを表現しうる空間上の秘密分散値を表す。
[x]Oは、m種類の順序集合を表現しうる空間上の秘密分散値を表す。
[x]Bは、ビットの秘密分散値を表す。
[x]Vは、ソート対象のバリューを表現しうる空間上の秘密分散値を表す。
[x]Kは、ソート順を決定するキーの一部を表現しうる空間上の秘密分散値を表し、L個の組み合わせでキー空間全体を表現する（例えば、[x]Kがビット列の秘密分散値であり、キーがLビットである場合など）。
≪x≫ρは、平文x∈Gの加法的秘密分散値を表す。加法的秘密分散値とは、平文xを加法的秘密分散で分散したシェアすべてを集めた組を表す。
≪x≫ρpは、加法的秘密分散値≪x≫ρのうち、パーティp∈ρが所持するシェアを表す。
≪x→≫ρは、平文の列がx→となる加法的秘密分散値の列を表す。
≪G≫ρは、可換群G上の加法的秘密分散値全体の集合を表す。
<π>は、置換データπの置換データ秘密分散値を表す。
【００１８】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
［第一実施形態］
図１を参照して、第一実施形態に係る秘密計算システムの構成例を説明する。秘密計算システムは、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、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。ソート装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。ソート装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２０】
図３を参照しながら、第一実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００２１】
ソート装置１は、キー列k→の秘密分散値[k→]Kとバリュー列v→の秘密分散値[v→]Vの組([k→]K,[v→]V)を入力とし、整列後バリュー列σv→の秘密分散値[σv→]Vを出力する。ここで、σはソートを表す置換関数である。キー列k→はm個のキーk0,…,km-1の列である。各キーkiのビット長はLである。すなわち、各キーki=(ki,0,…,ki,L-1)と表すことができる。キー列k→のビット毎の分散値の列を[k→0]K,…,[k→L-1]Kと表す。バリュー列v→はm個のバリューv0,…,vm-1の列である。各バリューviは少なくとも一つの値であり、複数の値の組み合わせであってもよい。キー列k→とバリュー列v→は同一であってもよい。
【００２２】
ステップＳ１０において、置換データ生成部１０は、i=0,…,L-1について、置換データ<πi>,<π’i>を並列かつ同時に生成する。続いて、置換データ<πL>を生成する。
【００２３】
ステップＳ１２において、ランダムＩＤ列生成部１２は、i=0,…,L-1について、互いに重複した値を含まないランダムＩＤ列[r→i]IDを並列かつ同時に生成する。続いて、互いに重複した値を含まないランダムＩＤ列[r→L]IDを生成する。
【００２４】
ステップＳ１４において、秘密ランダム置換部１４は、i=1,…,L-1について、ランダムＩＤ列[r→i-1]ID、キー列[k→i]K及びランダムＩＤ列[r→i]IDの組([r→i-1]ID,[k→i]K,[r→i]ID)を置換データ<πi>により並列かつ同時に秘密ランダム置換し、置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]K及び置換後ランダムＩＤ列[πir→i]IDの組(πir→i-1,[πik→i]K,[πir→i]ID)を生成する。続いて、ランダムＩＤ列[r→L-1]IDを置換データ<πL>により秘密ランダム置換し、置換後ランダムＩＤ列πLr→L-1を生成する。
【００２５】
秘密ランダム置換の方法は、任意の秘密ランダム置換を利用することができる。例えば、下記参考文献１に記載の方法を用いることができる。また、置換回路による置換も適用することができる。
〔参考文献１〕濱田浩気、五十嵐大、千田浩司、高橋克巳、“3パーティ秘匿関数計算のランダム置換プロトコル”、コンピュータセキュリティシンポジウム2010、2010年
【００２６】
さらに、秘密ランダム置換は、以下の1-加法的再分散プロトコルを用いて行うこともできる。1-加法的再分散プロトコルは、kパーティ組ρ=p0,…,pk-1が所持する秘密分散値≪a≫ρ∈≪G≫ρを入力とし、以下の手順でデータ処理を行い、他のkパーティ組ρ’=p1,…,pkが所持する秘密分散値≪a≫ρ’∈≪G≫ρ’を出力する秘密ランダム置換である。1-加法的再分散プロトコルでは、kパーティ組ρとkパーティ組ρ’とで1パーティだけが異なるため、通信量及び通信段数を低減することができ、効率的に秘密ランダム置換を行うことができる。ただし、パーティの役割は適切に変更されるものとする。
【００２７】
まず、パーティp0は、i=1,…,k-1について、パーティpiと乱数ri∈Gを共有する。次に、パーティp0は、次式により秘密分散値≪a≫ρ'pkを計算してパーティpkに送信する。
【数１】
0006009697.tif 000002
【００２８】
パーティpkは、受信した≪a≫ρ'pkを出力する。パーティpi（i=1,…,k-1）は、次式により秘密分散値≪a≫ρ'piを計算して出力する。
【数２】
0006009697.tif 000003
【００２９】
ステップＳ１６において、フラグ作成部１６は、j=0,…,m-1及びh=0,…,L-1について、キー[kj]K=([kj,0]B,…,[kj,L-1]B)に対して、kj=hであるか否かを判定して、並列かつ同時にフラグ[fj,h]を設定する。具体的には、kj=hであればフラグ[fj,h]B=[1]Bを、kj≠hであればフラグ[fj,h]B=[0]Bを設定する。フラグの設定は等号判定回路を利用すればよい。
【００３０】
続いて、フラグ作成部１６は、フラグ[fj,h]Bをフラグ[fj,h]Oに変換する。値aの秘密分散値[a]Bを秘密分散値[a]Oに変換する方法は、例えば、[a]BがZ2を部分群として持つ秘密分散（例えば、mod 2の複製秘密分散、2の拡大体上のShamir秘密分散など）のとき、以下のように行えばよい。まず、パーティpiは乱数riを生成し、二通りの秘密分散により秘密分散値[ri]B,[ri]Oを生成する。次に、秘密計算により次式を計算し、乱数rの秘密分散値[r]B,[r]Oを生成する。
【数３】
0006009697.tif 000004
【００３１】
続いて、秘密分散値[a]Bと秘密分散値[r]Bを用いて、値aと値rの排他的論理和[a'=a XOR r]Bを計算し、値a'を復元する。そして、値a'と秘密分散値[r]Oの排他的論理和[a]O=a' XOR [r]Oを計算する。つまり、a XOR r=0なら、[a]O:=[r]Oであり、a XOR r=1なら、[a]O:=1-[r]Oである。
【００３２】
ステップＳ１８において、順位表作成部１８は、フラグ[fj,h]Oを用いて、順位表[s→]Oを作成する。まず、[S]O=[0]Oを設定する。次に、j=0,…,m-1について、[sj,h]O=[Sj,h-1]O+[fj,h]O（ただし、0≦h<2Lの各整数）を設定する。続いて、j=0,…,m-1について、次式を並列かつ同時に計算し、順位表[s→:=(s0,…,sm-1)]Oを設定する。作成された順位表[s→]Oは、キー列k→=k0,…,km-1の各要素の昇順の順位が設定されたベクトルとなる。
【数４】
0006009697.tif 000005
【００３３】
ステップＳ２０において、ソート置換生成部２０は、順位表[s→]O、ランダムＩＤ列[r→i]、置換データ<π’i>、置換後キー列[πik→i]K及び置換後ランダムＩＤ列[σir→i]IDを用いて、ソート置換σπ-1Lを生成する。まず、置換関数σ0=Iを設定する。ただし、Iは恒等置換である。次に、i=0,…,L-1について、ランダムＩＤ列[r→i]IDを置換関数σiにより置換し、置換後ランダムＩＤ列[σir→i]IDを生成する。続いて、順位表[s→]O及び置換後ランダムＩＤ列[σir→i]IDを置換データ<π’i>により秘密ランダム置換し、置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成する。次に、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列し、整列後ランダムＩＤ列σi+1r→iを生成する。ここで、置換関数σi+1=s→-1σiである。さらに、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]K及び置換後ランダムＩＤ列[πi+1r→i+1]IDの組(πi+1r→i,[πi+1k→i+1]K,[πi+1r→i+1]ID)と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]K及び整列後ランダムＩＤ列[σi+1r→i+1]IDの組(σi+1r→i,[σi+1k→i+1]K,[σi+1r→i+1]ID)を生成する。続いて、置換後ランダムＩＤ列πLr→L-1と整列後ランダムＩＤ列σLr→L-1とを等結合し、ソート置換σπ-1Lを生成する。ここで、置換関数σ=σLである。
【００３４】
ステップＳ２２において、バリュー整列部２２は、バリュー列[v→]Vを置換データ<πL>により秘密ランダム置換し、置換後バリュー列[πLv→]Vを生成する。続いて、置換後バリュー列[πLv→]Vをソート置換σπ-1Lに基づいて整列し、整列後バリュー列[σv→]を生成する。
【００３５】
従来の秘密ソート技術ではランダムＩＤ列の生成と秘密ランダム置換を逐次的に行っていた。第一実施形態の秘密計算システムでは最初に必要な個数のランダムＩＤ列を生成することで、ランダムＩＤ列を用いた秘密ランダム置換を並列かつ同時に行うことが可能となっている。さらに、順位表作成に必要とするフラグも並列かつ同時に生成する。これにより、秘密ソートの通信段数を低減することができ、秘密ソートが含まれる秘密計算を高速に実行することができる。
【００３６】
［第二実施形態］
図４を参照して、第二実施形態に係るソート装置２の構成例を説明する。ソート装置２は、第一実施形態に係るソート装置１と同様に、置換データ生成部１０、ランダムＩＤ列生成部１２、フラグ作成部１６及び順位表作成部１８を含み、秘密ランダム置換部２４及び整列部２６をさらに含む。
【００３７】
図５を参照しながら、第二実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００３８】
ステップＳ１０からステップＳ１２までの処理は第一実施形態に係る秘密計算方法と同様である。
【００３９】
ステップＳ２４において、秘密ランダム置換部２４は、i=1,…,L-1について、ランダムＩＤ列[r→i-1]ID、キー列[k→i]K及びランダムＩＤ列[r→i]IDの組([r→i-1]ID,[k→i]K,[r→i]ID)を置換データ<πi>で並列かつ同時に秘密ランダム置換し、置換後ランダムＩＤ列πir→i-1、置換後キー列[πik→i]K及び置換後ランダムＩＤ列[πir→i]IDの組(πir→i-1,[πik→i]K,[πir→i]ID)を生成する。続いて、ランダムＩＤ列[r→L-1]ID及びバリュー列[v→]Vの組([r→L-1]ID,[v→]V)を置換データ<πL>により秘密ランダム置換し、置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vの組(πLr→L-1,[πLv→]V)を生成する。
【００４０】
ステップＳ１６からステップＳ１８の処理は第一実施形態に係る秘密計算方法と同様である。
【００４１】
ステップＳ２６において、整列部２６は、順位表[s→]O、ランダムＩＤ列[r→i]、置換データ<π’i>、置換後キー列[πik→i]K、置換後ランダムＩＤ列[σir→i]ID及び置換後バリュー列[πLv→]Vを用いて、整列後バリュー列[σv→]を生成する。まず、置換関数σ0=Iを設定する。ただし、Iは恒等置換である。次に、i=0,…,L-1について、ランダムＩＤ列[r→i]IDを置換関数σiにより置換し、置換後ランダムＩＤ列[σir→i]IDを生成する。続いて、順位表[s→]O及び置換後ランダムＩＤ列[σir→i]IDを置換データ<π’i>により秘密ランダム置換し、置換後順位表π’is→及び置換後ランダムＩＤ列π’iσir→iを生成する。次に、置換後順位表π’is→に基づいて置換後ランダムＩＤ列π’iσir→iを整列し、整列後ランダムＩＤ列σi+1r→iを生成する。ここで、置換関数σi+1=s→-1σiである。さらに、i=0,…,L-2について、置換後ランダムＩＤ列πi+1r→i、置換後キー列[πi+1k→i+1]K及び置換後ランダムＩＤ列[πi+1r→i+1]IDの組(πi+1r→i,[πi+1k→i+1]K,[πi+1r→i+1]ID)と、整列後ランダムＩＤ列σi+1r→iとを、置換後ランダムＩＤ列πi+1r→iをキーとして等結合し、整列後ランダムＩＤ列σi+1r→i、整列後キー列[σi+1k→i+1]K及び整列後ランダムＩＤ列[σi+1r→i+1]IDの組(σi+1r→i,[σi+1k→i+1]K,[σi+1r→i+1]ID)を生成する。続いて、置換後ランダムＩＤ列πLr→L-1及び置換後バリュー列[πLv→]Vの組(πLr→L-1,[πLv→]V)と、整列後ランダムＩＤ列σLr→L-1とを、置換後ランダムＩＤ列πLr→L-1をキーとして等結合し、整列後バリュー列[σv→]Vを生成する。ここで、置換関数σ=σLである。
【００４２】
第一実施形態の秘密計算システムでは、キー列[k→]Kに基づいてソート置換σπ-1Lを生成する処理と、ソート置換σπ-1Lに基づいて整列後バリュー列[σv→]Vを得る処理とが分かれていた。このような構成とすることで、例えば、キー列k→とバリュー列v→が同一でありキー列k→のみをソートしたい場合などは、バリュー整列部の処理を省略することができる。第二実施形態の秘密計算システムでは、秘密ランダム置換部において、バリュー列[v→]VをランダムＩＤ列[r→L-1]IDと同じ置換データ<πL>で同時に秘密ランダム置換するため、キー列k→とバリュー列v→をいずれもソートしたい場合には、より通信段数を低減することができる。
【００４３】
［第三実施形態］
図６を参照して、第三実施形態に係るソート装置３の構成例を説明する。ソート装置３は、第一実施形態に係るソート装置１と同様に、置換データ生成部１０、ランダムＩＤ列生成部１２、秘密ランダム置換部１４、順位表作成部１８、ソート置換生成部２０及びバリュー整列部２２を含み、フラグ作成部２８をさらに含む。第三実施形態の構成は第二実施形態に応用することもできる。すなわち、第二実施形態に係るソート装置２と同様に、置換データ生成部１０、ランダムＩＤ列生成部１２、秘密ランダム置換部２４、順位表作成部１８及び整列部２６を含み、フラグ作成部２８をさらに含むように構成してもよい。
【００４４】
図７を参照しながら、第三実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００４５】
第一実施形態に係るソート装置１及び第二実施形態に係るソート装置２は、入力されるキー列k→の秘密分散値[k→]Kが、ビットの秘密分散値であった。すなわち、j=0,…,m-1について、キー[kj]K=([kj,0]B,…,[kj,L-1]B)と表すことができた。一方、第三実施形態に係るソート装置３では、入力されるキー列k→の秘密分散値[k→]Kが、m種類の順序集合を表現しうる空間上の秘密分散値である。すなわち、j=0,…,m-1について、キー[kj]K=([kj,0]O,…,[kj,L-1]O)と表すことができる。
【００４６】
ステップＳ１０からステップＳ１４までの処理は第一実施形態に係る秘密計算方法と同様である。
【００４７】
ステップＳ２８において、フラグ作成部２８は、j=0,…,m-1及びh=0,…,L-1について、キー[kj]K=([kj,0]O,…,[kj,L-1]O)に対して、kj=hであるか否かを判定して、並列かつ同時にフラグ[fj,h]を設定する。具体的には、kj=hであればフラグ[fj,h]O=[1]Oを、kj≠hであればフラグ[fj,h]O=[0]Oを設定する。フラグの設定は等号判定回路を利用すればよい。
【００４８】
ステップＳ１８からステップＳ２２までの処理は第一実施形態に係る秘密計算方法と同様である。
【００４９】
第一実施形態の秘密計算システムでは、キーkjをビット毎に秘密分散した秘密分散値[kj,0]B,…,[kj,L-1]Bからフラグ[fj,h]Bを設定するため、フラグ[fj,h]Bをフラグ[fj,h]Oへ変換する必要があった。第三実施形態の秘密計算システムでは、キーkjの各ビットをより広い空間上の秘密分散値[kj,0]O,…,[kj,L-1]Oとして取り扱い、直接フラグ[fj,h]Oを設定するため変換が不要である。これにより、第一実施形態よりも単純な構成となっており、実装が容易である。ただし、計算に用いる空間が広くなることで計算量は増えるため、第一実施形態の方が効率的に計算することができる。
【００５０】
［第四実施形態］
第四実施形態は、この発明の秘密ソートに対して秘密計算中の改ざんを検知することを可能とする実施形態である。秘密計算中の改ざんを検知する秘密改ざん検知方法として、下記参考文献２に記載の方法が提案されている。参考文献２では、３つのフェーズで秘密計算中の改ざん検知を行う。ランダム化フェーズでは、分散値を正当性検証可能なランダム化分散値へと変換する。計算フェーズでは、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→の分散値[k→]Kとバリューv→の分散値[v→]Vの組([k→]K,[v→]V)をランダム化分散値へ変換する。ランダム化分散値とは、値x∈Rの分散値[x]と、値x∈Rと乱数r∈Aとの積算値xrの分散値[xr]との組([x],[xr])である。ここで、Rは環であり、Aは環R上の結合多元環である。結合多元環とは、結合的な環であって、かつそれと両立するような、何らかの体上の線型空間の構造を備えたものである。結合多元環は、ベクトル空間で扱う値が体ではなく環でよくなったものと言える。ランダム化分散値の第０成分（[x]）はR成分、第１成分（[xr]）はA成分とも呼ぶ。
【００５６】
ランダム化分散値を生成する際に用いる乱数は、同一の環上の秘密分散を複数利用する場合には、一方の秘密分散のための分散値を他方の秘密分散のための分散値に変換することで、乱数の値が同一となるように生成する。この形式変換においても、改ざん検知が可能もしくは改ざんが不可能でなければならない。例えば、複製型秘密分散（replicated secret sharing）から線形秘密分散（linear secret sharing）へ変換する改ざん不可能な方法は下記参考文献４に記載されている。
〔参考文献４〕R. Cramer, I. Damgard, and Y. Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation”, TCC, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362, Springer, 2005.
【００５７】
ステップＳ１４からステップＳ１８において、秘密ランダム置換部１４、フラグ作成部１６及び順位表作成部１８は、計算対象のランダム化分散値と計算結果のランダム化分散値を秘密分散の種類ごとに用意したチェックサムCj（j=0,…,J-1、Ｊは秘密分散の種類の数）へ含めながら、所定の秘密計算を実行する。
【００５８】
ステップＳ３４において、ソート置換生成部３４は、順位表[s→]O及び置換後ランダムＩＤ列[σir→i]IDを置換データ<π’i>により秘密ランダム置換する際に、改ざん検知が可能な秘密ランダム置換方法を用いる。順位表[s→]O及び置換後ランダムＩＤ列[σir→i]IDに改ざんがあった場合、秘匿性が破られる可能性があるためである。改ざん検知が可能なランダム置換方法は、例えば、(k,n)-秘密分散値を加法的秘密分散値に変換し、置換と再分散を繰り返すようなランダム置換方法において、入力をランダム化分散値に変換し、一回の置換が終了するたびにランダム化分散値を加法的秘密分散値から(k,n)-秘密分散値へ変換してチェックサムに含め、反復するすべての置換が終了した後に下記ステップＳ３６と同様の正当性証明を行う。なお、ランダム置換の中では任意のタイミングでチェックサムの取得と正当性証明を繰り返すことが可能である。このとき、ランダム化分散値の生成は少なくとも入力に対して一回行っていればよい。
【００５９】
ステップＳ３６において、正当性証明部３６は、すべての秘密分散についてすべての秘密計算が終了するまで待機する同期処理（SYNC）を実行する。すべての秘密分散についてすべての秘密計算が終了したことを検知すると、ランダム化部３２で用いた乱数r0,…,rJ-1の分散値[r0],…,[rJ-1]を用いてチェックサムC0,…,CJ-1を検証し、秘密ソートの結果として得られる整列後バリュー列[σv→]Vの正当性を検証する。J個のチェックサムC0,…,CJ-1すべてを検証した結果、改ざんがないと判定した場合は整列後バリュー列[σv→]Vを出力する。改ざんがあったと判断した場合はその旨を示す情報（例えば、「⊥」など）を出力する。
【００６０】
チェックサムの検証は、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以外であれば改ざんがあったものと判定する。このようにして、すべての同一の環上の秘密分散の組み合わせについて検証し、秘密ソート全体で改ざんがなかったことを検証する。本形態では２個の秘密分散が同一の環上の秘密分散である例を説明したが、３個以上の秘密分散が同一の環上の秘密分散である場合でも、同様の方法により正当性証明を行うことができる。
【００６２】
本形態のように構成すれば、この発明の秘密ソートにおいて、改ざん検知が可能となり、安全性が向上する。
【００６３】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６４】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００６５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0006009697.tif 000006
【図２】
0006009697.tif 000007
【図３】
0006009697.tif 000008
【図４】
0006009697.tif 000009
【図５】
0006009697.tif 000010
【図６】
0006009697.tif 000011
【図７】
0006009697.tif 000012
【図８】
0006009697.tif 000013
【図９】
0006009697.tif 000014