(57)【特許請求の範囲】
【請求項１】
Ｎは３以上の整数とし、暗号化装置とＮ個の秘密計算装置とを含む秘密計算システムであって、
前記暗号化装置は、
ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化し、Ｎ個の暗号行列を生成する暗号行列生成部と、
ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、Ｎ個の暗号入力ベクトルを生成する暗号入力ベクトル生成部と、
ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化し、Ｎ個の暗号目印ベクトルを生成する暗号目印ベクトル生成部と、
ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の前記暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成する像ベクトル生成部と、
ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成する更新済ベクトル生成部と、
Ｎ個の前記暗号行列の１列目からなる列ベクトル、Ｎ個の前記暗号入力ベクトル、Ｎ個の前記暗号目印ベクトル、Ｎ個の前記像ベクトル及びＮ個の前記更新済ベクトルをそれぞれＮ個の秘密計算装置に配布する送信部と、を含み、
各前記秘密計算装置は、
秘密計算により前記暗号行列の１列目からなる列ベクトルの各要素に２を乗じた列ベクトルと、秘密計算により前記暗号入力ベクトルの各要素に２を乗じたものに１を足した列ベクトルとを垂直に連結したソート用キーベクトルと、前記暗号目印ベクトル、前記像ベクトル及び前記更新済ベクトルを水平に連結した行列を、前記ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソート部と、
入力データの個数に１を足した値の対数値以上の最小の整数を反復回数ｔとし、ｕ［ｐ…ｑ］を列ベクトルｕのｐ＋１行目からｑ行目までとし、Ａ||ＢはＡとＢとの論理和を表し、ｉは１以上ｔ以下の整数であり、ｉ＝１からｉ＝ｔまで
d=2i-1
[[ci]][0…d]=[[ci-1]][0…d]
[[ai]][0…d]=[[ai-1]][0…d]
[[ci]][d…(m+n)]=[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]
[[ai]][d…(m+n)]
=[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])を秘密計算する反復計算部と、
前記暗号目印ベクトルと反復計算後の前記像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換部と、
当該秘密計算装置が保管する前記暗号目印ベクトルと他の秘密計算装置が保管する前記暗号目印ベクトルとから前記目印ベクトルを復号する目印ベクトル復号部と、
目印ベクトルの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトルの要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替え部と、を含む、
秘密計算システム。
【請求項２】
Ｎは３以上の整数とし、ある数値から秘密計算可能な暗号文であるＮ個の断片を生成する暗号化装置であって、
ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化し、Ｎ個の暗号行列を生成する暗号行列生成部と、
ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、Ｎ個の暗号入力ベクトルを生成する暗号入力ベクトル生成部と、
ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化し、Ｎ個の暗号目印ベクトルを生成する暗号目印ベクトル生成部と、
ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の前記暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成する像ベクトル生成部と、
ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成する更新済ベクトル生成部と、
Ｎ個の前記暗号行列の１列目からなる列ベクトル、Ｎ個の前記暗号入力ベクトル、Ｎ個の前記暗号目印ベクトル、Ｎ個の前記像ベクトル及びＮ個の前記更新済ベクトルをそれぞれＮ個の秘密計算装置に配布する送信部と、を含む、
暗号化装置。
【請求項３】
ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化したものを暗号行列とし、ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化したものを暗号入力ベクトルとし、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化したものを暗号目印ベクトルとし、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、前記暗号行列の２列目と暗号列ベクトル[[０ｎ]]とを垂直に連結したものを像ベクトル[[ａ０]]とし、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、暗号ベクトル[[１ｍ]]と暗号列ベクトル[[０ｎ]]とを垂直に連結したものを更新済ベクトル[[ｃ０]]とし、
秘密計算により前記暗号行列の１列目からなる列ベクトルの各要素に２を乗じた列ベクトルと、秘密計算により前記暗号入力ベクトルの各要素に２を乗じたものに１を足した列ベクトルとを垂直に連結したソート用キーベクトルと、前記暗号目印ベクトル、前記像ベクトル及び前記更新済ベクトルを水平に連結した行列を、前記ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソート部と、
入力データの個数に１を足した値の対数値以上の最小の整数を反復回数ｔとし、ｕ［ｐ…ｑ］を列ベクトルｕのｐ＋１行目からｑ行目までとし、Ａ||ＢはＡとＢとの論理和を表し、ｉは１以上ｔ以下の整数であり、ｉ＝１からｉ＝ｔまで
d=2i-1
[[ci]][0…d]=[[ci-1]][0…d]
[[ai]][0…d]=[[ai-1]][0…d]
[[ci]][d…(m+n)]=[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]
[[ai]][d…(m+n)]
=[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])を秘密計算する反復計算部と、
前記暗号目印ベクトルと反復計算後の前記像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換部と、
当該秘密計算装置が保管する前記暗号目印ベクトルと他の秘密計算装置が保管する前記暗号目印ベクトルとから前記目印ベクトルを復号する目印ベクトル復号部と、
目印ベクトルの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトルの要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替え部と、を含む、
秘密計算装置。
【請求項４】
Ｎは３以上の整数とし、暗号化装置とＮ個の秘密計算装置とを用いる秘密計算方法であって、
ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、前記暗号化装置の暗号行列生成部が、写像を表現する行列Ｔの各要素を暗号化し、Ｎ個の暗号行列を生成する暗号行列生成ステップと、
ｎを入力データの個数とし、前記暗号化装置の暗号入力ベクトル生成部が、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、Ｎ個の暗号入力ベクトルを生成する暗号入力ベクトル生成ステップと、
前記暗号化装置の暗号目印ベクトル生成部が、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化し、Ｎ個の暗号目印ベクトルを生成する暗号目印ベクトル生成ステップと、
前記暗号化装置の像ベクトル生成部が、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の前記暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成する像ベクトル生成ステップと、
前記暗号化装置の更新済ベクトル生成部が、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成する更新済ベクトル生成ステップと、
前記暗号化装置の送信部が、Ｎ個の前記暗号行列の１列目からなる列ベクトル、Ｎ個の前記暗号入力ベクトル、Ｎ個の前記暗号目印ベクトル、Ｎ個の前記像ベクトル及びＮ個の前記更新済ベクトルをそれぞれＮ個の秘密計算装置に配布する送信ステップと、
各前記秘密計算装置のソート部が、秘密計算により前記暗号行列の１列目からなる列ベクトルの各要素に２を乗じた列ベクトルと、秘密計算により前記暗号入力ベクトルの各要素に２を乗じたものに１を足した列ベクトルとを垂直に連結したソート用キーベクトルと、前記暗号目印ベクトル、前記像ベクトル及び前記更新済ベクトルを水平に連結した行列を、前記ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソートステップと、
入力データの個数に１を足した値の対数値以上の最小の整数を反復回数ｔとし、ｕ［ｐ…ｑ］を列ベクトルｕのｐ＋１行目からｑ行目までとし、Ａ||ＢはＡとＢとの論理和を表し、ｉは１以上ｔ以下の整数であり、各前記秘密計算装置の反復計算部が、ｉ＝１からｉ＝ｔまで
d=2i-1
[[ci]][0…d]=[[ci-1]][0…d]
[[ai]][0…d]=[[ai-1]][0…d]
[[ci]][d…(m+n)]=[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]
[[ai]][d…(m+n)]
=[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])を秘密計算する反復計算ステップと、
各前記秘密計算装置のランダム置換部が、前記暗号目印ベクトルと反復計算後の前記像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換ステップと、
各前記秘密計算装置の目印ベクトル復号部が、当該秘密計算装置が保管する前記暗号目印ベクトルと他の秘密計算装置が保管する前記暗号目印ベクトルとから前記目印ベクトルを復号する目印ベクトル復号ステップと、
各前記秘密計算装置の並び替え部が、目印ベクトルの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトルの要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替えステップと、を含む、
秘密計算方法。
【請求項５】
Ｎは３以上の整数とし、ある数値から秘密計算可能な暗号文であるＮ個の断片を生成する暗号化方法であって、
ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、暗号行列生成部が、写像を表現する行列Ｔの各要素を暗号化し、Ｎ個の暗号行列を生成する暗号行列生成ステップと、
ｎを入力データの個数とし、暗号入力ベクトル生成部が、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、Ｎ個の暗号入力ベクトルを生成する暗号入力ベクトル生成ステップと、
暗号目印ベクトル生成部が、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化し、Ｎ個の暗号目印ベクトルを生成する暗号目印ベクトル生成ステップと、
像ベクトル生成部が、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の前記暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成する像ベクトル生成ステップと、
更新済ベクトル生成部が、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成する更新済ベクトル生成ステップと、
送信部が、Ｎ個の前記暗号行列の１列目からなる列ベクトル、Ｎ個の前記暗号入力ベクトル、Ｎ個の前記暗号目印ベクトル、Ｎ個の前記像ベクトル及びＮ個の前記更新済ベクトルをそれぞれＮ個の秘密計算方法に配布する送信ステップと、を含む、
暗号化方法。
【請求項６】
ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化したものを暗号行列とし、ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化したものを暗号入力ベクトルとし、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化したものを暗号目印ベクトルとし、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、前記暗号行列の２列目と暗号列ベクトル[[０ｎ]]とを垂直に連結したものを像ベクトル[[ａ０]]とし、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、暗号ベクトル[[１ｍ]]と暗号列ベクトル[[０ｎ]]とを垂直に連結したものを更新済ベクトル[[ｃ０]]とし、
ソート部が、秘密計算により前記暗号行列の１列目からなる列ベクトルの各要素に２を乗じた列ベクトルと、秘密計算により前記暗号入力ベクトルの各要素に２を乗じたものに１を足した列ベクトルとを垂直に連結したソート用キーベクトルと、前記暗号目印ベクトル、前記像ベクトル及び前記更新済ベクトルを水平に連結した行列を、前記ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソートステップと、
入力データの個数に１を足した値の対数値以上の最小の整数を反復回数ｔとし、ｕ［ｐ…ｑ］を列ベクトルｕのｐ＋１行目からｑ行目までとし、Ａ||ＢはＡとＢとの論理和を表し、ｉは１以上ｔ以下の整数であり、反復計算部が、ｉ＝１からｉ＝ｔまで
d=2i-1
[[ci]][0…d]=[[ci-1]][0…d]
[[ai]][0…d]=[[ai-1]][0…d]
[[ci]][d…(m+n)]=[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]
[[ai]][d…(m+n)]
=[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])を秘密計算する反復計算ステップと、
ランダム置換部が、前記暗号目印ベクトルと反復計算後の前記像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換ステップと、
目印ベクトル復号部が、当該秘密計算方法を実施する秘密計算装置が保管する前記暗号目印ベクトルと他の秘密計算装置が保管する前記暗号目印ベクトルとから前記目印ベクトルを復号する目印ベクトル復号ステップと、
並び替え部が、目印ベクトルの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトルの要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替えステップと、を含む、
秘密計算方法。
【請求項７】
請求項２記載の暗号化装置、または、請求項３記載の秘密計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関するものであり、特に三個以上の秘密計算装置に入力データの断片（暗号文）を送り、各秘密計算装置において復号せずに、入力データを明かすことなく断片のまま計算を行う秘密計算技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元せずに演算結果を得る方法として、秘密計算と呼ばれる方法がある。非特許文献１が秘密計算の従来技術として知られている。非特許文献１では、三個の秘密計算装置に数値の断片を分散させるという暗号化を行い、数値を復元せずに、加減算、定数和、乗算、定数倍、論理演算(否定、論理積、論理和、排他的論理和)及びデータ形式変換(整数、二進数)の結果を三個の秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】千田浩司、濱田浩気、五十嵐大、高橋克巳、「軽量検証可能３パーティ秘匿関数計算の再考」、情報処理学会シンポジウム論文集、２０１０年、巻：２０１０、号：９、頁：５５５−５６０
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術は、暗号化された数値を復元せずに写像を計算し、その結果を得る方法（以下、「秘密写像」という）について何ら開示していない。仮に秘密写像を実現しようとすると、以下の方法が考えられる。
【０００５】
定義域及び値域に含まれる全ての元を暗号化しておき、定義域に含まれる各元の断片（暗号文）と入力データの断片とを比較し、一致する元の断片における写像の像を求める必要がある。そのため一つの入力データに対して定義域の大きさｍに比例した計算時間Ｏ（ｍ）がかかる。暗号化されたｎ個の入力データに対して秘密写像を計算する場合、Ｏ（ｍｎ）の計算時間が必要となる。
【０００６】
本発明は、暗号化されたｎ個の入力データに対して計算時間がＯ（（ｍ＋ｎ）ｌｏｇｎ）で秘密写像を計算できる秘密計算装置、そのための暗号化装置、暗号化装置と秘密計算装置とからなる秘密システム及びその方法、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、本発明の第一の態様によれば、Ｎは３以上の整数とし、秘密計算システム、暗号化装置とＮ個の秘密計算装置とを含む。暗号化装置は、ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化し、Ｎ個の暗号行列を生成する暗号行列生成部と、ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、Ｎ個の暗号入力ベクトルを生成する暗号入力ベクトル生成部と、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化し、Ｎ個の暗号目印ベクトルを生成する暗号目印ベクトル生成部と、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成する像ベクトル生成部と、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成する更新済ベクトル生成部と、Ｎ個の暗号行列の１列目からなる列ベクトル、Ｎ個の暗号入力ベクトル、Ｎ個の暗号目印ベクトル、Ｎ個の像ベクトル及びＮ個の更新済ベクトルをそれぞれＮ個の秘密計算装置に配布する送信部と、を含む。各秘密計算装置は、秘密計算により暗号行列の１列目からなる列ベクトルの各要素に２を乗じた列ベクトルと、秘密計算により暗号入力ベクトルの各要素に２を乗じたものに１を足した列ベクトルとを垂直に連結したソート用キーベクトルと、暗号目印ベクトル、像ベクトル及び更新済ベクトルを水平に連結した行列を、ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソート部と、入力データの個数に１を足した値の対数値以上の最小の整数を反復回数ｔとし、ｕ［ｐ…ｑ］を列ベクトルｕのｐ＋１行目からｑ行目までとし、Ａ||ＢはＡとＢとの論理和を表し、ｉは１以上ｔ以下の整数であり、ｉ＝１からｉ＝ｔまで
d=2i-1
[[ci]][0…d]=[[ci-1]][0…d]
[[ai]][0…d]=[[ai-1]][0…d]
[[ci]][d…(m+n)]=[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]
[[ai]][d…(m+n)]
=[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])
を秘密計算する反復計算部と、暗号目印ベクトルと反復計算後の像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換部と、その秘密計算装置が保管する暗号目印ベクトルと他の秘密計算装置が保管する暗号目印ベクトルとから目印ベクトルを復号する目印ベクトル復号部と、目印ベクトルの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトルの要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替え部と、を含む。
【０００８】
上記の課題を解決するために、本発明の第二の態様によれば、Ｎは３以上の整数とし、暗号化装置は、ある数値から秘密計算可能な暗号文であるＮ個の断片を生成する。暗号化装置は、ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化し、Ｎ個の暗号行列を生成する暗号行列生成部と、ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、Ｎ個の暗号入力ベクトルを生成する暗号入力ベクトル生成部と、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化し、Ｎ個の暗号目印ベクトルを生成する暗号目印ベクトル生成部と、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成する像ベクトル生成部と、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成する更新済ベクトル生成部と、Ｎ個の暗号行列の１列目からなる列ベクトル、Ｎ個の暗号入力ベクトル、Ｎ個の暗号目印ベクトル、Ｎ個の像ベクトル及びＮ個の更新済ベクトルをそれぞれＮ個の秘密計算装置に配布する送信部と、を含む。
【０００９】
上記の課題を解決するために、本発明の第三の態様によれば、ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化したものを暗号行列とし、ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化したものを暗号入力ベクトルとし、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化したものを暗号目印ベクトルとし、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、暗号行列の２列目と暗号列ベクトル[[０ｎ]]とを垂直に連結したものを像ベクトル[[ａ０]]とし、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、暗号ベクトル[[１ｍ]]と暗号列ベクトル[[０ｎ]]とを垂直に連結したものを更新済ベクトル[[ｃ０]]とし、秘密計算装置は、秘密計算により暗号行列の１列目からなる列ベクトルの各要素に２を乗じた列ベクトルと、秘密計算により暗号入力ベクトルの各要素に２を乗じたものに１を足した列ベクトルとを垂直に連結したソート用キーベクトルと、暗号目印ベクトル、像ベクトル及び更新済ベクトルを水平に連結した行列を、ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソート部と、入力データの個数に１を足した値の対数値以上の最小の整数を反復回数ｔとし、ｕ［ｐ…ｑ］を列ベクトルｕのｐ＋１行目からｑ行目までとし、Ａ||ＢはＡとＢとの論理和を表し、ｉは１以上ｔ以下の整数であり、ｉ＝１からｉ＝ｔまで
d=2i-1
[[ci]][0…d]=[[ci-1]][0…d]
[[ai]][0…d]=[[ai-1]][0…d]
[[ci]][d…(m+n)]=[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]
[[ai]][d…(m+n)]
=[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])
を秘密計算する反復計算部と、暗号目印ベクトルと反復計算後の像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換部と、その秘密計算装置が保管する暗号目印ベクトルと他の秘密計算装置が保管する暗号目印ベクトルとから目印ベクトルを復号する目印ベクトル復号部と、目印ベクトルの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトルの要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替え部と、を含む。
【００１０】
上記の課題を解決するために、本発明の第四の態様によれば、Ｎは３以上の整数とし、秘密計算方法は、暗号化装置とＮ個の秘密計算装置とを用いる。秘密計算方法は、ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、暗号化装置が、写像を表現する行列Ｔの各要素を暗号化し、Ｎ個の暗号行列を生成する暗号行列生成ステップと、ｎを入力データの個数とし、暗号化装置が、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、Ｎ個の暗号入力ベクトルを生成する暗号入力ベクトル生成ステップと、暗号化装置が、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化し、Ｎ個の暗号目印ベクトルを生成する暗号目印ベクトル生成ステップと、暗号化装置が、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成する像ベクトル生成ステップと、暗号化装置が、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成する更新済ベクトル生成ステップと、暗号化装置が、Ｎ個の暗号行列の１列目からなる列ベクトル、Ｎ個の暗号入力ベクトル、Ｎ個の暗号目印ベクトル、Ｎ個の像ベクトル及びＮ個の更新済ベクトルをそれぞれＮ個の秘密計算装置に配布する送信ステップと、秘密計算により暗号行列の１列目からなる列ベクトルの各要素に２を乗じた列ベクトルと、秘密計算により暗号入力ベクトルの各要素に２を乗じたものに１を足した列ベクトルとを垂直に連結したソート用キーベクトルを生成するソート用キーベクトル生成ステップと、各秘密計算装置が、ソート用キーベクトルと、暗号目印ベクトル、像ベクトル及び更新済ベクトルを水平に連結した行列を、ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソートステップと、入力データの個数に１を足した値の対数値以上の最小の整数を反復回数ｔとして算出するステップと、ｕ［ｐ…ｑ］を列ベクトルｕのｐ＋１行目からｑ行目までとし、Ａ||ＢはＡとＢとの論理和を表し、ｉは１以上ｔ以下の整数であり、各秘密計算装置が、ｉ＝１からｉ＝ｔまで
d=2i-1
[[ci]][0…d]=[[ci-1]][0…d]
[[ai]][0…d]=[[ai-1]][0…d]
[[ci]][d…(m+n)]=[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]
[[ai]][d…(m+n)]
=[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])
を秘密計算する反復計算ステップと、各秘密計算装置が、暗号目印ベクトルと反復計算後の像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換ステップと、各秘密計算装置が、その秘密計算装置が保管する暗号目印ベクトルと他の秘密計算装置が保管する暗号目印ベクトルとから目印ベクトルを復号する目印ベクトル復号ステップと、各秘密計算装置が、目印ベクトルの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトルの要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替えステップと、を含む。
【００１１】
上記の課題を解決するために、本発明の第五の態様によれば、Ｎは３以上の整数とし、暗号化方法は、ある数値から秘密計算可能な暗号文であるＮ個の断片を生成する。暗号化方法は、ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化し、Ｎ個の暗号行列を生成する暗号行列生成ステップと、ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、Ｎ個の暗号入力ベクトルを生成する暗号入力ベクトル生成ステップと、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化し、Ｎ個の暗号目印ベクトルを生成する暗号目印ベクトル生成ステップと、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成する像ベクトル生成ステップと、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成する更新済ベクトル生成ステップと、Ｎ個の暗号行列の１列目からなる列ベクトル、Ｎ個の暗号入力ベクトル、Ｎ個の暗号目印ベクトル、Ｎ個の像ベクトル及びＮ個の更新済ベクトルをそれぞれＮ個の秘密計算方法に配布する送信ステップと、を含む。
【００１２】
上記の課題を解決するために、本発明の第六の態様によれば、ｍ行２列の行列の各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Ｔの各要素を暗号化したものを暗号行列とし、ｎを入力データの個数とし、ｎ個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化したものを暗号入力ベクトルとし、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルの各要素を暗号化したものを暗号目印ベクトルとし、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、暗号行列の２列目と暗号列ベクトル[[０ｎ]]とを垂直に連結したものを像ベクトル[[ａ０]]とし、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、暗号ベクトル[[１ｍ]]と暗号列ベクトル[[０ｎ]]とを垂直に連結したものを更新済ベクトル[[ｃ０]]とし、秘密計算方法は、秘密計算により暗号行列の１列目からなる列ベクトルの各要素に２を乗じた列ベクトルと、秘密計算により暗号入力ベクトルの各要素に２を乗じたものに１を足した列ベクトルとを垂直に連結したソート用キーベクトルと、暗号目印ベクトル、像ベクトル及び更新済ベクトルを水平に連結した行列を、ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソートステップと、入力データの個数に１を足した値の対数値以上の最小の整数を反復回数ｔとし、ｕ［ｐ…ｑ］を列ベクトルｕのｐ＋１行目からｑ行目までとし、Ａ||ＢはＡとＢとの論理和を表し、ｉは１以上ｔ以下の整数であり、ｉ＝１からｉ＝ｔまで
d=2i-1
[[ci]][0…d]=[[ci-1]][0…d]
[[ai]][0…d]=[[ai-1]][0…d]
[[ci]][d…(m+n)]=[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]
[[ai]][d…(m+n)]
=[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])
を秘密計算する反復計算ステップと、暗号目印ベクトルと反復計算後の像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換ステップと、目印ベクトルを復号する目印ベクトル復号ステップと、目印ベクトルの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトルの要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替えステップと、を含む。
【発明の効果】
【００１３】
本発明に係る秘密計算方法によれば、定義域の大きさがｍであるとき、暗号化されたｎ個の入力データに対して計算時間がＯ（（ｍ＋ｎ）ｌｏｇｎ）で秘密写像を計算できるという効果を奏する。
【図面の簡単な説明】
【００１４】
【図１】秘密計算システムの構成例を示す図。
【図２】暗号化装置の機能ブロック図。
【図３】暗号化装置の初期設定時の処理フローを示す図。
【図４】暗号化装置の、入力データ取得時の処理フローを示す図。
【図５】秘密計算装置の機能ブロック図。
【図６】秘密計算装置の初期設定時の処理フローを示す図。
【図７】秘密計算装置の、暗号入力ベクトル受信時の処理フローを示す図。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。また、ベクトルや行列の各要素単位で行われる処理は、特に断りがない限り、そのベクトルやその行列の全ての要素に対して適用されるものとする。
【００１６】
＜第一実施形態に係る秘密計算システム１０＞
図１は秘密計算システム１０の構成例を示す。秘密計算システム１０は暗号化装置１１と通信回線１３と秘密計算装置１２−１，１２−２，…，１２−Ｎとを含む。ただし、Ｎは３以上の整数とする。通信回線１３は例えば電気事業者が提供する広域通信回線、ＶＰＮ（Virtual Private Network）またはＬＡＮ（Local Area Network）等からなり、秘密計算システム１０と各秘密計算装置１２−１，１２−２，…，１２−Ｎとの通信及び各秘密計算装置１２−１，１２−２，…，１２−Ｎ間の通信を可能としている。以下、各装置の詳細を説明する。
【００１７】
＜暗号化装置１１＞
図２は暗号化装置１１の機能ブロック図を、図３は暗号化装置１１の初期設定時の処理フローを、図４は暗号化装置１１の入力データ受信時の処理フローを示す。
【００１８】
暗号化装置１１は、暗号行列生成部１１１、暗号入力ベクトル生成部１１２、暗号目印ベクトル生成部１１３、像ベクトル生成部１１４、更新済ベクトル生成部１１５、送信部１１６及び記憶部１１７を含む。
【００１９】
暗号化装置１１は、写像を表現するｍ行２列の行列Ｔ及びｎ個の入力データを入力とし、記憶部１１７に格納する。この入力を用いて、Ｎ個の暗号行列の１列目からなるＮ個の列ベクトル、Ｎ個の暗号入力ベクトル、Ｎ個の暗号目印ベクトル、Ｎ個の像ベクトル及びＮ個の更新済ベクトルを生成し、それぞれＮ個の秘密計算装置に出力する。なお、行列Ｔ及び各ベクトルの詳細は後述する。
【００２０】
暗号化装置１１内の各部（暗号行列生成部１１１、暗号入力ベクトル生成部１１２、暗号目印ベクトル生成部１１３、像ベクトル生成部１１４及び更新済ベクトル生成部１１５）では暗号化が行われる。その暗号化の方法としては例えば参考文献１記載の方法がある。
（参考文献１）SecureSCM. Security analysis. Deliverable D9.2, SecureSCM Project, 2009
【００２１】
例えば数値Ａから暗号文であるＮ個の断片[[Ａ]]が生成される。この場合において、Ｎ個の断片[[Ａ]]のうちのＮ’個の断片[[Ａ]]がなければ数値Ａを復元することはできない。ただし、Ｎ’は、２以上Ｎ以下の整数である。Ｎ及びＮ’の値は、暗号化の方式により異なる。なおＮ個の断片[[Ａ]]はそれぞれ異なる値であるが、便宜上全ての断片を[[Ａ]]と表記する。
【００２２】
[暗号行列生成部１１１]
ベクトルＶ及び行列Ｍの各要素を暗号化した際に得られるＮ個の暗号ベクトル及び暗号行列をそれぞれ[[Ｖ]]、[[Ｍ]]と記載する。暗号行列生成部１１１は、写像を表現する行列Ｔを与えられ、行列Ｔの各要素を暗号化し、Ｎ個の暗号行列[[Ｔ]]を生成し（ｓ１１）、記憶部１１７に格納する。なお、ｍ行２列の行列Ｔの１列目に含まれる要素を元とする集合（定義域）から行列Ｔの２列目に含まれる要素を元とする集合（値域）への写像であって、行列Ｔの各行の１列目の要素に対して同じ行の２列目の要素を指定する写像を、行列Ｔが表現する写像と呼ぶ。行列Ｔの１列目からなる列ベクトルをｘとし、２列目からなる列ベクトルをｙとする。よって、
【００２３】
【数１】
0005689826.tif 000002
【００２４】
である。ただし「Ｔ」は転置を表す。
【００２５】
[暗号目印ベクトル生成部１１３]
暗号目印ベクトル生成部１１３は、ｍ個の数値０と、数値１，２，…，ｎとからなる列ベクトルである目印ベクトルｈの各要素を暗号化し、Ｎ個の暗号目印ベクトル[[ｈ]]を生成し（ｓ１３）、記憶部１１７に格納する。
【００２６】
【数２】
0005689826.tif 000003
【００２７】
[像ベクトル生成部１１４]
像ベクトル生成部１１４は、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号行列の２列目とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の像ベクトル[[ａ０]]を生成し（ｓ１５）、記憶部１１７に格納する。
【００２８】
【数３】
0005689826.tif 000004
【００２９】
[更新済ベクトル生成部１１５]
更新済ベクトル生成部１１５は、ｍ個の数値１からなる列ベクトル１ｍを暗号化し、ｎ個の数値０からなる列ベクトル０ｎを暗号化し、Ｎ個の暗号ベクトル[[１ｍ]]とＮ個の暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したＮ個の更新済ベクトル[[ｃ０]]を生成し（ｓ１７）、記憶部１１７に格納する。
【００３０】
【数４】
0005689826.tif 000005
【００３１】
送信部１１６は、Ｎ個の暗号行列の１列目からなるＮ個の列ベクトル[[ｘ]]、Ｎ個の暗号目印ベクトル[[ｈ]]、Ｎ個の像ベクトル[[ａ０]]及びＮ個の更新済ベクトル[[ｃ０]]が生成されると、これらのベクトルを記憶部１１７から取り出し、それぞれＮ個の秘密計算装置に送信し、配布する（ｓ１９）。
【００３２】
[暗号入力ベクトル生成部１１２]
暗号入力ベクトル生成部１１２は、ｎ個の入力データを入力されると（ｓ２１）、ｎ個の要素を持つ列ベクトルである入力ベクトルｋの各要素を暗号化し、Ｎ個の暗号入力ベクトル[[ｋ]]を生成し（ｓ２３）、記憶部１１７に格納する。
【００３３】
【数５】
0005689826.tif 000006
【００３４】
送信部１１６は、Ｎ個の暗号入力ベクトルが生成されると、記憶部１１７から取り出し、それぞれＮ個の秘密計算装置に送信し、配布する（ｓ２５）。
【００３５】
なお、本実施形態では予め入力データの個数をｎと定めておき、その大きさに対する各種ベクトルを生成している。入力データの個数がｎ以下の場合にはブランクを表す記号を不足分だけ入力して各種ベクトルを生成し、入力データの個数がｎ以上の場合には入力データをｎ個づつのブロックに分割して、ブロック毎に各種ベクトルを生成する。
【００３６】
ｎを予め定めず、入力データを入力された時点において、ｎを決定してもよい。その場合には、各種ベクトルを入力データ入力後に生成する構成となる。この構成の場合には、ブランクを表す記号を入力したり、入力データを分割する処理を省くことができ、一回の送信で全てのベクトルを送信できるというメリットがある。本実施形態の場合には入力データが入力された後は暗号入力ベクトルのみを生成し、送信するため、応答時間が早いが、ｎを予め定めない場合には入力データが入力された後で各種ベクトルを生成するため応答時間が長くなるというデメリットがある。
【００３７】
＜秘密計算装置１２−１＞
図５は秘密計算装置１２−１の機能ブロック図を、図６はその初期設定時の処理フローを、図７はその暗号入力ベクトル受信時の処理フローを示す。なお、他の秘密計算装置１２−２，１２−３，…，１２−Ｎにおいても同様の機能構成を有し、同様の処理を行う。
【００３８】
秘密計算装置１２−１は、ソート用キーベクトル生成部１２１、ソート部１２２、反復計算部１２３、ランダム置換部１２４、目印ベクトル復号部１２５、並び替え部１２６、送受信部１２７及び記憶部１２８を含む。
【００３９】
秘密計算装置１２−１は、まず送受信部１２７を介して暗号行列[[Ｔ]]の１列目からなる列ベクトル[[ｘ]]、暗号目印ベクトル[[ｈ]]、像ベクトル[[ａ０]]及び更新済ベクトル[[ｃ０]]を受信し、記憶部１２８に格納する（図６のｓ３１）。次に送受信部１２７を介して暗号入力ベクトル[[ｋ]]を受信し、記憶部１２８に格納する（図７のｓ３３）。秘密計算装置１２−１は、これらのベクトルを用いて、入力ベクトルｋを復元せずに、入力ベクトルｋの各要素に行列Ｔが表現する写像を適用した大きさｎの出力ベクトルｖの暗号文[[ｖ]]を計算し、計算結果を暗号化したまま記憶部１２８に保持する。以下、各部の処理内容を説明する。
【００４０】
[ソート用キーベクトル生成部１２１]
ソート用キーベクトル生成部１２１は、暗号行列[[Ｔ]]の１列目からなる列ベクトル[[ｘ]]を受信すると、これを記憶部１２８から取り出し、秘密計算により暗号行列[[Ｔ]]の１列目からなる列ベクトル[[ｘ]]の各要素に２を乗じた列ベクトル２・[[ｘ]]を生成し、記憶部１２８に格納する（図６のｓ３２）。
【００４１】
【数６】
0005689826.tif 000007
【００４２】
さらに、ソート用キーベクトル生成部１２１は、暗号入力ベクトル[[ｋ]]を受信すると、これを記憶部１２８から取り出し、秘密計算により暗号入力ベクトル[[ｋ]]の各要素に２を乗じたものに１を足した列ベクトル（２・[[ｋ]]＋１ｎ）を生成し、記憶部１２８に格納する。
【００４３】
【数７】
0005689826.tif 000008
【００４４】
なお、１ｎはｎ個の数値１を要素として持つ列ベクトルを表す。秘密計算により加算、乗算を行う方法として既存技術を利用することができる（例えば参考文献１参照）。
【００４５】
さらに、ソート用キーベクトル生成部１２１は、列ベクトル２・[[ｘ]]と（２・[[ｋ]]＋１ｎ）とを垂直に連結したソート用キーベクトル[[ｅ]]を生成し（ｓ３５）、記憶部１２８に格納する。
【００４６】
【数８】
0005689826.tif 000009
【００４７】
[ソート部１２２]
ソート部１２２は、暗号目印ベクトル[[ｈ]]、像ベクトル[[ａ０]]、更新済ベクトル[[ｃ０]]及びソート用キーベクトル[[ｅ]]を記憶部１２８から取り出し、これらのベクトルを水平に連結した行列
【００４８】
【数９】
0005689826.tif 000010
【００４９】
を（式（６）、（７）、（８）、（１３）参照）、ソート用キーベクトル[[ｅ]]の各要素の大小関係に応じて行毎に秘密計算によりソートし（ｓ３７）、ソート後の暗号目印ベクトル[[ｈ]]、像ベクトル[[ａ０]]及び更新済ベクトル[[ｃ０]]を記憶部１２８に格納する。なお、秘密計算によりソートを行う方法として既存技術を利用することができる（例えば参考文献２参照）。
（参考文献２参照）濱田浩気、五十嵐大、千田浩司、高橋克巳、「秘匿関数計算上の線形時間ソート」、ＳＣＩＳ、２０１１年、pp.1-7
【００５０】
本実施形態で用いるソートは、秘匿関数計算でソートを行う暗号文の組[[Ｘ]]の平文Ｘの行を指定した列の値に従って整列した平文Ｙの各要素を暗号化した暗号文[[Ｙ]]を計算し、[[Ｘ]]と[[Ｙ]]の各要素の対応が誰にもわからないように計算することができるものであればよい。
【００５１】
[反復計算部１２３]
反復計算部１２３は、暗号化入力ベクトルの要素の個数に１を足した値の対数値以上の最小の整数を算出し（ｓ３８）、この値を反復回数ｔとする。
【００５２】
【数１０】
0005689826.tif 000011
【００５３】
ただし、ｃｅｉｌ（・）は、天井関数を表し、・以上の最小の整数を表す。
【００５４】
反復計算部１２３は、記憶部１２８からソート後の像ベクトル[[ａ０]]及び更新済ベクトル[[ｃ０]]を取り出し、ｉ＝１からｉ＝ｔまで
d←2i-1    (16)
[[ci]][0…d]←[[ci-1]][0…d]    (17)
[[ai]][0…d]←[[ai-1]][0…d]    (18)
[[ci]][d…(m+n)]←[[ci-1]][d…(m+n)]||[[ci-1]][0…(m+n-d)]    (19)
[[ai]][d…(m+n)]
←[[ai-1]][d…(m+n)]+[[ai-1]][0…(m+n-d)]×([[ci]][d…(m+n)]-[[ci-1]][d…(m+n)])
(20)
を秘密計算により求め（ｓ３９〜ｓ４５）、[[ａｔ]]を記憶部１２８に格納する。ただし、ｕ［ｐ…ｑ］は列ベクトルｕのｐ＋１行目からｑ行目までを、Ａ||ＢはＡとＢとの論理和を、ｉは１以上ｔ以下の整数を表し、要素毎に代入、論理和、乗算、加算を行うものとする。なお、秘密計算により論理和を求める方法として既存技術を利用することができる（例えば参考文献１参照）。
【００５５】
[ランダム置換部１２４]
ランダム置換部１２４は、暗号目印ベクトル[[ｈ]]と反復計算後の像ベクトル[[ａｔ]]とを記憶部１２８から取り出し、この組合せを行毎に秘密計算によりランダム置換し（ｓ４７）、置換後の暗号目印ベクトル[[ｈ]]と像ベクトル[[ａｔ]]とを記憶部１２８に格納する。なお、秘密計算によりランダム置換を行う方法として既存技術を利用することができる（参考文献３参照）。
（参考文献３参照）濱田浩気、五十嵐大、千田浩司、高橋克巳、「３パーティ秘匿関数計算上のランダム置換プロトコル」、情報処理学会シンポジウム論文集、２０１０年、巻:２０１０、号:９、頁:561-566
【００５６】
本実施形態におけるランダム置換は、秘匿関数計算でランダム置換を行う暗号文の組[[Ｘ]]の平文Ｘの行をランダムに置換した平文Ｙの各要素を暗号化した暗号文[[Ｙ]]を計算し、[[Ｘ]]と[[Ｙ]]の各要素の対応が誰にも分からないように計算するものであればよい。
【００５７】
[目印ベクトル復号部１２５]
目印ベクトル復号部１２５は、送受信部１２７を介して、少なくとも他の（Ｎ’−１）個の秘密計算装置に対して、その秘密計算装置が保管する暗号目印ベクトル[[ｈ]]を送信するように要求する。目印ベクトル復号部１２５は、他の秘密計算装置から（Ｎ’−１）個の暗号目印ベクトル[[ｈ]]を受信すると、当該秘密計算装置が保管する暗号目印ベクトル[[ｈ]]と併せて、Ｎ’個の暗号目印ベクトル[[ｈ]]から、元の目印ベクトルｈを復号し（ｓ４９）、復号後の目印ベクトルｈと置換後の像ベクトル[[ａｔ]]とを、行の関係を変えずに記憶部１２８に格納する。なお、この場合における復号方法は暗号化装置１１において行われた暗号化に対応するものであればよい（例えば参考文献１参照）。
【００５８】
[並び替え部１２６]
並び替え部１２６は、復元した目印ベクトルｈの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトル[[ａｔ]]の要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトル[[ｖ]]として求め（ｓ５１）、記憶部１２８に格納する。このようにして求めた暗号出力ベクトル[[ｖ]]は、入力ベクトルｋに行列Ｔの表現する写像を適用した結果を示す出力ベクトルｖを暗号化したものとなる。よって、暗号入力ベクトル[[ｋ]]を復元せずに行列Ｔの表現する写像を計算し、その結果を得ることができる。
【００５９】
＜効果＞
ある領域内に配置された値をどこから読み出したかを秘匿したまま読み出すという計算（以下「秘匿読み込み」という）を、従来技術において実現しようとすると、一つの入力データに対して秘匿読み込みを一度行う必要がある。そのため、領域内に配置された全ての値を読み込んだ「ふり」をするために領域の大きさｍに比例した時間がかかってしまう。本実施形態は、秘匿読み込みを大量の入力データに対して一度行うことにより効率化したものである。本実施形態では、反復毎に計算済みの要素数が指数的に増加するように写像適用後の値を計算するような反復計算を作り、これを使うことによって計算時間をＯ（（ｍ＋ｎ）ｌｏｇｎ）にした。
【００６０】
＜実施例＞
本実施例では、暗号化装置１１は、以下の行列Ｔと入力ベクトルｋとを入力された場合について説明する。なお、説明を容易にするために各数値を平文で記載しているが、実際には暗号文で秘密計算を行う。
【００６１】
【数１１】
0005689826.tif 000012
【００６２】
暗号化装置１１は、以下の目印ベクトルｈ、像ベクトルａ０、更新済ベクトルｃ０を生成する。また、秘密計算装置１２−１は、以下のソート用キーベクトルｅを生成する。
【００６３】
【数１２】
0005689826.tif 000013
【００６４】
ソート部１２２は、これらのベクトルを水平に連結した行列をソート用キーベクトル[[ｅ]]の各要素の大小関係に応じてソートする。ソート後の各ベクトルを以下に示す。
【００６５】
【数１３】
0005689826.tif 000014
【００６６】
反復計算部１２３は、ソート後の像ベクトルａ０及び更新済ベクトルｃ０を用いて、ｉ＝１からｉ＝ｔまで式（１６）〜（２０）を繰り返す。各ｉにおける像ベクトルａｉ及び更新済ベクトルｃｉは以下のようになる。
【００６７】
【数１４】
0005689826.tif 000015
【００６８】
ランダム置換部１２４は、ソート後の目印ベクトルｈと反復計算後の像ベクトルａ４
【００６９】
【数１５】
0005689826.tif 000016
【００７０】
の組合せをランダム置換する。なお、目印ベクトルｈの要素０の位置から写像の計算結果の分布が分かるのを防ぐためにランダム置換を行う。目印ベクトルｈの要素０の行は、像ベクトルａ０（暗号行列の２列目と暗号列ベクトル[[０ｎ]]とをそれぞれ垂直に連結したもの）の暗号行列の２列目の要素の行と対応している。例えば、ｈの４番目の０と５番目の０との間に、ｈは５個の要素（９、５、２、３及び７）を持っている。これはｙの４番目の要素と５番目の要素との間に、５個の値が存在することを表している。ランダム置換前に目印ベクトルｈを復元すると、この分布が分かるが、ランダム置換後に目印ベクトルｈを復元することで、これを防ぐことができる。
【００７１】
並び替え部１２６は、復元した目印ベクトルｈの要素の内、１からｎまでの値を持つ要素と同じ行の像ベクトル[[ａｔ]]の要素を１からｎまで順に並べた列ベクトルを暗号出力ベクトルｖとして求める。
【００７２】
【数１６】
0005689826.tif 000017
【００７３】
この出力ベクトルｖは、入力ベクトルｋに行列Ｔが表現する写像を適用したベクトルとなっていることが分かる。
【００７４】
なお、実施例１において、入力ベクトルｋの各要素が必ずしも行列Ｔの１列目からなる列ベクトルｘに含まれなくてもよい。この場合、ｘの各要素を小さいものからｘ１，ｘ２，…，ｘｍとし、行列Ｔの表現する写像をｆとすると、[−∞，ｘ１），[ｘ１，ｘ２），…，[ｘｍ−１，ｘｍ），[ｘｍ，∞]の各区間に含まれる値はそれぞれ０，ｆ（ｘ１），…，ｆ（ｘｍ−１）、ｆ（ｘｍ）として出力される。上述の例での入力ベクトルをｋ＝（３７，３０，３２，４９，２８，３，３４，４１，２５）Ｔとしても同じ出力ベクトルｖ＝（４０，３０，３０，５０，３０，０，３０，４０，３０）Ｔが得られ、この例では５４以下の自然数に対する四捨五入が実現できている。
【００７５】
＜変形例＞
本実施形態では、秘密計算装置側でソート用キーベクトル生成部１２１の処理を行っているが、暗号化装置１１側で行ってもよい。その場合、暗号化装置１１は生成したＮ個のソート用キーベクトル[[ｅ]]をＮ個の秘密計算装置１２−１，１２−２，…，１２−Ｎに送信し配布する。
【００７６】
本実施形態では、秘密計算装置側で反復回数ｔを求めているが、暗号化装置１１においてｔを求め、ｔをＮ個の秘密計算装置１２−１，１２−２，…，１２−Ｎに送信し配布する構成としてもよい。
【００７７】
本実施形態では、秘密計算装置とは別の装置として暗号化装置を構成しているが、何れかの秘密計算装置上に暗号化装置を実装してもよい。
【００７８】
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００７９】
＜プログラム及び記録媒体＞
上述した暗号化装置及び秘密計算装置は、コンピュータにより機能させることもできる。この場合はコンピュータに、目的とする装置（各種実施形態で図に示した機能構成をもつ装置）として機能させるためのプログラム、またはその処理手順（各実施形態で示したもの）の各過程をコンピュータに実行させるためのプログラムを、ＣＤ−ＲＯＭ、磁気ディスク、半導体記憶装置などの記録媒体から、あるいは通信回線を介してそのコンピュータ内にダウンロードし、そのプログラムを実行させればよい。
【図１】
0005689826.tif 000018
【図２】
0005689826.tif 000019
【図３】
0005689826.tif 000020
【図４】
0005689826.tif 000021
【図５】
0005689826.tif 000022
【図６】
0005689826.tif 000023
【図７】
0005689826.tif 000024