(57)【要約】  従来よりも速い速度で秘匿ソートを行う技術を提供する。秘匿ソートシステムは、第１装置から第Ｍ装置を備えている。第１装置から第Ｍ装置は、{→k0}のLビット安定ソートの逆置換[[σ0-1]]を得る。第１装置から第Ｍ装置は、[[σi-1-1]]をハイブリッド置換に変換して{σi-1-1}を得る処理と、{→ki}を{σi-1-1}で逆置換して{σi-1→ki}を得る処理と、[[σi-1→ki]]のLビット安定ソートの逆置換[[σi'-1]]を得る処理と、[[σi'-1]]に{σi-1-1}を合成して[[σi-1]]:=[[σi-1-1σi'-1]]を得る処理とをi=1,…,N-1に対して行い、 [[σN-1-1]]をハイブリッド置換に変換して{σN-1-1}を得る処理を行う。第１装置から第Ｍ装置は、[[→v]]を{σN-1-1}で逆置換をして[[σN-1→v]]を出力する。
2019074044.tif 000002
【特許請求の範囲】
【請求項１】
第１装置、第２装置、…、第Ｍ装置を含む秘匿ソートシステムであって、
ソートされるべきデータの本体をバリュー→vとして、上記ソート後の順序を決めるタグをキーとし、上記キーのビット長をL'とし、Nを所定の正の整数とし、上記キーをN個のビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとし、任意の値又は置換をxAとして{xA}をxAの複製秘密分散値であるとし、任意の値をxAとして[[xA]]をxAの準同型性を持つ秘密分散値であるとし、Mを２以上の所定の正の整数とし、
上記第１装置、第２装置、…、第Ｍ装置は、{→k0}のLビット安定ソートの逆置換[[σ0-1]]を得て、
上記第１装置、第２装置、…、第Ｍ装置は、[[σi-1-1]]をハイブリッド置換に変換して{σi-1-1}を得る処理と、{→ki}を{σi-1-1}で逆置換して{σi-1→ki}を得る処理と、[[σi-1→ki]]のLビット安定ソートの逆置換[[σi'-1]]を得る処理と、[[σi'-1]]に{σi-1-1}を合成して[[σi-1]]:=[[σi-1-1σi'-1]]を得る処理とをi=1,…,N-1に対して行い、[[σN-1-1]]をハイブリッド置換に変換して{σN-1-1}を得る処理を行い、
上記第１装置、第２装置、…、第Ｍ装置は、[[→v]]を{σN-1-1}で逆置換をして[[σN-1→v]]を出力する、
秘匿ソートシステム。
【請求項２】
第１装置、第２装置及び第３装置を含む秘匿ソートシステムであって、
ソートされるべきデータの本体をバリュー→vとして、上記ソート後の順序を決めるタグをキーとし、上記キーのビット長をL'とし、Nを所定の正の整数とし、上記キーをN個のビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとし、任意の値又は置換をxAとして{xA}をxAの複製秘密分散値であるとし、任意の値をxAとして、[[xA]]をxAの準同型性を持つ秘密分散値であるとし、<xA>を準公開値とし、[xA]を(2,2)加法的秘密分散値とし、{→ki}(Z_2)^L=({→ki,0}Z_2,{→ki,1}Z_2,…, {→ki,L-1}Z_2)(i=0,…,N-1)とし、qを所定の正の整数とし、任意のベクトルを→fAとして(→fA)uをベクトル→fAのu個目の要素とし、s0:=0とし、j=1,…,3に対してsj:=Σ0≦u<m(→fj-1)u+sj-1とし、ベクトル→fj-1の要素の数をmとし、01は第１装置及び第２装置の集合を表し、12は第２装置及び第３装置の集合を表し、20は第３装置及び第１装置の集合を表し、Gを任意の群、環又は体とし、Pを装置の集合として[xA]G,PをPが持つG上で表された[xA]のシェアを表すとし、πを所定の置換とし、{π}PはPが共有する{π}のサブシェアを意味するとし、{π}01,12はπ={π}12{π}01となる複製秘密分散値を表すとし、<πσi-1>20はπσi-1が第３装置及び第１装置で共有されていることを表すとして、
上記第１装置、第２装置及び第３装置は、mod 2 → mod q変換により、{→k0,0}Z_2,{→k0,1}Z_2,…,{→k0,L-1}Z_2を[[→k0,0]]Z_q,[[→k0,1]]Z_q,…,[[→k0,L-1]]Z_qに変換する処理と、η<┌log L┐を満たす正の整数ηと、D⊆ZLかつ2η+1≦|D|≦min(2η+1,L)を満たすDとの組のそれぞれに対して、[[KD]]:=[[Πw∈D→k0,w]]Z_qを計算する処理と、jのビット表現のwビット目をjwとして、→k'0,wは、jw=0の場合には→k'0,w=1-→k0,w、jw=1の場合には→k'0,w=→k0,wとして、j<2Lの各jに対して、[[→fj]]Z_q:=Πj<L[[→k'0,w]]を求める処理と、 [[(→f'j)u]]Z_q:=Σ0≦t<u[[(→fj)t]]Z_q+[[sj]]Z_qを計算する処理と、 (2,2)出力積和により、[σ0-1]Z_q,01:=Σ0≦j<2^L[→f'j→fj]Z_q,01を計算する処理と、<πσ0-1>20:={π}01,12[σ0-1]Z_q,01を計算する処理を行い、
上記第１装置、第２装置及び第３装置は、i=1,…,N-1として、{→ki,0}Z_2,{→ki,1}Z_2,…,{→ki,L-1}Z_2を(2,2)加法的秘密分散値[→ki,0]Z_2,01,[→ki,1]Z_2,01,…,[→ki,L-1]Z_2,01に変換する処理と、[→ki,0]Z_2,01,[→ki,1]Z_2,01…,[→ki,L-1]Z_2,01に{σi-1-1}を逆適用し、[→b0]Z_2,20:=[σi-1ki,0]Z_2,20,[→b1]Z_2,20:=[σi-1ki,1]Z_2,20,…,[→bL-1]Z_2,20:=[σi-1ki,L-1]Z_2,20を得る処理と、mod 2 → mod q変換により、[→b0]Z_2,20,[→b1]Z_2,20,…,[→bL-1]Z_2,20を[[→b0]]Z_q,[[→b1]]Z_q,…,[→bL-1]Z_qに変換する処理と、η<┌log L┐を満たす正の整数ηと、D⊆ZLかつ2η+1≦|D|≦min(2η+1,L)を満たすDとの組のそれぞれに対して、[[KD]]:=[[Πw∈D→k0,w]]Z_qを計算する処理と、jのビット表現のwビット目をjwとして、→k'i,wは、jw=0の場合には→k'i,w=1-→ki,w、jw=1の場合には→k'i,w=→ki,wとして、j<2Lの各jに対して、[[→fj]]Z_q:=Πj<L[[→k'i,w]]を求める処理と、 [[(→f'j)u]]Z_q:=Σ0≦t<u[[(→fj)t]]Z_q+[[sj]]Z_qを計算する処理と、(2,2)出力積和により、[σ'-1]Z_q,20:=Σ0≦j<2^L[→f'j→fj]Z_q,20を計算する処理と、[σ-1]Z_q,20に{σi-1-1}を適用し、[σ-1]Z_q,01:= [σi-1-1σ'-1]Z_q,01を得る処理と、<πσi-1>20:={π}01,12[σ-1]Z_q,01を計算する処理をi=1,…,N-1に対して行い、
上記第１装置、第２装置、…、第Ｍ装置は、{σ-1}=(<πσN-1-1>20,{π}01,12)として、[[→v]]を{σ-1}で逆置換をして[[σ→v]]を出力する、
秘匿ソートシステム。
【請求項３】
ソートされるべきデータの本体をバリュー→vとして、上記ソート後の順序を決めるタグをキーとし、上記キーのビット長をL'とし、Nを所定の正の整数とし、上記キーをN個のビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとし、任意の値又は置換をxAとして{xA}をxAの複製秘密分散値であるとし、任意の値をxAとして[[xA]]をxAの準同型性を持つ秘密分散値であるとし、Mを２以上の所定の正の整数とし、
第１装置、第２装置、…、第Ｍ装置が、{→k0}のLビット安定ソートの逆置換[[σ0-1]]を得るステップと、
上記第１装置、第２装置、…、第Ｍ装置が、 [[σi-1-1]]をハイブリッド置換に変換して{σi-1-1}を得る処理と、{→ki}を{σi-1-1}で逆置換して{σi-1→ki}を得る処理と、[[σi-1→ki]]のLビット安定ソートの逆置換[[σi'-1]]を得る処理と、 [[σi'-1]]に{σi-1-1}を合成して[[σi-1]]:=[[σi-1-1σi'-1]]を得る処理とをi=1,…,N-1に対して行い、 [[σN-1-1]]をハイブリッド置換に変換して{σN-1-1}を得る処理を行うステップと、
上記第１装置、第２装置、…、第Ｍ装置が、[[→v]]を{σN-1-1}で逆置換をして[[σN-1→v]]を出力するステップと、
を含む秘匿ソート方法。
【請求項４】
ソートされるべきデータの本体をバリュー→vとして、上記ソート後の順序を決めるタグをキーとし、上記キーのビット長をL'とし、Nを所定の正の整数とし、上記キーをN個のビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとし、任意の値又は置換をxAとして{xA}をxAの複製秘密分散値であるとし、任意の値をxAとして、[[xA]]をxAの準同型性を持つ秘密分散値であるとし、<xA>を準公開値とし、[xA]を(2,2)加法的秘密分散値とし、{→ki}(Z_2)^L=({→ki,0}Z_2,{→ki,1}Z_2,…, {→ki,L-1}Z_2)(i=0,…,N-1)とし、qを所定の正の整数とし、任意のベクトルを→fAとして(→fA)uをベクトル→fAのu個目の要素とし、s0:=0とし、j=1,…,3に対してsj:=Σ0≦u<m(→fj-1)u+sj-1とし、ベクトル→fj-1の要素の数をmとし、01は第１装置及び第２装置の集合を表し、12は第２装置及び第３装置の集合を表し、20は第３装置及び第１装置の集合を表し、Gを任意の群、環又は体とし、Pを装置の集合として[xA]G,PをPが持つG上で表された[xA]のシェアを表すとし、πを所定の置換とし、{π}PはPが共有する{π}のサブシェアを意味するとし、{π}01,12はπ={π}12{π}01となる複製秘密分散値を表すとし、<πσi-1>20はπσi-1が第３装置及び第１装置で共有されていることを表すとして、
上記第１装置、第２装置及び第３装置が、mod 2 → mod q変換により、{→k0,0}Z_2,{→k0,1}Z_2,…,{→k0,L-1}Z_2を[[→k0,0]]Z_q,[[→k0,1]]Z_q,…,[[→k0,L-1]]Z_qに変換する処理と、η<┌log L┐を満たす正の整数ηと、D⊆ZLかつ2η+1≦|D|≦min(2η+1,L)を満たすDとの組のそれぞれに対して、[[KD]]:=[[Πw∈D→k0,w]]Z_qを計算する処理と、jのビット表現のwビット目をjwとして、→k'0,wは、jw=0の場合には→k'0,w=1-→k0,w、jw=1の場合には→k'0,w=→k0,wとして、j<2Lの各jに対して、[[→fj]]Z_q:=Πj<L[[→k'0,w]]を求める処理と、 [[(→f'j)u]]Z_q:=Σ0≦t<u[[(→fj)t]]Z_q+[[sj]]Z_qを計算する処理と、 (2,2)出力積和により、[σ0-1]Z_q,01:=Σ0≦j<2^L[→f'j→fj]Z_q,01を計算する処理と、<πσ0-1>20:={π}01,12[σ0-1]Z_q,01を計算する処理を行うステップと、
上記第１装置、第２装置及び第３装置が、i=1,…,N-1として、{→ki,0}Z_2,{→ki,1}Z_2,…,{→ki,L-1}Z_2を(2,2)加法的秘密分散値[→ki,0]Z_2,01,[→ki,1]Z_2,01,…,[→ki,L-1]Z_2,01に変換する処理と、[→ki,0]Z_2,01,[→ki,1]Z_2,01…,[→ki,L-1]Z_2,01に{σi-1-1}を逆適用し、[→b0]Z_2,20:=[σi-1ki,0]Z_2,20,[→b1]Z_2,20:=[σi-1ki,1]Z_2,20,…,[→bL-1]Z_2,20:=[σi-1ki,L-1]Z_2,20を得る処理と、mod 2 → mod q変換により、[→b0]Z_2,20,[→b1]Z_2,20,…,[→bL-1]Z_2,20を[[→b0]]Z_q,[[→b1]]Z_q,…,[→bL-1]Z_qに変換する処理と、η<┌log L┐を満たす正の整数ηと、D⊆ZLかつ2η+1≦|D|≦min(2η+1,L)を満たすDとの組のそれぞれに対して、[[KD]]:=[[Πw∈D→k0,w]]Z_qを計算する処理と、jのビット表現のwビット目をjwとして、→k'i,wは、jw=0の場合には→k'i,w=1-→ki,w、jw=1の場合には→k'i,w=→ki,wとして、j<2Lの各jに対して、[[→fj]]Z_q:=Πj<L[[→k'i,w]]を求める処理と、 [[(→f'j)u]]Z_q:=Σ0≦t<u[[(→fj)t]]Z_q+[[sj]]Z_qを計算する処理と、(2,2)出力積和により、[σ'-1]Z_q,20:=Σ0≦j<2^L[→f'j→fj]Z_q,20を計算する処理と、[σ-1]Z_q,20に{σi-1-1}を適用し、[σ-1]Z_q,01:= [σi-1-1σ'-1]Z_q,01を得る処理と、<πσi-1>20:={π}01,12[σ-1]Z_q,01を計算する処理をi=1,…,N-1に対して行うステップと、
上記第１装置、第２装置、…、第Ｍ装置が、{σ-1}=(<πσN-1-1>20,{π}01,12)として、 [[→v]]を{σ-1}で逆置換をして[[σ→v]]を出力するステップと、
を含む秘匿ソート方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。
【背景技術】
【０００２】
従来の秘匿ソート技術として、非特許文献１に記載された技術が知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】五十嵐大, 菊池亮, 濱田浩気, 千田浩司, 「複数体上active モデルで秘匿性・正当性を保証する秘密分散ベース秘密計算と高速秘密計算ソートへの応用」, In SCIS2015, 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の非特許文献１の技術は、ソート処理に伴う通信量が大きいため通信がボトルネックとなりソート処理の速度が遅くなる可能性があった。【０００５】
この発明の目的は、従来よりも速い速度で秘匿ソートを行うことができる秘匿ソートシステム及び方法を提供することである。
【課題を解決するための手段】
【０００６】
この発明の一態様による秘匿ソートシステムは、第１装置、第２装置、…、第Ｍ装置を備えている。ソートされるべきデータの本体をバリュー→vとして、上記ソート後の順序を決めるタグをキーとし、上記キーのビット長をL'とし、Nを所定の正の整数とし、上記キーをN個のビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとし、任意の値又は置換をxAとして{xA}をxAの複製秘密分散値であるとし、任意の値をxAとして[[xA]]をxAの準同型性を持つ秘密分散値であるとし、Mを２以上の所定の正の整数とし、第１装置、第２装置、…、第Ｍ装置は、{→k0}のLビット安定ソートの逆置換[[σ0-1]]を得る。第１装置、第２装置、…、第Ｍ装置は、[[σi-1-1]]をハイブリッド置換に変換して{σi-1-1}を得る処理と、{→ki}を{σi-1-1}で逆置換して{σi-1→ki}を得る処理と、[[σi-1→ki]]のLビット安定ソートの逆置換[[σi'-1]]を得る処理と、[[σi'-1]]に{σi-1-1}を合成して[[σi-1]]:=[[σi-1-1σi'-1]]を得る処理とをi=1,…,N-1に対して行い、 [[σN-1-1]]をハイブリッド置換に変換して{σN-1-1}を得る処理を行う。第１装置、第２装置、…、第Ｍ装置は、[[→v]]を{σN-1-1}で逆置換をして[[σN-1→v]]を出力する。【０００７】
この発明の一態様による秘匿ソートシステムは、第１装置、第２装置、…、第Ｍ装置を備えている。ソートされるべきデータの本体をバリュー→vとして、上記ソート後の順序を決めるタグをキーとし、上記キーのビット長をL'とし、Nを所定の正の整数とし、上記キーをN個のビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとし、任意の値又は置換をxAとして{xA}をxAの複製秘密分散値であるとし、任意の値をxAとして、[[xA]]をxAの準同型性を持つ秘密分散値であるとし、<xA>を準公開値とし、[xA]を(2,2)加法的秘密分散値とし、{→ki}(Z_2)^L=({→ki,0}Z_2,{→ki,1}Z_2,…, {→ki,L-1}Z_2)(i=0,…,N-1)とし、qを所定の正の整数とし、任意のベクトルを→fAとして(→fA)uをベクトル→fAのu個目の要素とし、s0:=0とし、j=1,…,3に対してsj:=Σ0≦u<m(→fj-1)u+sj-1とし、ベクトル→fj-1の要素の数をmとし、01は第１装置及び第２装置の集合を表し、12は第２装置及び第３装置の集合を表し、20は第３装置及び第１装置の集合を表し、Gを任意の群、環又は体とし、Pを装置の集合として[xA]G,PをPが持つG上で表された[xA]のシェアを表すとし、πを所定の置換とし、{π}PはPが共有する{π}のサブシェアを意味するとし、{π}01,12はπ={π}12{π}01となる複製秘密分散値を表すとし、<πσi-1>20はπσi-1が第３装置及び第１装置で共有されていることを表すとして、第１装置、第２装置及び第３装置は、mod 2 → mod q変換により、{→k0,0}Z_2,{→k0,1}Z_2,…,{→k0,L-1}Z_2を[[→k0,0]]Z_q,[[→k0,1]]Z_q,…,[[→k0,L-1]]Z_qに変換する処理と、η<┌log L┐を満たす正の整数ηと、D⊆ZLかつ2η+1≦|D|≦min(2η+1,L)を満たすDとの組のそれぞれに対して、[[KD]]:=[[Πw∈D→k0,w]]Z_qを計算する処理と、jのビット表現のwビット目をjwとして、→k'0,wは、jw=0の場合には→k'0,w=1-→k0,w、jw=1の場合には→k'0,w=→k0,wとして、j<2Lの各jに対して、[[→fj]]Z_q:=Πj<L[[→k'0,w]]を求める処理と、 [[(→f'j)u]]Z_q:=Σ0≦t<u[[(→fj)t]]Z_q+[[sj]]Z_qを計算する処理と、 (2,2)出力積和により、[σ0-1]Z_q,01:=Σ0≦j<2^L[→f'j→fj]Z_q,01を計算する処理と、<πσ0-1>20:={π}01,12[σ0-1]Z_q,01を計算する処理を行う。第１装置、第２装置及び第３装置は、i=1,…,N-1として、{→ki,0}Z_2,{→ki,1}Z_2,…,{→ki,L-1}Z_2を(2,2)加法的秘密分散値[→ki,0]Z_2,01,[→ki,1]Z_2,01,…,[→ki,L-1]Z_2,01に変換する処理と、[→ki,0]Z_2,01,[→ki,1]Z_2,01…,[→ki,L-1]Z_2,01に{σi-1-1}を逆適用し、[→b0]Z_2,20:=[σi-1ki,0]Z_2,20,[→b1]Z_2,20:=[σi-1ki,1]Z_2,20,…,[→bL-1]Z_2,20:=[σi-1ki,L-1]Z_2,20を得る処理と、mod 2 → mod q変換により、[→b0]Z_2,20,[→b1]Z_2,20,…,[→bL-1]Z_2,20を[[→b0]]Z_q,[[→b1]]Z_q,…,[→bL-1]Z_qに変換する処理と、η<┌log L┐を満たす正の整数ηと、D⊆ZLかつ2η+1≦|D|≦min(2η+1,L)を満たすDとの組のそれぞれに対して、[[KD]]:=[[Πw∈D→k0,w]]Z_qを計算する処理と、jのビット表現のwビット目をjwとして、→k'i,wは、jw=0の場合には→k'i,w=1-→ki,w、jw=1の場合には→k'i,w=→ki,wとして、j<2Lの各jに対して、[[→fj]]Z_q:=Πj<L[[→k'i,w]]を求める処理と、 [[(→f'j)u]]Z_q:=Σ0≦t<u[[(→fj)t]]Z_q+[[sj]]Z_qを計算する処理と、(2,2)出力積和により、[σ'-1]Z_q,20:=Σ0≦j<2^L[→f'j→fj]Z_q,20を計算する処理と、[σ-1]Z_q,20に{σi-1-1}を適用し、[σ-1]Z_q,01:= [σi-1-1σ'-1]Z_q,01を得る処理と、<πσi-1>20:={π}01,12[σ-1]Z_q,01を計算する処理をi=1,…,N-1に対して行う。第１装置、第２装置、…、第Ｍ装置は、{σ-1}=(<πσN-1-1>20,{π}01,12)として、[[→v]]を{σ-1}で逆置換をして[[σ→v]]を出力する。
【発明の効果】
【０００８】
従来よりも速い速度で秘匿ソートを行うことができる。
【図面の簡単な説明】
【０００９】
【図１】第一実施形態の秘匿ソートシステムの例を示すブロック図。
【図２】第一実施形態を説明するための図。
【図３】第一実施形態を説明するための図。
【図４】第一実施形態を説明するための図。
【図５】第一実施形態を説明するための図。
【図６】第二実施形態の秘匿ソートシステムの例を示すブロック図。
【図７】第二実施形態を説明するための図。
【図８】第二実施形態を説明するための図。
【図９】第二実施形態を説明するための図。
【図１０】第二実施形態を説明するための図。
【図１１】第二実施形態を説明するための図。
【図１２】第二実施形態を説明するための図。
【図１３】第二実施形態を説明するための図。
【図１４】第二実施形態を説明するための図。
【図１５】第二実施形態を説明するための図。
【図１６】第二実施形態を説明するための図。
【図１７】第二実施形態を説明するための図。
【図１８】第二実施形態を説明するための図。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、この発明の一実施形態について説明する。なお、数式等において、logの底を省略した場合、底は2である。
【００１１】
［準備］
ソートの対象には、キーとバリューがある。キーはソート後の順序を決めるタグであり、バリューはソートされるべきデータ本体である。キーとバリューが同一のこともある。
【００１２】
秘密分散値とは、秘密分散された全パーティのシェアを仮想的に集めた組である。
【００１３】
置換πをベクトル→xに適用した結果を乗法的に表記し、π→xと書く。また、整数ベクトルは置換としても扱い、ベクトルの乗法的記法→y→xは、→xの→yによる置換を表す。なお、記載の簡略化のためにベクトルを意味する「→」を省略することもある。
【００１４】
以下のように、記号類を定義する。
m:ソート及び置換対象のベクトルの要素数。
L':キーのビット長。
p,q:素数。
|p|,|q|:素数のビット長。
[[x]]:準同形性を持つ秘密分散値。すなわち、任意の値をxAとして[[xA]]をxAの準同型性を持つ秘密分散値であるとする。
{x}:複製秘密分散値であることを明示する記法。すなわち、任意の値又は置換をxAとして{xA}をxAの複製秘密分散値であるとする。
[x]:(2,2) 加法的秘密分散値。
<x>:準公開値。すなわち、kパーティで共有する平文。
[[X]]:X上の秘密分散値の集合。
[x]X,P:上記分散値等で、肩の上の1 個目の添え字は群/環/体、2個目の添え字はシェアを持つパーティ集合を表す。すなわち、Gを任意の群、環又は体とし、Pを装置の集合として[x]G,PはPが持つ、G上で表された[x]のシェアを表す。
→x,[[→x]]X:長さmのベクトル及びその秘密分散値。
【００１５】
P':パーティ全体の集合。
01,12,20:添え字に使ったとき、それぞれパーティ0と1,パーティ1と2,パーティ2と0のパーティ集合を表す。例えば、01は第１装置及び第２装置の集合を表し、12は第２装置及び第３装置の集合を表し、20は第３装置及び第１装置の集合を表す。なお、第１装置のことをP0、第２装置のことをP1、第３装置のことをP2と表記することもある。
【００１６】
[[x]]P:パーティPのシェア。
{π}:置換πの複製秘密分散値。
{π}P:P∈P'が共有する{π}の断片(サブシェア)。
{π}01,12,20のように添え字付きの置換の複製秘密分散値：π={π}20{π}12{π}01となる複製秘密分散値。すなわち、置換の適用順まで気にした場合の記法。
{π}01,12のように3 個未満の添え字付きの置換の複製秘密分散値: π={π}12{π}01となる複製秘密分散値。
【００１７】
ここで、複製秘密分散とは、複数のパーティ集合ごとに、パーティ集合内で同じ値を共有するような秘密分散である。例えば(2,3)-複製秘密分散は、a=a01+a12+a20とし、各パーティのシェアは(a20,a01),(a01,a12),(a12,a20)となる。各a01,a12,a20をサブシェアと呼ぶ。ここでは、置換が群であることを利用し、置換を秘匿する秘密分散としても利用する。
【００１８】
ソートは置換の一種である。ここでは、秘密計算における置換の理論を構成し、それに基づいて効率的でシンプルな基数ソートを構成する。
【００１９】
秘密計算において置換を体系的に扱われたことはなかった。ここでは、より置換を自由に扱えるようにするため、置換に関して体系的に整理する。まず、置換自体や、既存の秘密計算における置換をおさらいし、その上で置換の理論を展開する。
【００２０】
置換とは並び替えを表現する数学的構造である。例えば、置換(0,2,1)はベクトル(10,5,2)を(10,2,5)に並び替える。
【００２１】
置換は非可換群を為すことが知られている。すなわち、単位元が存在し(恒等置換, 並びを変化させない置換)、逆元が存在し(置換した後に逆元で置換すると元に戻る)、結合律が成り立つ。
【００２２】
秘密計算におけるランダム置換は筆者ら及びLaurによって独立に提案され改良されている（例えば、参考文献１，２参照）。複製秘密分散は群で構成できるため、置換の複製秘密分散を考えることができ、例えば(2,3)-複製秘密分散では、π=π20π12π01とするとき、各分散値は(π20,π01),(π01,π12),(π12,π20)となる。上記ランダム置換はいずれもこの置換を適用するプロトコルと見なすことができる。
【００２３】
〔参考文献１〕濱田浩気，五十嵐大，千田浩司，高橋克巳, 「3 パーティ秘匿関数計算のランダム置換プロトコル」，CSS2010 (2010).
〔参考文献２〕Laur, S., Willemson, J. and Zhang, B., "Round-Efficient Oblivious Database Manipulation", ISC (Lai, X., Zhou, J. and Li, H.,eds.), Lecture Notes in Computer Science, Vol. 7001, Springer, pp. 262-277 (2011).
【００２４】
ランダム置換プロトコルで、置換{π}の各サブシェア{π}01,{π}12,{π}20の逆元({π}01)-1,({π}12)-1,({π}20)-1を逆順に適用するように実行すると、逆行列{π}-1で置換したのと同じ効果が得られる（例えば、参考文献３参照。）。これは、一度ランダム置換して、元の並びに戻すなどの処理に使うことができる。
【００２５】
〔参考文献３〕桐淵直人，五十嵐大，諸橋玄武，濱田浩気, 「属性情報と履歴情報の秘匿統合分析に向けた秘密計算による高速な等結合アルゴリズムとその実装」，CSS2016 (2016).
【００２６】
置換の複製秘密分散を本発明ではネイティブ置換と呼ぶ。ネイティブ置換だけでは、ランダム置換しか表現できず、より豊富な置換を扱うことはできない。そのため、本稿では、インデックス置換、ハイブリッド置換の2つを導入する。
【００２７】
長さmの整数分散値のベクトルであって、0〜m-1の互いに異なる値を要素とするものをインデックス置換と呼ぶことにする。インデックス置換を置換として直接適用することはできないが、ネイティブ置換を適用することで、ネイティブ置換との置換の合成を行うことができる。例えば、[[π]]に{ρ}を適用すると[[ρπ]]となり、合成されたインデックス置換となる。恒等置換Iのインデックス置換[[I]]に合成を適用すれば、ネイティブ置換{π}をインデックス置換[[π]]に変換することもできる。
【００２８】
ハイブリッド置換は、ネイティブ置換と平文の置換の組である。({ρ},ρ-1π)を{{π}}と書き、ハイブリッド置換と呼ぶことにする。ハイブリッド置換からネイティブ置換への変換がオフライン処理なので、{{π}}を{π}と表記することもある。ハイブリッド置換はネイティブ置換と平文の置換の組であるから、順番に適用することで適用および逆適用が可能である。また、適用が可能なので、インデックス置換と置換の合成および、インデックス置換への変換を行うことができる。
【００２９】
ハイブリッド置換ではさらに、インデックス置換からの変換が可能である。[[π]]に{ρ-1}を適用すると[[ρ-1π]]となり、公開によりρ-1πを得る。({ρ},ρ-1π)はハイブリッド置換になっている。
【００３０】
インデックス置換がランダム置換以外も扱えるため、ハイブリッド置換もランダムでない置換を秘匿することができる。ランダムでない置換を秘匿性をもって適用するためにはハイブリッド置換が必要になる。
【００３１】
ハイブリッド置換はネイティブ置換への変換も可能である。{ρ}を{ρ}01,12,20と書くとき、{ρ}2001,12,20にρ-1πを合成すればよい。ρ-1πが公開値なのでこの処理はオフラインである。
【００３２】
なお、ハイブリッド置換からネイティブ置換への変換がオフライン処理なので、抽象的な粒度のプロトコルではハイブリッド置換をネイティブ置換と同一視して{π}のように書くことにする。
【００３３】
以下に、上記及び簡単に構成可能な置換操作をまとめた。ネイティブ置換だけでなくインデックス置換とハイブリッド置換を経由することで、置換、逆置換、変換、合成の４操作を自由に行うことができる。合成がインデックス置換、合成後の置換/逆置換がハイブリッド置換を必要とすることに注意する。
【００３４】
[[置換適用]]
1. ネイティブ置換:{π}[[x]]=[[x]](ランダム置換プロトコル)
2. インデックス置換: 直接は不可。ハイブリッド置換を経由。
3. ハイブリッド置換: ({ρ}ρ-1π[[x]])
【００３５】
[[逆置換適用]]
1. ネイティブ置換: {π}[[x]]
2. インデックス置換: 直接は不可。ハイブリッド置換を経由。
3. ハイブリッド置換: (ρ-1)-1{ρ}-1[[x]]
【００３６】
[[変換]]
1. ネイティブ置換→インデックス置換: {π}[[I]]=[[π]]
2. インデックス置換→ネイティブ置換: ハイブリッド置換を経由。
3. ネイティブ置換→ハイブリッド置換: ({π},I)
4. ハイブリッド置換→ネイティブ置換: {ρ}01,12,20の{ρ}2001,12,20にρ-1πを合成する。
5. インデックス置換→ハイブリッド置換: {{π}}[[I]]={{π}}
6. ハイブリッド置換→インデックス置換: {{π}}[[I]]=[[π]]
【００３７】
[[合成]]
1. インデックス置換とネイティブ置換: {ρ}[[π]]=[[ρπ]]
2. インデックス置換とハイブリッド置換: {{ρ}}[[π]]
3. その他の組み合わせはインデックス置換を経由。
【００３８】
［第一実施形態］
図１に示すように、第一実施形態の秘匿ソートシステムは、第１装置１、第２装置２、…、第Ｍ装置Ｍを例えば備えている。Mを２以上の所定の正の整数である。この例では、パーティがＭ個あり、Ｍ個のパーティは、それぞれ第１装置１、第２装置２、…、第Ｍ装置Ｍである。
【００３９】
第一実施形態の秘匿ソート方法は、第１装置１、第２装置２、…、第Ｍ装置Ｍが、図２のScheme 4-1及び図３のScheme 4-2の各処理を行うことにより例えば実現される。以下、「第１装置１、第２装置２、…、第Ｍ装置Ｍが、○○を行う」と言った場合には、第１装置１、第２装置２、…、第Ｍ装置Ｍが、共同して秘密計算により〇〇を行うことを意味する。もちろん、○○の処理が秘密計算の必要がない場合には、第１装置１、第２装置２、…、第Ｍ装置Ｍは、秘密計算を行う必要はない。
【００４０】
まず、第１装置１、第２装置２、…、第Ｍ装置Ｍは、図２に示すScheme 4-1の処理を行うことにより、秘匿ソート処理をまずキーについて行う。
【００４１】
Scheme 4-1の「1:」において、第１装置、第２装置、…、第Ｍ装置は、{→k0}のLビット安定ソートの逆置換[[σ0-1]]を得る（Scheme 4-1の「1:」）。ここで、キーのビット長をL'とし、Lを所定の正の整数とし、NをNL=L'を満たす正の整数とし、キーをビット長Lのビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとする。Lビット安定ソートの逆置換は、例えば、図４のScheme 3-1及び図５のScheme 3-2により行うことができる。図４及び図５において、[[k]](Z_2)^L=([[k0]]Z_2,[[k1]]Z_2,…, [[kL-1]]Z_2)であり、[[f]](Z_q)^(2^L)=([[f0]]Z_q,[[f1]]Z_q,…, [[f(2^L)-1)]]Z_q)である。(fj)iは、ベクトルjのi番目の要素を表す。mは、前記の通り、ソート及び置換対象のベクトルの要素数である。具体的には、図４のmはkjの要素数であり、図５のmはfjの要素数である。
図４において、mod 2 → mod q変換は、例えば、図１３のScheme 3-3により行うことができる。図１３のreveal()は、revealの括弧の中の秘密分散を復元して公開することを表す。
【００４２】
Scheme 4-1の「2:」から[6:]において、第１装置、第２装置、…、第Ｍ装置は、各i=1,…,Nに対して、Scheme 4-1の「3:」から[6:]の処理を行う。
【００４３】
すなわち、第１装置、第２装置、…、第Ｍ装置が、i=1,…,N-1として、[[σi-1-1]]をハイブリッド置換に変換して{σi-1-1}を得る（Scheme 4-1の「3:」）。
【００４４】
第１装置、第２装置、…、第Ｍ装置が、i=1,…,N-1として、{→ki}を{σi-1-1}で逆置換して{σi-1→ki}を得る（Scheme 4-1の「4:」）。
【００４５】
第１装置、第２装置、…、第Ｍ装置が、i=1,…,N-1として、[[σi-1→ki]]のLビット安定ソートの逆置換[[σi'-1]]を得る(Scheme 4-1の「5:」)。
【００４６】
第１装置、第２装置、…、第Ｍ装置が、i=1,…,N-1として、[[σi'-1]]に{σi-1-1}を合成して[[σi-1]]:=[[σi-1-1σi'-1]] を得る（Scheme 4-1の「6:」）。
【００４７】
Scheme 4-1の「7:」において、第１装置、第２装置、…、第Ｍ装置は、[[σN-1-1]]をハイブリッド置換に変換して{σN-1-1}を得る（Scheme 4-1の「7:」）。
【００４８】
次に、第１装置１、第２装置２、…、第Ｍ装置Ｍは、図３に示すScheme 4-2の処理を行うことにより、秘匿ソート処理をバリューについて行う。
【００４９】
すなわち、第１装置１、第２装置２、…、第Ｍ装置Ｍは、図３に示すScheme 4-2の「1:」において、[[→v]]を{σN-1-1}で逆置換をして[[σN-1→v]]を出力する（Scheme 4-2の「1:」）。→vは、ソートされるべきデータの本体であるバリューである。
【００５０】
このように、逆置換を用いることで従来よりも秘匿ソートのアルゴリズムをシンプルにすることができる。これにより、従来よりも速い速度で秘匿ソートを行うことができる。
【００５１】
なお、いわゆるpassive（攻撃者は盗み見はするが不正な処理はしないセキュリティ）版で第一実施形態の秘密計算を行う場合には、Shamir秘密分散又は複製秘密分散を用いることができる。
【００５２】
Shamir秘密分散を用いる場合には、ランダム置換及び逆置換は、参考文献４に記載された方法（例えば、2.5, Shuffling Protocol）で行えばよい。また、公開は、参考文献５に記載された方法で行えばよい。また、公開値出力ランダム置換は、参考文献４に記載された方法でランダム置換を行った後に、参考文献５に記載された方法で公開を行えばよい。また、加算、乗算及び積和は、参考文献６に記載された方法（例えば、The Computation Stage）で行えばよい。また、Lビット安定ソートは、参考文献２に記載された方法（例えば、Scheme 6+7）で行えばよい。
【００５３】
複製秘密分散を用いる場合には、ランダム置換及び逆置換は、参考文献４に記載された方法（例えば、2.5, Shuffling Protocol）で行えばよい。公開は、参考文献７に記載された方法（例えば、cramer2005, 2.Preliminaries, 2.Replicated Secret-sharing）で行えばよい。公開値出力ランダム置換は、参考文献４に記載された方法でランダム置換を行った後に、参考文献７に記載された方法で公開を行えばよい。また、加算、乗算及び積和は、参考文献８に記載された方法（例えば、プロトコル1,7）で行えばよい。また、Lビット安定ソートは、参考文献２に記載された方法（例えば、Scheme 6+7）で行えばよい。
【００５４】
いわゆるactive（攻撃者が不正が処理をしても安全）版で第一実施形態の秘密計算を行う場合には、Shamir秘密分散を用いることができる。
【００５５】
active版で第一実施形態の秘密計算を行う場合においてShamir秘密分散を用いる場合には、ランダム置換及び逆置換は、参考文献９に記載された方法（例えば、Scheme 6）で行えばよい。また、公開は、参考文献１０に記載された方法（例えば、Scheme 12）で行えばよい。また、公開値出力ランダム置換は、参考文献９に記載された方法でランダム置換を行った後に、参考文献１０に記載された方法で公開を行えばよい。また、加算、乗算及び積和は、参考文献９に記載された方法（例えば、Scheme 3から5）で行えばよい。また、Lビット安定ソートは、参考文献２に記載された方法（例えば、Scheme 6+7）で行えばよい。
【００５６】
〔参考文献４〕Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, Katsumi Takahashi, "Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms", ICISC 2012: 202-216
〔参考文献５〕Adi Shamir, "How to Share a Secret", Commun. ACM 22(11): 612-613 (1979)
〔参考文献６〕Michael Ben-Or, Shafi Goldwasser, Avi Wigderson, "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)", STOC 1988: 1-10
〔参考文献７〕Ronald Cramer, Ivan Damgard, Yuval Ishai, "Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation", TCC 2005: 342-362
〔参考文献８〕五十嵐大, 千田浩司, 濱田浩気, 高橋克巳, 「軽量検証可能3パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理」
〔参考文献９〕五十嵐大, 菊池亮, 濱田浩気, 千田浩司, 「複数体上active モデルで秘匿性・正当性を保証する秘密分散ベース秘密計算と高速秘密計算ソートへの応用」, In SCIS2015, 2015.
〔参考文献１０〕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, 2014:304, 2014.
【００５７】
［第二実施形態］
第二実施形態は、図６に示すように、第１装置１、第２装置２及び第３装置３を例えば備えている。この例では、パーティが３個あり、３個のパーティは、それぞれ第１装置１、第２装置２及び第３装置Ｍである。
【００５８】
第二実施形態の秘匿ソート方法は、第１装置１、第２装置２及び第３装置３が、図７のScheme 5及び図８のScheme 5-3の各処理を行うことにより例えば実現される。以下、「第１装置１、第２装置２及び第３装置３が、○○を行う」と言った場合には、第１装置１、第２装置２及び第３装置３が、共同して秘密計算により〇〇を行うことを意味する。もちろん、○○の処理が秘密計算の必要がない場合には、第１装置１、第２装置２及び第３装置３は、秘密計算を行う必要はない。
【００５９】
まず、第１装置１、第２装置２及び第３装置３は、図７に示すScheme 5の処理を行うことにより、秘匿ソート処理をまずキーについて行う。
【００６０】
Scheme 5の「1:」において、第１装置、第２装置及び第３装置３は、{→k0}(Z_2)^Lに対してScheme 5-1の処理を行うことにより、{σ0-1}=(<πσ0-1>20,{π}01,12)を得る（Scheme 5の「1:」）。
【００６１】
ここで、i=0,…,N-1として、{→ki}(Z_2)^L=({→ki,0}Z_2,{→ki,1}Z_2,…, {→ki,L-1}Z_2)である。また、キーのビット長をL'とし、Lを所定の正の整数とし、NをNL=L'を満たす正の整数とし、キーをビット長Lのビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとする。
【００６２】
Scheme 5の「2:」「3:」において、第１装置、第２装置及び第３装置３は、{→ki}(Z_2)^Lに対するScheme 5-2の処理をi=0,…,N-1について行うことにより、最終的に{σN-1-1}=(<πσN-1-1>20,{π}01,12)を得る（Scheme 5の「2:」「3:」）。
【００６３】
次に、第１装置１、第２装置２及び第３装置３は、図８に示すScheme 5-3の処理を行うことにより、秘匿ソート処理をバリューについて行う。
【００６４】
すなわち、第１装置１、第２装置２及び第３装置３は、図８に示すScheme 5-3の「1:」において、[[→v]]を{σN-1-1}で逆置換をして[[σN-1→v]]を出力する（Scheme 5-3の「1:」）。→vは、ソートされるべきデータの本体であるバリューである。
【００６５】
以下、図９及び図１０のScheme 5-1について説明する。
【００６６】
Scheme 5-1の「1:」において、第１装置、第２装置及び第３装置３は、mod 2 → mod q変換により、{→k0,0}Z_2,{→k0,1}Z_2,…,{→k0,L-1}Z_2を[[→k0,0]]Z_q,[[→k0,1]]Z_q,…,[[→k0,L-1]]Z_qに変換する（Scheme 5の「1:」）。ここで、qを所定の正の整数とする。mod 2 → mod q変換は、例えば、図１３のScheme 3-3により行うことができる。
【００６７】
Scheme 5-1の「2:」から「5:」において、第１装置、第２装置及び第３装置３は、η<┌log L┐を満たす正の整数ηと、D⊆ZLかつ2η+1≦|D|≦min(2η+1,L)を満たすDとの組のそれぞれに対して、[[KD]]:=[[Πw∈D→k0,w]]Z_qを計算する（Scheme 5の「2:」から「5:」）。ここで、xAを任意の実数として、┌xA┐は天井関数である。すなわち、┌xA┐は実数xAに対してxA以上の最小の整数を表す。ここで、":="は、"="と同じ意味である。
【００６８】
Scheme 5-1の「6:」から「8:」において、第１装置、第２装置及び第３装置３は、j<2Lの各jに対して、[[→fj]]Z_q:=Πj<L[[→k'0,w]]を求める処理を行う（Scheme 5-1の「6:」から「8:」）。ここで、jのビット表現のwビット目をjwとして、→k'0,wは、jw=0の場合には→k'0,w=1-→k0,w、jw=1の場合には→k'0,w=→k0,wとする。
【００６９】
Scheme 5-1の「9:」において、第１装置、第２装置及び第３装置３は、[[(→f'j)u]]Z_q:=Σ0≦t<u[[(→fj)t]]Z_q+[[sj]]Z_qを計算する処理を行う（Scheme 5-1の「9:」）。ここで、任意のベクトルを→fAとして(→fA)uをベクトル→fAのu個目の要素とし、s0:=0とし、j=1,…,3に対してsj:=Σ0≦u<m(→fj-1)u+sj-1とし、ベクトル→fj-1の要素の数をmとする。
【００７０】
Scheme 5-1の「10:」において、第１装置、第２装置及び第３装置３は、(2,2)出力積和により、[σ0-1]Z_q,01:=Σ0≦j<2^L[→f'j→fj]Z_q,01を計算する処理を行う（Scheme 5-1の「10:」）。(2,2)出力積和の計算は、例えば、図１４のScheme 5-4により行うことができる。(2,2)出力積和とは、(2,2)-加法的秘密分散形式の出力を得る積和処理である。
【００７１】
Scheme 5-1の「11:」において、<πσ0-1>20:={π}01,12[σ0-1]Z_q,01を計算する処理を行う（Scheme 5-1の「11:」）。ここで、<πσi-1>20はπσi-1が第３装置及び第１装置で共有されていることを表す。Scheme 5-1の「11:」の処理は、図１５のScheme 5-5の処理を行うことにより実現することができる。
【００７２】
以下、図１１及び図１２のScheme 5-2について説明する。
【００７３】
Scheme 5-2の「1:」において、第１装置、第２装置及び第３装置は、{→ki,0}Z_2,{→ki,1}Z_2,…,{→ki,L-1}Z_2を(2,2)加法的秘密分散値[→ki,0]Z_2,01,[→ki,1]Z_2,01,…,[→ki,L-1]Z_2,01に変換する処理を行う（Scheme 5-2の「1:」）。
【００７４】
Scheme 5-2の「2:」において、第１装置、第２装置及び第３装置は、[→ki,0]Z_2,01,[→ki,1]Z_2,01…,[→ki,L-1]Z_2,01に{σi-1-1}を逆適用し、[→b0]Z_2,20:=[σi-1ki,0]Z_2,20,[→b1]Z_2,20:=[σi-1ki,1]Z_2,20,…,[→bL-1]Z_2,20:=[σi-1ki,L-1]Z_2,20を得る処理を行う（Scheme 5-2の「2:」）。
【００７５】
Scheme 5-2の「3:」において、第１装置、第２装置及び第３装置は、mod 2 → mod q変換により、[→b0]Z_2,20,[→b1]Z_2,20,…,[→bL-1]Z_2,20を[[→b0]]Z_q,[[→b1]]Z_q,…,[→bL-1]Z_qに変換する処理を行う（Scheme 5-2の「3:」）。
【００７６】
Scheme 5-2の「4:」から「7:」において、第１装置、第２装置及び第３装置は、η<┌log L┐を満たす正の整数ηと、D⊆ZLかつ2η+1≦|D|≦min(2η+1,L)を満たすDとの組のそれぞれに対して、[[KD]]:=[[Πw∈D→k0,w]]Z_qを計算する処理を行う（Scheme 5-2の「4:」から「7:」）。
【００７７】
Scheme 5-2の「8:」から「10:」において、第１装置、第２装置及び第３装置は、j<2Lの各jに対して、[[→fj]]Z_q:=Πj<L[[→k'i,w]]を求める処理を行う（Scheme 5-2の「8:」から「10:」）。ここで、jのビット表現のwビット目をjwとして、→k'i,wは、jw=0の場合には→k'i,w=1-→ki,w、jw=1の場合には→k'i,w=→ki,wとする。
【００７８】
Scheme 5-2の「11:」において、第１装置、第２装置及び第３装置は、 [[(→f'j)u]]Z_q:=Σ0≦t<u[[(→fj)t]]Z_q+[[sj]]Z_qを計算する処理を行う（Scheme 5-2の「11:」）。
【００７９】
Scheme 5-2の「12:」において、第１装置、第２装置及び第３装置は、(2,2)出力積和により、[σ'-1]Z_q,20:=Σ0≦j<2^L[→f'j→fj]Z_q,20を計算する処理を行う（Scheme 5-2の「11:」）。
【００８０】
Scheme 5-2の「13:」において、第１装置、第２装置及び第３装置は、[σ-1]Z_q,20に{σi-1-1}を適用し、[σ-1]Z_q,01:= [σi-1-1σ'-1]Z_q,01を得る処理を行う（Scheme 5-2の「13:」）。
【００８１】
Scheme 5-2の「14:」において、第１装置、第２装置及び第３装置は、<πσi-1>20:={π}01,12[σ-1]Z_q,01を計算する処理を行う（Scheme 5-2の「14:」）。なお、Scheme 5-2の「14:」の処理は、図１５のScheme 5-5の処理を行うことにより実現することができる。
【００８２】
なお、L=2の場合には、Scheme 5-1及びScheme 5-2は、それぞれ図１６及び図１７，図１８に記載されたScheme 5-1及びScheme 5-2となる。
【００８３】
このように、逆置換を用いることで従来よりも秘匿ソートのアルゴリズムをシンプルにすることができる。これにより、従来よりも速い速度で秘匿ソートを行うことができる。
【００８４】
［変形例］
以下に述べるように通信路利用の最適化を行ってもよい。言い換えれば、空いた通信路ができる限りなくなるように通信路を有効活用してもよい。
【００８５】
例えば、図１６及び図１７，図１８のScheme 5-1及びScheme 5-2における、「3:」のmod 2 to mod qの処理、「4:」の乗算の処理、「7:」の(2,2)出力積和の処理には通信の方向に自由度がある。これらの処理を、空いた通信路ができる限りなくなるように通信路を有効活用して行ってもよい。
【００８６】
L'がLの倍数でないときは、NL+L''=L'となるように長さL'のキーを分割してもよい。また、Σi=0N-1Li=L'となるように長さL'のキーを分割してもよい。この場合、例えば、→knは、Σi=0N-1Li=L'となるように長さL'のキーを分割したときのn+1(n=0,…,N-1)番目のビット列から構成されるベクトルとなる。このように、Nを所定の正の整数とし、キーをN個のビット列に分割したときのn+1(n=0,…,N-1)番目のビット列を→knとしてもよい。
【００８７】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００８８】
［プログラム及び記録媒体］
例えば、各装置における処理をコンピュータによって実現する場合、各装置の各部が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各装置の処理がコンピュータ上で実現される。
【００８９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９０】
また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019074044.tif 000003
【図２】
2019074044.tif 000004
【図３】
2019074044.tif 000005
【図４】
2019074044.tif 000006
【図５】
2019074044.tif 000007
【図６】
2019074044.tif 000008
【図７】
2019074044.tif 000009
【図８】
2019074044.tif 000010
【図９】
2019074044.tif 000011
【図１０】
2019074044.tif 000012
【図１１】
2019074044.tif 000013
【図１２】
2019074044.tif 000014
【図１３】
2019074044.tif 000015
【図１４】
2019074044.tif 000016
【図１５】
2019074044.tif 000017
【図１６】
2019074044.tif 000018
【図１７】
2019074044.tif 000019
【図１８】
2019074044.tif 000020
【国際調査報告】
2019074044.tif 000021
2019074044.tif 000022
2019074044.tif 000023
2019074044.tif 000024