特許
J-GLOBAL ID:201603001350053821

秘密計算方法、秘密計算システム、ソート装置及びプログラム

発明者:
出願人/特許権者:
代理人 (3件): 中尾 直樹 ,  中村 幸雄 ,  義村 宗洋
公報種別:特許公報
出願番号(国際出願番号):特願2015-557796
特許番号:特許第6009697号
出願日: 2015年01月07日
請求項(抜粋):
【請求項1】 Lビットのm個のキーk0,...,km-1の列k→の秘密分散値[k→]及びm個のバリューv0,...,vm-1の列v→の秘密分散値[v→]の組を入力とし、バリュー列v→を整列するためのソート置換σπ-1Lを生成する秘密計算方法であって、 置換データ生成部が、i=1,...,L-1について、置換データ<πi>,<π’i>を生成し、置換データ<πL>を生成する置換データ生成ステップと、 ランダムID列生成部が、i=1,...,L-1について、互いに重複した値を含まないランダムID列[r→i]を生成し、互いに重複した値を含まないランダムID列[r→L]を生成するランダムID列生成ステップと、 秘密ランダム置換部が、i=1,...,L-1について、ランダムID列[r→i-1]、キー列[k→i]及びランダムID列[r→i]の組を置換データ<πi>により秘密ランダム置換して置換後ランダムID列πir→i-1、置換後キー列[πik→i]及び置換後ランダムID列[πir→i]の組を生成し、ランダムID列[r→L-1]を置換データ<πL>により秘密ランダム置換して置換後ランダムID列π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について、ランダムID列[r→i]を置換関数σiにより置換して置換後ランダムID列[σir→i]を生成し、順位表[s→]及び置換後ランダムID列[σir→i]を置換データ<π’i>により秘密ランダム置換して置換後順位表π’is→及び置換後ランダムID列π’iσir→iを生成し、置換後順位表π’is→に基づいて置換後ランダムID列π’iσir→iを整列して整列後ランダムID列σi+1r→iを生成し、置換関数σi+1=s→-1σiを設定し、i=0,...,L-2について、置換後ランダムID列πi+1r→i、置換後キー列[πi+1k→i+1]及び置換後ランダムID列[πi+1r→i+1]の組と、整列後ランダムID列σi+1r→iとを、置換後ランダムID列πi+1r→iをキーとして等結合し、整列後ランダムID列σi+1r→i、整列後キー列[σi+1k→i+1]及び整列後ランダムID列[σi+1r→i+1]の組を生成し、置換後ランダムID列πLr→L-1と整列後ランダムID列σLr→L-1とを等結合してソート置換σπ-1Lを生成するソート置換生成ステップと、 を含む秘密計算方法。
IPC (3件):
G06F 7/08 ( 200 6.01) ,  G09C 1/00 ( 200 6.01) ,  G06F 21/60 ( 201 3.01)
FI (3件):
G06F 7/08 ,  G09C 1/00 650 Z ,  G06F 21/60
引用特許:
出願人引用 (2件)
引用文献:
出願人引用 (2件)
  • Secure Multi-Party Sorting and Applications
  • Bureaucratic Protocols for Secure Two-Party Sorting

前のページに戻る