(57)【特許請求の範囲】
【請求項１】
Ｎ（ｉ），Ｍ（ｉ）が１以上の整数、Ｌが２以上の整数、ｉ＝１，...，Ｌ、ｎ（ｉ）＝１，...，Ｎ（ｉ）、各エントリＥｉ，ｎ（ｉ）に対応するＭ（ｉ）個の属性Ａｉ，１，...，Ａｉ，Ｍ（ｉ）の属性値を要素とする属性ベクトルがＶｉ，ｎ（ｉ）、前記属性ベクトルＶｉ，１，...，Ｖｉ，Ｎ（ｉ）からなる行列がＴｉ、前記属性ベクトルＶｉ，ｎ（ｉ）の各要素の暗号文を要素とするベクトルが暗号化属性ベクトル［Ｖｉ，ｎ（ｉ）］、前記暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］からなる行列が入力暗号化行列［Ｔｉ］であり、前記暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］をランダム置換し、置換暗号化行列［ＲＴｉ］を得る表シャッフル部と、
何れかの属性Ａｉ∈｛Ａｉ，１，...，Ａｉ，Ｍ（ｉ）｝のすべてのエントリＥｉ，１，...，Ｅｉ，Ｎ（ｉ）に対応する属性値を要素とするベクトルがキーベクトルｋｉ、前記キーベクトルｋｉに対応する前記置換暗号化行列［ＲＴｉ］の要素［ＫＥｉ，ｎ（ｉ）］からなるベクトルが暗号化キーベクトル［ｋｉ］、Ｎ（ｉ）個の互いに異なる要素ＴＥｉ，ｎ（ｉ）の暗号文［ＴＥｉ，ｎ（ｉ）］を要素とするベクトルが暗号化タグベクトル［ｔｉ］であり、前記暗号化キーベクトル［ｋｉ］の各要素［ＫＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））に対し、前記暗号化タグベクトル［ｔｉ］の各要素［ＴＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））を対応付けるタグ付け部と、
前記暗号化キーベクトル［ｋ１］，...，［ｋＬ］のすべての要素からなる暗号化結合キーベクトル［ｋ］、および、前記暗号化タグベクトル［ｔ１］，...，［ｔＬ］のすべての要素からなる暗号化結合タグベクトル［ｔ］を得るベクトル結合部と、
前記暗号化結合キーベクトル［ｋ］に含まれる属性値ＡＴＴ（ｐ）（ｐ∈｛１，...，Ｐ｝、Ｐは正整数）に対応するＬ個の要素からなる集合がグループＧ（ｐ）であり、前記グループＧ（ｐ）にグループ値ＧＶ（ｐ）が対応し、互いに異なる前記グループＧ（ｐ）には互いに異なる前記グループ値ＧＶ（ｐ）が対応し、いずれの前記グループＧ（ｐ）にも属さない前記暗号化結合キーベクトル［ｋ］の要素にはいずれの前記グループ値ＧＶ（ｐ）とも異なる規定値が対応し、要素ＧＥｉ，１，...，ＧＥｉ，Ｎ（ｉ）（ｉ＝１，...，Ｌ）からなるベクトルがグループベクトルｇ、前記グループＧ（ｐ）に属する前記要素［ＫＥｉ，ｎ（ｉ，ｐ）］（ｎ（ｉ，ｐ）∈｛１，...，Ｎ（ｉ）｝）に対応する前記要素ＧＥｉ，ｎ（ｉ，ｐ）が前記グループ値ＧＶ（ｐ）、いずれの前記グループＧ（ｐ）にも属さない前記要素［ＫＥｉ，ｎ（ｉ，ｑ）］（ｎ（ｉ，ｑ）≠ｎ（ｉ，ｐ）、ｎ（ｉ，ｑ）∈｛１，...，Ｎ（ｉ）｝）に対応する前記要素ＧＥｉ，ｎ（ｉ，ｑ）が前記規定値であり、前記要素ＧＥｉ，１，...，ＧＥｉ，Ｎ（ｉ）の暗号文［ＧＥｉ，１］，...，［ＧＥｉ，Ｎ（ｉ）］からなる暗号化グループベクトル［ｇ］を生成する抽象化グループ計算部と、
前記暗号化結合タグベクトル［ｔ］および前記暗号化グループベクトル［ｇ］の各要素の対応関係を保ちつつ、前記暗号化結合タグベクトル［ｔ］および前記暗号化グループベクトル［ｇ］の各要素をランダム置換し、置換暗号化グループベクトル［ｒｔ］および置換暗号化結合タグベクトル［ｒｇ］を得るタグシャッフル部と、
前記置換暗号化グループベクトル［ｒｇ］の復元値である復元グループベクトルｒｇ、および前記置換暗号化結合タグベクトル［ｒｔ］の復元値である前記復元結合タグベクトルｒｔを用い、前記復元グループベクトルｒｇの要素ＧＥｉ，ｎ（ｉ，ｐ）に対応する前記復元結合タグベクトルｒｔの要素ＴＥｉ，ｎ（ｉ，ｐ）を得、前記置換暗号化行列［ＲＴｉ］から前記要素ＴＥｉ，ｎ（ｉ，ｐ）に対応する暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］を得、すべての前記暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］からなる暗号化行列［Ｓ］を出力する行列結合部と、
を有する秘密計算装置。
【請求項２】
請求項１の秘密計算装置であって、
前記要素ＴＥｉ，ｎ（ｉ）が０以外であり、
前記抽象化グループ計算部は、
前記暗号化結合キーベクトル［ｋ］および前記暗号化結合タグベクトル［ｔ］の各要素の対応関係を保ちつつ、前記暗号化結合キーベクトル［ｋ］および前記暗号化結合タグベクトル［ｔ］の各要素に対し、前記暗号化結合キーベクトル［ｋ］の要素に対応する属性値をキーとしたソートを行い、ソートベクトル［ｓｋ］および［ｓｔ］を得るソート部と、
前記ソートベクトル［ｓｋ］の要素［ＫＥｎ］（ｎ＝１，...，Ｎ、Ｎ＝Ｎ（１）＋... ＋Ｎ（Ｌ））のうち、同一の前記属性値ＡＴＴ（ｐ）（ｐ∈｛１，...，Ｐ｝）に対応するＬ個の要素［ＫＥｒ（ｐ）］，...，［ＫＥｒ（ｐ）＋Ｌ−１］（ｒ（ｐ）∈｛１，...，Ｎ｝）を特定し、前記要素［ＫＥｒ（ｐ）］（ｐ＝１，...，Ｐ）に対応する要素［ＥＥｒ（ｐ）］をそれぞれ１とし、前記要素［ＥＥｒ（ｐ）］（ｐ＝１，...，Ｐ）以外の要素を０としたＮ個の要素［ＥＥ１］，...，［ＥＥＮ］からなる暗号化等号ベクトル［ｅ］を得る連続検知部と、
前記ソートベクトル［ｓｔ］の要素［ＴＥｎ］と前記暗号化等号ベクトル［ｅ］の要素［ＥＥｎ］との乗算値を要素［ＸＥｎ］（ｎ＝１，...，Ｎ）とする代表ベクトル［ｘ］を得る代表計算部と、
前記暗号化グループベクトル［ｇ］のｗ＋１番目の要素が［ｇ］［ｗ］であり、代表ベクトル［ｘ］のｊ＋１番目の要素が［ｘ］［ｊ］であり、
【数１】
0005689845.tif 000013
の復元値が［ｇ］［ｗ］の復元値と等しくなる前記暗号化グループベクトル［ｇ］を生成するグループ計算部と、
を有する秘密計算装置。
【請求項３】
請求項１または２の秘密計算装置であって、
前記暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］が前記入力暗号化行列［Ｔｉ］の行ベクトルであり、かつ、前記暗号化キーベクトル［ｋｉ］が前記置換暗号化行列［ＲＴｉ］の何れかの列ベクトルであるか、または、前記暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］が前記入力暗号化行列［Ｔｉ］の列ベクトルであり、かつ、前記暗号化キーベクトル［ｋｉ］が前記置換暗号化行列［ＲＴｉ］の何れかの行ベクトルである、秘密計算装置。
【請求項４】
Ｎ（ｉ），Ｍ（ｉ）が１以上の整数、Ｌが２以上の整数、ｉ＝１，...，Ｌ、ｎ（ｉ）＝１，...，Ｎ（ｉ）、各エントリＥｉ，ｎ（ｉ）に対応するＭ（ｉ）個の属性Ａｉ，１，...，Ａｉ，Ｍ（ｉ）の属性値を要素とする属性ベクトルがＶｉ，ｎ（ｉ）、前記属性ベクトルＶｉ，１，...，Ｖｉ，Ｎ（ｉ）からなる行列がＴｉ、前記属性ベクトルＶｉ，ｎ（ｉ）の各要素の暗号文を要素とするベクトルが暗号化属性ベクトル［Ｖｉ，ｎ（ｉ）］、前記暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］からなる行列が入力暗号化行列［Ｔｉ］であり、表シャッフル部において、前記暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］をランダム置換し、置換暗号化行列［ＲＴｉ］を得る表シャッフルステップと、
何れかの属性Ａｉ∈｛Ａｉ，１，...，Ａｉ，Ｍ（ｉ）｝のすべてのエントリＥｉ，１，...，Ｅｉ，Ｎ（ｉ）に対応する属性値を要素とするベクトルがキーベクトルｋｉ、前記キーベクトルｋｉに対応する前記置換暗号化行列［ＲＴｉ］の要素［ＫＥｉ，ｎ（ｉ）］からなるベクトルが暗号化キーベクトル［ｋｉ］、Ｎ（ｉ）個の互いに異なる要素ＴＥｉ，ｎ（ｉ）の暗号文［ＴＥｉ，ｎ（ｉ）］を要素とするベクトルが暗号化タグベクトル［ｔｉ］であり、タグ付け部において、前記暗号化キーベクトル［ｋｉ］の各要素［ＫＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））に対し、前記暗号化タグベクトル［ｔｉ］の各要素［ＴＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））を対応付けるタグ付けステップと、
ベクトル結合部において、前記暗号化キーベクトル［ｋ１］，...，［ｋＬ］のすべての要素からなる暗号化結合キーベクトル［ｋ］、および、前記暗号化タグベクトル［ｔ１］，...，［ｔＬ］のすべての要素からなる暗号化結合タグベクトル［ｔ］を得るベクトル結合ステップと、
前記暗号化結合キーベクトル［ｋ］に含まれる属性値ＡＴＴ（ｐ）（ｐ∈｛１，...，Ｐ｝、Ｐは正整数）に対応するＬ個の要素からなる集合がグループＧ（ｐ）であり、前記グループＧ（ｐ）にグループ値ＧＶ（ｐ）が対応し、互いに異なる前記グループＧ（ｐ）には互いに異なる前記グループ値ＧＶ（ｐ）が対応し、いずれの前記グループＧ（ｐ）にも属さない前記暗号化結合キーベクトル［ｋ］の要素にはいずれの前記グループ値ＧＶ（ｐ）とも異なる規定値が対応し、要素ＧＥｉ，１，...，ＧＥｉ，Ｎ（ｉ）（ｉ＝１，...，Ｌ）からなるベクトルがグループベクトルｇ、前記グループＧ（ｐ）に属する前記要素［ＫＥｉ，ｎ（ｉ，ｐ）］（ｎ（ｉ，ｐ）∈｛１，...，Ｎ（ｉ）｝）に対応する前記要素ＧＥｉ，ｎ（ｉ，ｐ）が前記グループ値ＧＶ（ｐ）、いずれの前記グループＧ（ｐ）にも属さない前記要素［ＫＥｉ，ｎ（ｉ，ｑ）］（ｎ（ｉ，ｑ）≠ｎ（ｉ，ｐ）、ｎ（ｉ，ｑ）∈｛１，...，Ｎ（ｉ）｝）に対応する前記要素ＧＥｉ，ｎ（ｉ，ｑ）が前記規定値であり、抽象化グループ計算部において、前記要素ＧＥｉ，１，...，ＧＥｉ，Ｎ（ｉ）の暗号文［ＧＥｉ，１］，...，［ＧＥｉ，Ｎ（ｉ）］からなる暗号化グループベクトル［ｇ］を生成する抽象化グループ計算ステップと、
タグシャッフル部において、前記暗号化結合タグベクトル［ｔ］および前記暗号化グループベクトル［ｇ］の各要素の対応関係を保ちつつ、前記暗号化結合タグベクトル［ｔ］および前記暗号化グループベクトル［ｇ］の各要素をランダム置換し、置換暗号化グループベクトル［ｒｔ］および置換暗号化結合タグベクトル［ｒｇ］を得るタグシャッフルステップと、
行列結合部において、前記置換暗号化グループベクトル［ｒｇ］の復元値である復元グループベクトルｒｇ、および前記置換暗号化結合タグベクトル［ｒｔ］の復元値である前記復元結合タグベクトルｒｔを用い、前記復元グループベクトルｒｇの要素ＧＥｉ，ｎ（ｉ，ｐ）に対応する前記復元結合タグベクトルｒｔの要素ＴＥｉ，ｎ（ｉ，ｐ）を得、前記置換暗号化行列［ＲＴｉ］から前記要素ＴＥｉ，ｎ（ｉ，ｐ）に対応する暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］を得、すべての前記暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］からなる暗号化行列［Ｓ］を出力する行列結合ステップと、
を有する秘密計算方法。
【請求項５】
請求項４の秘密計算方法であって、
前記要素ＴＥｉ，ｎ（ｉ）が０以外であり、
前記抽象化グループ計算ステップは、
前記暗号化結合キーベクトル［ｋ］および前記暗号化結合タグベクトル［ｔ］の各要素の対応関係を保ちつつ、前記暗号化結合キーベクトル［ｋ］および前記暗号化結合タグベクトル［ｔ］の各要素に対し、前記暗号化結合キーベクトル［ｋ］の要素に対応する属性値をキーとしたソートを行い、ソートベクトル［ｓｋ］および［ｓｔ］を得るソートステップと、
前記ソートベクトル［ｓｋ］の要素［ＫＥｎ］（ｎ＝１，...，Ｎ、Ｎ＝Ｎ（１）＋... ＋Ｎ（Ｌ））のうち、同一の前記属性値ＡＴＴ（ｐ）（ｐ∈｛１，...，Ｐ｝）に対応するＬ個の要素［ＫＥｒ（ｐ）］，...，［ＫＥｒ（ｐ）+Ｌ＋１］（ｒ（ｐ）∈｛１，...，Ｎ｝）を特定し、前記要素［ＫＥｒ（ｐ）］（ｐ＝１，...，Ｐ）に対応する要素［ＥＥｒ（ｐ）］をそれぞれ１とし、前記要素［ＥＥｒ（ｐ）］（ｐ＝１，...，Ｐ）以外の要素を０としたＮ個の要素［ＥＥ１］，...，［ＥＥＮ］からなる暗号化等号ベクトル［ｅ］を得る連続検知ステップと、
前記ソートベクトル［ｓｔ］の要素［ＴＥｎ］と前記暗号化等号ベクトル［ｅ］の要素［ＥＥｎ］との乗算値を要素［ＸＥｎ］（ｎ＝１，...，Ｎ）とする代表ベクトル［ｘ］を得る代表計算ステップと、
前記暗号化グループベクトル［ｇ］のｗ＋１番目の要素が［ｇ］［ｗ］であり、代表ベクトル［ｘ］のｊ＋１番目の要素が［ｘ］［ｊ］であり、
【数１】
0005689845.tif 000014
の復元値が［ｇ］［ｗ］の復元値と等しくなる前記暗号化グループベクトル［ｇ］を生成するグループ計算ステップと、
を有する秘密計算方法。
【請求項６】
請求項１から３の何れかの秘密計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号応用技術に関するものであり、特に表のデータを暗号化したまま、共通のキーをもとに表の結合を行う技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば、非特許文献１参照）。非特許文献１に記載された方法では、３個の秘密計算装置に数値の断片を分散させるという暗号化を行い、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）などを実行し、それらの実行結果を３個の秘密計算装置に分散された状態、すなわち暗号化されたまま保持させる。
【０００３】
秘密計算による行列の結合演算を実現した方法として、非特許文献２の方法がある。非特許文献２の方法では、秘密計算によって、まず複数の表の直積（表の要素からなる集合の直積）を計算し、その後、得られた直積集合の要素からなる行列から結合後の表に含まれない行を削除することにより、秘密計算上での結合の演算を実現している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考,” In CSS, 2010.
【非特許文献２】志村正法, 遠藤つかさ, 宮崎邦彦, 吉浦裕, “安全で機能制限のないデータベースを実現するマルチパーティプロトコルを用いた関係代数演算,” 情報処理学会研究報告, CSEC, Vol. 2008, No. 71, pp. 187-193, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、従来の方法では、結合する表の個数がＬ、各表Ｔ（ｉ）（ｉ＝１，...，Ｌ）の行数がそれぞれＭ（ｉ）である場合、計算時間がＯ（Πi=1,...,L Ｍ（ｉ））と膨大になってしまう。
本発明の目的は、従来よりも少ない計算時間で、秘密計算による行列の結合演算を実現する技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
まず、入力暗号化行列［Ｔｉ］の暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］をランダム置換し、置換暗号化行列［ＲＴｉ］を得る。ただし、Ｎ（ｉ），Ｍ（ｉ）が１以上の整数、Ｌが２以上の整数、ｉ＝１，...，Ｌ、ｎ（ｉ）＝１，...，Ｎ（ｉ）、各エントリＥｉ，ｎ（ｉ）に対応するＭ（ｉ）個の属性Ａｉ，１，...，Ａｉ，Ｍ（ｉ）の属性値を要素とする属性ベクトルがＶｉ，ｎ（ｉ）、属性ベクトルＶｉ，１，...，Ｖｉ，Ｎ（ｉ）からなる行列がＴｉ、属性ベクトルＶｉ，ｎ（ｉ）の各要素の暗号文を要素とするベクトルが暗号化属性ベクトル［Ｖｉ，ｎ（ｉ）］、暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］からなる行列が入力暗号化行列［Ｔｉ］である。
【０００７】
次に、暗号化キーベクトル［ｋｉ］の各要素［ＫＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））に対し、暗号化タグベクトル［ｔｉ］の各要素［ＴＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））を対応付ける。ただし、何れかの属性Ａｉ∈｛Ａｉ，１，...，Ａｉ，Ｍ（ｉ）｝のすべてのエントリＥｉ，１，...，Ｅｉ，Ｎ（ｉ）に対応する属性値を要素とするベクトルがキーベクトルｋｉ、キーベクトルｋｉに対応する置換暗号化行列［ＲＴｉ］の要素［ＫＥｉ，ｎ（ｉ）］からなるベクトルが暗号化キーベクトル［ｋｉ］、Ｎ（ｉ）個の互いに異なる要素ＴＥｉ，ｎ（ｉ）の暗号文［ＴＥｉ，ｎ（ｉ）］を要素とするベクトルが暗号化タグベクトル［ｔｉ］である。
【０００８】
次に、暗号化キーベクトル［ｋ１］，...，［ｋＬ］のすべての要素からなる暗号化結合キーベクトル［ｋ］、および、暗号化タグベクトル［ｔ１］，...，［ｔＬ］のすべての要素からなる暗号化結合タグベクトル［ｔ］を得る。
【０００９】
次に、グループベクトルｇの要素ＧＥｉ，１，...，ＧＥｉ，Ｎ（ｉ）（ｉ＝１，...，Ｌ）の暗号文［ＧＥｉ，１］，...，［ＧＥｉ，Ｎ（ｉ）］からなる暗号化グループベクトル［ｇ］を生成する。ただし、暗号化結合キーベクトル［ｋ］に含まれる属性値ＡＴＴ（ｐ）（ｐ∈｛１，...，Ｐ｝、Ｐは正整数）に対応するＬ個の要素からなる集合がグループＧ（ｐ）であり、グループＧ（ｐ）にグループ値ＧＶ（ｐ）が対応し、互いに異なるグループＧ（ｐ）には互いに異なるグループ値ＧＶ（ｐ）が対応する。いずれのグループＧ（ｐ）にも属さない暗号化結合キーベクトル［ｋ］の要素にはいずれのグループ値ＧＶ（ｐ）とも異なる規定値が対応する。グループＧ（ｐ）に属する要素［ＫＥｉ，ｎ（ｉ，ｐ）］（ｎ（ｉ，ｐ）∈｛１，...，Ｎ（ｉ）｝）に対応する要素ＧＥｉ，ｎ（ｉ，ｐ）がグループ値ＧＶ（ｐ）、いずれのグループＧ（ｐ）にも属さない要素［ＫＥｉ，ｎ（ｉ，ｑ）］（ｎ（ｉ，ｑ）≠ｎ（ｉ，ｐ）、ｎ（ｉ，ｑ）∈｛１，...，Ｎ（ｉ）｝）に対応する要素ＧＥｉ，ｎ（ｉ，ｑ）が規定値である。
【００１０】
次に、暗号化結合タグベクトル［ｔ］および暗号化グループベクトル［ｇ］の各要素の対応関係を保ちつつ、暗号化結合タグベクトル［ｔ］および暗号化グループベクトル［ｇ］の各要素をランダム置換し、置換暗号化グループベクトル［ｒｔ］および置換暗号化結合タグベクトル［ｒｇ］を得る。
【００１１】
次に、置換暗号化グループベクトル［ｒｇ］の復元値である復元グループベクトルｒｇ、および置換暗号化結合タグベクトル［ｒｔ］の復元値である復元結合タグベクトルｒｔを用い、復元グループベクトルｒｇの要素ＧＥｉ，ｎ（ｉ，ｐ）に対応する復元結合タグベクトルｒｔの要素ＴＥｉ，ｎ（ｉ，ｐ）を得、置換暗号化行列［ＲＴｉ］から要素ＴＥｉ，ｎ（ｉ，ｐ）に対応する暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］を得、すべての暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］からなる暗号化行列［Ｓ］を出力する。
【発明の効果】
【００１２】
本発明では、各行列Ｔｉのキーベクトルｋｉに対応する暗号化キーベクトル［ｋｉ］を用い、結合行列の暗号文である暗号化行列［Ｓ］を構成する暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］を得てから暗号化行列［Ｓ］を生成する。そのため、結合される全ての表の直積を計算する従来の方法に比べて少ない計算時間で、秘密計算による行列の結合演算を行うことができる。
【図面の簡単な説明】
【００１３】
【図１】図１は、実施形態の秘密結合システムの構成を表す図である。
【図２】図２Ａは、実施形態の秘密計算装置の構成を表す図である。図２Ｂは、実施形態の抽象化グループ計算部の具体例を表す図である。
【図３】図３は、実施形態の秘密計算装置の処理を説明するための図である。
【図４】図４は、抽象化グループ計算方法の具体例を説明するための図である。
【発明を実施するための形態】
【００１４】
図面を参照して本発明の実施形態を説明する。
＜構成＞
図１に例示するように、本形態の秘密結合システム１は、Ｑ個（Ｑは２以上の整数）の秘密計算装置１１−ｑ（ｑ＝１，...，Ｑ）、および生成装置１２を有する。Ｑ個の秘密計算装置１１−ｑ、および生成装置１２は、ネットワークを通じた通信が可能に構成されている。
【００１５】
図２に例示するように、本形態の秘密計算装置１１−ｑは、入力部１１１ａ−ｑ、出力部１１１ｂ−ｑ、表シャッフル部１１２−ｑ、タグ付け部１１３−ｑ、ベクトル結合部１１４−ｑ、抽象化グループ計算部１１５−ｑ、タグシャッフル部１１６−ｑ、行列結合部１１７−ｑ、制御部１１８−ｑ、および記憶部１１９−ｑを有する。図２Ｂに例示するように、本形態の抽象化グループ計算部１１５−ｑは、ソート部１１５１−ｑ、連続検知部１１５２−ｑ、代表計算部１１５３−ｑ、およびグループ計算部１１５４−ｑを有する。
【００１６】
秘密計算装置１１−ｑおよび生成装置１２は、例えば、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）などから構成される公知または専用のコンピュータに所定のプログラムが読み込まれることで構成される特別な装置である。秘密計算装置１１−ｑおよび生成装置１２は、それぞれ制御部１１８−ｑおよび１２８の制御のもとで各処理を実行する。秘密計算装置１１−ｑおよび生成装置１２は、入力データおよび各処理で得られたデータを記憶部１１９−ｑおよび１２９にそれぞれ格納する。秘密計算装置１１−ｑおよび生成装置１２は、それぞれ、記憶部１１９−ｑおよび１２９に格納されたデータを用いて各処理を実行する。
【００１７】
＜方法＞
本形態の各処理は、暗号化、復元、ならびに秘密計算による加算、乗算、等号判定、ランダム置換およびソートからなる。本形態の秘密計算による加算や乗算は、暗号文を入力とし、暗号文に対応する平文の加算や乗算結果の暗号文を出力する処理である。本形態の秘密計算による等号判定は、秘匿関数計算で等号判定を行う２つの値α，βの暗号文［α］，［β］を入力とし、α＝βの場合には値１の暗号文を、そうでない場合は値０の暗号文を出力する処理である。本形態の秘密計算によるランダム置換は、秘匿関数計算でランダム置換を行う暗号文の組［α］の平文αの各要素をランダムに置換した平文βの各要素を暗号化した暗号文の組［β］を計算し、［α］と［β］の各要素の対応が誰にもわからないようにする処理である。本形態の秘密計算によるソートは、秘匿関数計算でソートを行う暗号文の組［α］の平文αの各要素を指定したソートキーの値に従って整列（ソート）した平文βの各要素を暗号化した暗号文の組［β］を計算し、［α］と［β］の各要素の対応が誰にもわからないようにする処理である。
【００１８】
暗号化、復元、ならびに秘密計算による加算および乗算としては、例えば参考文献１「五十嵐大, 千田浩司, 濱田浩気, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理”, In SCIS, pp. 1-8, 2011.」に記載された方法を用いることができる。秘密計算による等号判定としては、例えば参考文献２「Ronald Cramer and Ivan Damgard, “Secure distributed linear algebra in a constant number of rounds,” In Joe Kilian, editor, CRYPTO, Vol. 2139 of LNCS, pp. 119-136. Springer, 2001.」の7.1に記載された方法を用いることができる。秘密計算によるランダム置換としては、例えば参考文献３「濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “３パーティ秘匿関数計算上のランダム置換プロトコル,” In CSS, pp. 1-6, 2010.」に記載された方法を用いることができる。秘密計算によるソートとしては、例えば参考文献４「濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “秘匿関数計算上の線形時間ソート”, In SCIS, pp. 1-7, 2011.」に記載された方法を用いることができる。参考文献１〜４に例示した各処理はよく知られた秘密分散に基づくものであり、暗号化は秘密分散、復元は所定個の分散値からの復元、その他の処理は秘密分散値の線形演算である。しかしながら、これらは本発明を限定するものではなく、論理回路を秘匿化することで秘密計算を行う方法、準同型関数暗号を用いた方法、その他の公知の秘密計算方法によって各処理が実行されてもよい。以下に本形態の秘密結合方法の詳細を説明する。
【００１９】
＜生成装置での処理＞
生成装置１２には、結合演算の対象となるＬ個の表を表す行列Ｔｉ（ｉ＝１，...，Ｌ、Ｌが２以上の整数）が格納されている。本形態の行列Ｔｉは、Ｎ（ｉ）（Ｎ（ｉ）は１以上の整数）個の属性ベクトルＶｉ，１，...，Ｖｉ，Ｎ（ｉ）からなる。属性ベクトルＶｉ，ｎ（ｉ）（ｎ（ｉ）＝１，...，Ｎ（ｉ））は、それぞれ、Ｍ（ｉ）（Ｍ（ｉ）は１以上の整数）個の属性Ａｉ，１，...，Ａｉ，Ｍ（ｉ）の属性値を要素とするベクトル（レコード）である。各属性ベクトルＶｉ，ｎ（ｉ）は各エントリＥｉ，ｎ（ｉ）に対応する。ただし、ｎ（ｉ）は属性ベクトルＶｉ，ｎ（ｉ）の順序や行列Ｔｉ内の位置を表すものではない。属性ベクトルＶｉ，ｎ（ｉ）は、行列Ｔｉの行ベクトルであってもよいし、列ベクトルであってもよい。本形態では、属性ベクトルＶｉ，ｎ（ｉ）が行列Ｔｉの行ベクトルである場合を例示する。
【００２０】
生成装置１２は、行列Ｔｉを暗号化し、行列Ｔｉの暗号文である入力暗号化行列［Ｔｉ］を生成する。各行列Ｔｉに対応する入力暗号化行列［Ｔｉ］は例えばＱ個に分散された暗号文の断片である。所定個数以上の入力暗号化行列［Ｔｉ］が与えられれば行列Ｔｉを復元できるが、所定個数未満の入力暗号化行列［Ｔｉ］からは行列Ｔｉの情報は得られない。例えば、参考文献１の方法で暗号化される場合、入力暗号化行列［Ｔｉ］は行列Ｔｉの各要素の秘密分散値を各要素とする行列となる。各入力暗号化行列［Ｔｉ］は、Ｎ（ｉ）個の暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］から構成される。暗号化属性ベクトル［Ｖｉ，ｎ（ｉ）］は、属性ベクトルＶｉ，ｎ（ｉ）の各要素の暗号文を要素とするベクトル（本形態では行ベクトル）である。Ｌ個の入力暗号化行列［Ｔ１］，...，［ＴＬ］は、ネットワークを通じて各秘密計算装置１１−ｑに送信される。
【００２１】
＜秘密計算装置１１−ｑでの処理＞
各秘密計算装置１１−ｑは、入力暗号化行列［Ｔ１］，...，［ＴＬ］を入力として、予め指定された列をキーとした暗号化行列の結合を行い、新しい表を表す行列の暗号文［Ｓ］を生成して出力する。以下、この結合処理を説明する。
【００２２】
《表シャッフルステップ》
図３に例示するように、入力暗号化行列［Ｔ１］，...，［ＴＬ］は、各秘密計算装置１１−ｑの入力部１１１ａ−ｑに入力され、表シャッフル部１１２−ｑに入力される（ステップＳ１）。表シャッフル部１１２−ｑは、入力暗号化行列［Ｔｉ］ごとに独立に、暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］をランダム置換し、それによって置換暗号化行列［ＲＴｉ］を得て出力する。このランダム置換は、入力暗号化行列［Ｔｉ］を構成する暗号化属性ベクトルの順序を暗号化属性ベクトル単位でランダムに置換する処理（例えば、前述の「秘密計算によるランダム置換」）である（ステップＳ２）。
【００２３】
《タグ付けステップ》
タグ付け部１１３−ｑは、各置換暗号化行列［ＲＴｉ］に対し、Ｎ（ｉ）個の互いに異なる要素ＴＥｉ，1,...,ＴＥｉ，Ｎ（ｉ）（例えば０以外の要素）からなるタグベクトルｔｉを生成する。本形態のタグベクトルｔｉは、各置換暗号化行列［ＲＴｉ］の行数と同じ個数の要素を持つ列ベクトルである。本形態の各要素ＴＥｉ，1,...,ＴＥｉ，Ｎ（ｉ）は０以外の整数であり、ＴＥ１，1,...,ＴＥ１，Ｎ（１），...，ＴＥＬ，1,...,ＴＥＬ，Ｎ（Ｌ）は互いに重複する値をとらない。
【００２４】
またタグ付け部１１３−ｑは、タグベクトルｔｉの暗号文である暗号化タグベクトル［ｔｉ］を生成する。本形態の暗号化タグベクトル［ｔｉ］は、タグベクトルｔｉの要素ＴＥｉ，ｎ（ｉ）の暗号文［ＴＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））を要素とするＮ（ｉ）次元ベクトルである。さらにタグ付け部１１３−ｑは、暗号化タグベクトル［ｔｉ］の各要素［ＴＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））を、置換暗号化行列［ＲＴｉ］に含まれる暗号化キーベクトル［ｋｉ］の各要素［ＫＥｉ，ｎ（ｉ）］（ｎ（ｉ）＝１，...，Ｎ（ｉ））に対応付けて出力する。ただし暗号化キーベクトル［ｋｉ］は、行列Ｔｉのキーベクトルｋｉに対応する置換暗号化行列［ＲＴｉ］の要素［ＫＥｉ，ｎ（ｉ）］からなる。本形態では各置換暗号化行列［ＲＴｉ］の何れかの列ベクトルが暗号化キーベクトル［ｋｉ］とされる。またキーベクトルｋｉは、何れかの１個の属性Ａｉ∈｛Ａｉ，１，...，Ａｉ，Ｍ（ｉ）｝のすべてのエントリＥｉ，１，...，Ｅｉ，Ｎ（ｉ）に対応する属性値を要素とするベクトルである（ステップＳ３）。
【００２５】
《ベクトル結合ステップ》
ベクトル結合部１１４−ｑに、暗号化キーベクトル［ｋ１］，...，［ｋＬ］および暗号化タグベクトル［ｔ１］，...，［ｔＬ］が入力される。ベクトル結合部１１４−ｑは、暗号化キーベクトル［ｋ１］，...，［ｋＬ］のすべての要素からなる暗号化結合キーベクトル［ｋ］、および、暗号化タグベクトル［ｔ１］，...，［ｔＬ］のすべての要素からなる暗号化結合タグベクトル［ｔ］を得て出力する。言い換えると、ベクトル結合部１１４−ｑは、暗号化キーベクトル［ｋ１］，...，［ｋＬ］を連結して暗号化結合キーベクトル［ｋ］を生成し、暗号化タグベクトル［ｔ１］，...，［ｔＬ］を連結して暗号化結合タグベクトル［ｔ］を生成する。本形態では暗号化キーベクトル［ｋ１］，...，［ｋＬ］および暗号化タグベクトル［ｔ１］，...，［ｔＬ］は列ベクトルであるため、ベクトル結合部１１４−ｑは、暗号化キーベクトル［ｋ１］，...，［ｋＬ］を列方向につなげて暗号化結合キーベクトル［ｋ］を得、暗号化タグベクトル［ｔ１］，...，［ｔＬ］を列方向につなげて暗号化結合タグベクトル［ｔ］を得る（ステップＳ４）。
【００２６】
《抽象化グループ計算ステップ》
抽象化グループ計算部１１５−ｑに、暗号化結合キーベクトル［ｋ］および暗号化結合タグベクトル［ｔ］が入力される。抽象化グループ計算部１１５−ｑは、これらを用いて暗号化グループベクトル［ｇ］を得て出力する。ただし、暗号化グループベクトル［ｇ］は、グループベクトルｇの要素ＧＥｉ，１，...，ＧＥｉ，Ｎ（ｉ）（ｉ＝１，...，Ｌ）の暗号文［ＧＥｉ，１］，...，［ＧＥｉ，Ｎ（ｉ）］からなるベクトルである。また、グループベクトルｇの要素ＧＥｉ，１，...，ＧＥｉ，Ｎ（ｉ）は、以下を満たす要素である。
【００２７】
暗号化結合キーベクトル［ｋ］に含まれる属性値ＡＴＴ（ｐ）（ｐ∈｛１，...，Ｐ｝、Ｐは正整数）に対応するＬ個の要素からなる集合をグループＧ（ｐ）とする。言い換えると、グループＧ（ｐ）に属するＬ個の要素［ＫＥｉ，ｎ（ｉ，ｐ）］（ｎ（ｉ，ｐ）∈｛１，...，Ｎ（ｉ）｝）の復元値はすべて属性値ＡＴＴ（ｐ）である。グループＧ（ｐ）にはグループ値ＧＶ（ｐ）（例えば０以外の値）が割り当てられる。互いに異なるグループＧ（ｐ）には、互いに異なるグループ値ＧＶ（ｐ）が割り当てられる。いずれのグループＧ（ｐ）にも属さない暗号化結合キーベクトル［ｋ］の要素には、いずれのグループ値ＧＶ（ｐ）とも異なる規定値（例えば０）が割り当てられる。グループＧ（ｐ）に属する要素［ＫＥｉ，ｎ（ｉ，ｐ）］（ｎ（ｉ，ｐ）∈｛１，...，Ｎ（ｉ）｝）に対応する要素ＧＥｉ，ｎ（ｉ，ｐ）は、上記グループ値ＧＶ（ｐ）である。いずれのグループＧ（ｐ）にも属さない要素［ＫＥｉ，ｎ（ｉ，ｑ）］（ｎ（ｉ，ｑ）≠ｎ（ｉ，ｐ）、ｎ（ｉ，ｑ）∈｛１，...，Ｎ（ｉ）｝）に対応する要素ＧＥｉ，ｎ（ｉ，ｑ）は、上記規定値である。
【００２８】
［暗号化グループベクトルの生成方法の一例］
図４を用い、暗号化グループベクトル［ｇ］の生成方法の一例を示す。以下の例では、要素ＴＥｉ，ｎ（ｉ）が０以外に設定されることを前提とする。
【００２９】
まず、ソート部１１５１−ｑに暗号化結合キーベクトル［ｋ］および暗号化結合タグベクトル［ｔ］が入力される。ソート部１１５１−ｑは、これらの各要素の対応関係を保ちつつ、［ｋ］および［ｔ］の各要素に対し、［ｋ］の要素に対応する属性値（復元値）をキーとしたソートを行い、ソートベクトル［ｓｋ］および［ｓｔ］を得て出力する。言い換えると、ソート部１１５１−ｑは、（［ｋ］，［ｔ］）を［ｋ］の要素に対応する復元値をソートキーとしたソートを行い、（［ｓｋ］，［ｓｔ］）を得る。このソートは、例えば前述の「秘密計算によるソート」によって行われる（ステップＳ５１）。
【００３０】
次に連続検知部１１５２−ｑが、ソートベクトル［ｓｋ］を入力とし、Ｎ個の要素［ＥＥ１］，...，［ＥＥＮ］からなる暗号化等号ベクトル［ｅ］を得て出力する。すなわち連続検知部１１５２−ｑは、例えば、前述の「秘密計算による等号判定」により、ソートベクトル［ｓｋ］の要素［ＫＥｎ］（ｎ＝１，...，Ｎ、Ｎ＝Ｎ（１）＋... ＋Ｎ（Ｌ））のうち、各属性値ＡＴＴ（ｐ）（ｐ∈｛１，...，Ｐ｝）にそれぞれ対応するＬ個の要素［ＫＥｒ（ｐ）］，...，［ＫＥｒ（ｐ）+Ｌ−１］（ｒ（ｐ）∈｛１，...，Ｎ｝）を特定する。連続検知部１１５２−ｑは、特定された要素［ＫＥｒ（ｐ）］，...，［ＫＥｒ（ｐ）+Ｌ−１］のうち要素［ＫＥｒ（ｐ）］に対応する要素［ＥＥｒ（ｐ）］をそれぞれ１とし、当該要素［ＥＥｒ（ｐ）］（ｐ＝１，...，Ｐ）以外の要素をそれぞれ０とし、暗号化等号ベクトル［ｅ］の要素［ＥＥ１］，...，［ＥＥＮ］を定める。
【００３１】
例えば、連続検知部１１５２−ｑは、秘密計算による等号判定により、ソートベクトル［ｓｋ］の各要素［ＫＥｎ］（ｎ＝１，...，Ｎ、Ｎ＝Ｎ（１）＋... ＋Ｎ（Ｌ））を要素［ＫＥｎ＋Ｌ−１］と比較する。ここで、要素［ＫＥｎ＋Ｌ−１］が存在しないか、要素［ＫＥｎ］の復元値が要素［ＫＥｎ＋Ｌ−１］の復元値と相違する場合、連続検知部１１５２−ｑは、値０を暗号化して得られる値を要素［ＫＥｎ］とする。一方、要素［ＫＥｎ］の復元値が要素［ＫＥｎ＋Ｌ−１］の復元値と一致する場合、連続検知部１１５２−ｑは、値１を暗号化して得られる値を要素［ＫＥｎ］とする（ステップＳ５２）。
【００３２】
次にソートベクトル［ｓｔ］および暗号化等号ベクトル［ｅ］が代表計算部１１５３−ｑに入力される。代表計算部１１５３−ｑは、ソートベクトル［ｓｔ］の要素［ＴＥｎ］と暗号化等号ベクトル［ｅ］の要素［ＥＥｎ］との乗算値を要素［ＸＥｎ］（ｎ＝１，...，Ｎ）とする代表ベクトル［ｘ］を得て出力する。本形態ではソートベクトル［ｓｔ］および暗号化等号ベクトル［ｅ］は列ベクトルであり、代表ベクトル［ｘ］は、ソートベクトル［ｓｔ］と暗号化等号ベクトル［ｅ］との間の対応する要素同士の積を要素とするベクトルで表される。
［ｘ］＝［ｓｔ］（×）［ｅ］
ただし（×）は、同一次元ベクトル間の対応する要素同士の乗算を行う演算子を表す（ステップＳ５３）。
【００３３】
次に代表ベクトル［ｘ］がグループ計算部１１５４−ｑに入力される。グループ計算部１１５４−ｑは、
【数１】
0005689845.tif 000002
の復元値が［ｇ］［ｗ］の復元値と等しくなる暗号化グループベクトル［ｇ］を生成して出力する。ただし、［ｇ］［ｗ］は、暗号化グループベクトル［ｇ］のｗ＋１番目の要素を表し、［ｘ］［ｊ］は、代表ベクトル［ｘ］のｊ＋１番目の要素を表す。この処理は、例えば、上述の「秘密計算による加算」を用いて行われる（ステップＳ５４／［暗号化グループベクトルの生成方法の一例］の説明終了）。
【００３４】
≪タグシャッフルステップ≫
図３に示すように、次にタグシャッフル部１１６−ｑに、ソートベクトル［ｓｔ］および暗号化グループベクトル［ｇ］が入力される。タグシャッフル部１１６−ｑは、ソートベクトル［ｓｔ］および暗号化グループベクトル［ｇ］の各要素の対応関係（暗号化結合タグベクトル［ｔ］および暗号化グループベクトル［ｇ］の各要素の対応関係）を保ちつつ、これらの各要素をランダム置換（例えば、秘密計算によるランダム置換）し、置換暗号化グループベクトル［ｒｔ］および置換暗号化結合タグベクトル［ｒｇ］を得て出力する。本形態では、ソートベクトル［ｓｔ］、暗号化結合タグベクトル［ｔ］、および暗号化グループベクトル［ｇ］が列ベクトルであるため、タグシャッフル部１１６−ｑは、（［ｓｔ］，［ｇ］）の行の対応を維持したまま〔（［ｔ］，［ｇ］）の行の対応を維持したまま〕、各要素をランダム置換（例えば、秘密計算によるランダム置換）し、（［ｒｔ］，［ｒｇ］）を得る（ステップＳ６）。
【００３５】
≪行列結合ステップ≫
次に、置換暗号化グループベクトル［ｒｇ］、置換暗号化結合タグベクトル［ｒｔ］、および置換暗号化行列［ＲＴｉ］が行列結合部１１７−ｑに入力される。行列結合部１１７−ｑは、置換暗号化グループベクトル［ｒｇ］および置換暗号化結合タグベクトル［ｒｔ］を復元し、置換暗号化グループベクトル［ｒｇ］の復元値である復元グループベクトルｒｇ、および置換暗号化結合タグベクトル［ｒｔ］の復元値である復元結合タグベクトルｒｔを得る。行列結合部１１７−ｑは、復元グループベクトルｒｇおよび復元結合タグベクトルｒｔを用い、復元グループベクトルｒｇの要素ＧＥｉ，ｎ（ｉ，ｐ）＝ＧＶ（ｐ）（ｐ∈｛１，...，Ｐ｝）に対応する、復元結合タグベクトルｒｔの要素ＴＥｉ，ｎ（ｉ，ｐ）（ｐ∈｛１，...，Ｐ｝）を得る。さらに行列結合部１１７−ｑは、置換暗号化行列［ＲＴｉ］から要素ＴＥｉ，ｎ（ｉ，ｐ）に対応する暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］（レコード）を得、得られたすべての暗号化属性ベクトル［Ｖｉ，ｎ（ｉ，ｐ）］（ｉ＝１，...，Ｌ、ｐ∈｛１，...，Ｐ｝）からなる暗号化行列［Ｓ］を得て出力する。例えば行列結合部１１７−ｑは、以下のように暗号化行列［Ｓ］を生成する（ステップＳ７）。
【数２】
0005689845.tif 000003
【００３６】
出力部１１１ｂ−ｑは暗号化行列［Ｓ］を出力する（ステップＳ８）。当該暗号化行列［Ｓ］は、ネットワークを介して生成装置１２に送られる。生成装置１２は、当該暗号化行列［Ｓ］から行列Ｓを復元する。
【実施例】
【００３７】
次に具体的な値を示しつつ、秘密計算装置１１−ｑでの処理の実施例を説明する。
《表シャッフルステップ》
実施例ではＬ＝３であり、以下の行列Ｔ１，Ｔ２，Ｔ３の暗号文である入力暗号化行列［Ｔ１］，［Ｔ２］，［Ｔ３］が表シャッフル部１１２−ｑに入力される。
【数３】
0005689845.tif 000004
【００３８】
表シャッフル部１１２−ｑは、入力暗号化行列［Ｔ１］，［Ｔ２］，［Ｔ３］ごとに独立に、入力暗号化行列［Ｔ１］，［Ｔ２］，［Ｔ３］の行ベクトルをランダム置換（秘密計算によるランダム置換）し、それによって以下の行列ＲＴ１，ＲＴ２，ＲＴ３の暗号文である置換暗号化行列［ＲＴ１］，［ＲＴ２］，［ＲＴ３］を得て出力する（ステップＳ２）。
【数４】
0005689845.tif 000005
ただし、行列ＲＴ１は第１列ｋ１＝（２，４，５，１，６）Ｔを、行列ＲＴ２は第１列ｋ２＝（７，２，６，８）Ｔを、行列ＲＴ３は第２列ｋ３＝（１，５，６，２，７）Ｔを、それぞれキーとする。ただし、αＴはαの転置表す。
【００３９】
《タグ付けステップ》
タグ付け部１１３−ｑは、以下のタグベクトルｔ１，ｔ２，ｔ３の暗号文である暗号化タグベクトル［ｔ１］，［ｔ２］，［ｔ３］を生成し、それぞれの要素をキーベクトルｋ１，ｋ２，ｋ３の暗号文である暗号化キーベクトル［ｋ１］，［ｋ２］，［ｋ３］の各要素に対応付ける。タグ付け部１１３−ｑは、暗号化タグベクトル［ｔ１］，［ｔ２］，［ｔ３］を出力する（ステップＳ３）。
【数５】
0005689845.tif 000006
0005689845.tif 000007
0005689845.tif 000008
【００４０】
《ベクトル結合ステップ》
ベクトル結合部１１４−ｑは、暗号化キーベクトル［ｋ１］，［ｋ３］，［ｋ３］および暗号化タグベクトル［ｔ１］，［ｔ２］，［ｔ３］をそれぞれ列方向に連結し、以下の結合キーベクトルｋおよび結合タグベクトルｔの暗号文である、暗号化結合キーベクトル［ｋ］および暗号化結合タグベクトル［ｔ］を得て出力する（ステップＳ４）。
【数６】
0005689845.tif 000009
【００４１】
《抽象化グループ計算ステップ》
抽象化グループ計算部１１５−ｑのソート部１１５１−ｑは、（［ｋ］，［ｔ］）から以下のベクトル（ｓｋ，ｓｔ）の暗号文であるソートベクトル（［ｓｋ］，［ｓｔ］）を得て出力する（ステップＳ５１）。連続検知部１１５２−ｑは、ソートベクトル［ｓｋ］から以下の等号ベクトルｅの暗号文である暗号化等号ベクトル［ｅ］を得て出力する（ステップＳ５２）。代表計算部１１５３−ｑは、ソートベクトル［ｓｔ］および暗号化等号ベクトル［ｅ］から以下のベクトルｘの暗号文である代表ベクトル［ｘ］を得て出力する（ステップＳ５３）。グループ計算部１１５４−ｑは、代表ベクトル［ｘ］を用いて以下のグループベクトルｇの暗号文である暗号化グループベクトル［ｇ］を得て出力する（ステップＳ５４）。
【数７】
0005689845.tif 000010
【００４２】
≪タグシャッフルステップ≫
タグシャッフル部１１６−ｑは、（［ｓｔ］，［ｇ］）の行の対応を維持したまま、これらの各要素をランダム置換（秘密計算によるランダム置換）し、以下のベクトルｒｔ，ｒｇの暗号文である（［ｒｔ］，［ｒｇ］）を得て出力する（ステップＳ６）。
【数８】
0005689845.tif 000011
【００４３】
≪行列結合ステップ≫
行列結合部１１７−ｑは、（［ｒｔ］，［ｒｇ］）を復元してｒｔ，ｒｇを得る。行列結合部１１７−ｑは、復元グループベクトルｒｇの要素“１５”，“２２”に対応する、復元結合タグベクトルｒｔの要素“２３”，“１１”，“３４”，“３３”，“２２”，“１５”を得る。さらに行列結合部１１７−ｑは、置換暗号化行列［ＲＴ１］，［ＲＴ２］，［ＲＴ３］から復元結合タグベクトルｒｔの要素“２３”，“１１”，“３４”，“３３”，“２２”，“１５”に対応する属性ベクトル（６，ｒａｄｉｘ，１），（２，８３，９），（２．６，２），（５．９，６），（２，ｍｅｒｇｅ，０），（６，３９，０）に対応する暗号化属性ベクトルを得る。行列結合部１１７−ｑは、このように得られたすべての暗号化属性ベクトルから、以下の行列Ｓの暗号文である暗号化行列［Ｓ］を得て出力する。
【数９】
0005689845.tif 000012
【００４４】
＜本形態の特徴＞
本形態では、暗号化された各表のキーに対応する暗号化結合キーベクトルを取り出し、当該暗号化結合キーベクトルに同じキーに対応する要素がＬ個（表の個数）存在する場合にそれらの要素を抽出し、抽出した要素に対応する各表のレコードの暗号文をつなぎ合わせることで表の結合を行う。暗号化結合キーベクトルの要素の個数はそれに対応する各表の大きさの和と一致し、計算時間も各表のソートに要する時間の和に比例する。具体的には、本形態では、各表Ｔ（ｉ）（ｉ＝１，...，Ｌ）の行数がそれぞれＭ（ｉ）で、表のソートにＯ（Ｍ（ｉ） ｌｏｇ Ｍ（ｉ））の計算時間を要する場合、Ｏ（Σi=1,...,L Ｍ（ｉ）ｌｏｇ Ｍ（ｉ））の計算時間で表の結合を行うことができる。
【００４５】
また本形態では、表シャッフル部で入力暗号化行列を構成する暗号化属性ベクトルをランダム置換し、それによって得られた置換暗号化行列に暗号化タグベクトルを対応付け、暗号化タグベクトルを用いて結合されるレコードを取り出して暗号化行列を結合する。これにより、入力暗号化行列の要素と暗号化行列の要素との対応関係をかく乱できるため秘匿性が高い。
【００４６】
また本形態では、タグ付け部でタグベクトルが暗号化されるため、タグ付け部よりも後の処理が別の装置で分散処理される場合であっても秘匿性が保たれる。また、タグシャッフル部で暗号化結合タグベクトルおよび暗号化グループベクトルの各要素をランダム置換することとしたため、タグシャッフル部よりも後の処理が別の装置で分散処理される場合であっても秘匿性が保たれる。
【００４７】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記実施形態で説明した行と列とを入れ替えて、同様な処理が実行されてもよい。すなわち、上記実施形態では、暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］が入力暗号化行列［Ｔｉ］の行ベクトルであり、かつ、暗号化キーベクトル［ｋｉ］が置換暗号化行列［ＲＴｉ］の何れかの列ベクトルであった。しかしながら、暗号化属性ベクトル［Ｖｉ，１］，...，［Ｖｉ，Ｎ（ｉ）］が入力暗号化行列［Ｔｉ］の列ベクトルであり、かつ、暗号化キーベクトル［ｋｉ］が置換暗号化行列［ＲＴｉ］の何れかの行ベクトルであってもよい。
【００４８】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、秘密計算装置を構成する機能構成が複数の装置に分散配置されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４９】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００５０】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００５２】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００５３】
１１  秘密計算装置
１２  生成装置
【図１】
0005689845.tif 000015
【図２】
0005689845.tif 000016
【図３】
0005689845.tif 000017
【図４】
0005689845.tif 000018