JP7525066B2 - 秘密計算装置、秘密計算システム、秘密計算方法、およびプログラム - Google Patents

Description

本発明は、暗号技術に関し、特に秘密計算技術に関する。

集合A,Bの積集合をA∩Bと表記する。集合A,Bの秘匿化情報を入力として用い、集合A,Bを秘匿化したまま、秘密計算によって、集合A,Bの積集合演算結果の秘匿化情報を得る秘密積集合計算方法が知られている（例えば、非特許文献１等参照）。

濱田浩気, 五十嵐大, 千田浩司, "秘密計算上の関係代数演算アルゴリズムの改良(Improved Algorithms for Computing Relational Algebra Operators for Secure Function Evaluation)"，通信学技報LOIS2012-82, Vol. 112, No. 446, pp. 76-82, 2013.

しかし、従来の秘密積集合計算方法は、２個の集合の秘匿化情報を入力として用いる場合に限られていた。そのため、３個以上の集合の秘匿化情報を入力として用い、当該３個以上の集合の積集合演算結果の秘匿化情報を得るためには、２個の集合の秘匿化情報を入力として用いる秘密積集合計算を繰り返す必要があった。しかしながら、この方法では、積集合演算の対象となる集合の個数が増加するに伴ってラウンド数が増加し、また、ラウンド間で一部の処理が冗長になることから、計算コストが大きくなるという課題がある。

本発明はこのような点に鑑みてなされたものであり、２個の集合の秘匿化情報だけではなく、３個以上の集合の秘匿化情報をも、直接入力として扱うことが可能であり、当該３個以上の集合の積集合演算結果の秘匿化情報を直接得ることも可能な技術を提供することを目的とする。

本発明では、以下のように、L個の集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}を秘匿化したまま、集合X₀,…,X_L-1の積集合の秘匿化情報を表す秘匿化演算結果を得る。ここでLは２以上の整数であり、i=0,...,L-1であり、r(i)が１以上の整数であり、j(i)=0,...,r(i)-1であり、mが１以上の整数であり、k₀,...,k_m-1が互いに異なるキー情報であり、p=0,...,m-1であり、[α]がαの秘匿化情報であるとする。

(A)カウント部において、秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]を用い、秘密計算によって、カウント結果[c₀],...,[c_m-1]を得る。ここで、各要素x_i,j(i)はキー情報k₀,...,k_m-1の何れかを表し、要素x_0,0,...,x₀,_r(0)-1,…,x_L-1,0,...,x_L-1,_r(L-1)-1のうちキー情報k_pを表す要素の個数がc_pである。

(B)等号判定部において、カウント結果[c₀],...,[c_m-1]を用い、秘密計算によって、等号判定結果[eq₀],...,[eq_m-1]を得る。ここで、c_p=Lのときeq_p=Tであり、c_p=Lでないときにeq_p=Fであり、TおよびFが互いに異なる。

(C)出力フラグ付与部において、互いに対応付けられた秘匿化キー情報[k_p]および等号判定結果[eq_p]を含む秘匿化演算結果を出力する。

これにより、２個の集合の秘匿化情報だけではなく、３個以上の集合の秘匿化情報をも直接入力として扱うことが可能であり、当該３個以上の集合の積集合演算結果の秘匿化情報を直接得ることも可能になる。

図１は実施形態の秘密計算システムの機能構成を例示したブロック図である。 図２は実施形態の秘密計算装置の機能構成を例示したブロック図である。 図３は実施形態の秘密計算方法を例示するためのフロー図である。 図４は実施形態の秘密計算装置のハードウェア構成を例示したブロック図である。

以下、図面を参照して本発明の実施形態を説明する。
［用語の定義］
まず、実施形態で用いる記号を定義する。
X_ｉ={x_i,0,...,x_i,_r(i)-1}は、x_i,0,...,x_i,_r(i)-1を要素とする集合を表す。ｉは集合のインデックスであり、i=0,...,L-1である。Lは集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}の個数を表す２以上の整数である。Lが３以上であってもよい。r(i)は集合X_ｉの要素数を表す１以上の整数である。r(i)は１であってもよいし、２以上であってもよい。λ(i)は集合X_ｉの要素x_i,0,...,x_i,_r(i)-1のインデックスであり、集合X_ｉのインデックスλ(i)に対応する要素をx_i,λ(i)と表記する。ただし、λ(i)=0,...,r(i)-1である。同じ集合X_ｉに属する要素x_i,0,...,x_i,_r(i)-1がそれぞれ表す内容（例えば、数値、文字（アルファベットや数字など）、日時など）は互いに異なっている。すなわち、同じ集合X_ｉに属する要素x_i,0,...,x_i,_r(i)-1がそれぞれ表す内容に重複はない。これは通常の集合の定義と同じである。

(κ₀,...,κ_Θ-1)はΘ個の要素κ₀,...,κ_Θ-1の列を表す。例えば、列(κ₀,...,κ_Θ-1)は要素κ₀,...,κ_Θ-1を持つベクトルであるが、列(κ₀,...,κ_Θ-1)の実装形態に限定はない。

[α]はαの秘匿化情報を表す。すなわち、[α]はαを秘匿化して得られる情報を表す。αが複数の要素κ₀,...,κ_P-1の列(κ₀,...,κ_P-1)である場合、α=(κ₀,...,κ_P-1)が持つ複数の要素κ₀,...,κ_P-1それぞれの秘匿化情報の列[κ₀],...,[κ_P-1]も［α］と表現する。ただし、秘匿化情報[α]は秘密計算が可能な情報である。すなわち、αを秘匿したまま、秘匿化情報[α]を用いた秘密計算によって、αに対する演算結果βの秘匿化情報［β］を得ることができる。秘密計算は秘密分散に基づくものであってもよいし（例えば、非特許文献１等参照）、準同型暗号に基づくものであってもよい。前者の場合、[α]はαを秘密分散して得られるシェア（シークレットシェアまたは秘密分散値と呼ぶ場合もある）である。後者の場合、[α]は準同型暗号方式に則ってαを暗号化して得られる暗号文である。

＜秘密分散＞
秘密分散とはデータを複数の値(シェア)に分けて複数パーティに分散する暗号化手法である。秘密分散の一例は(K,N)閾値秘密分散である。(K,N)閾値秘密分散とは、元データをN個のランダムなシェアに分けて複数パーティに分散する方式であり、K個以上のシェアを集めると元のデータを復元できるが、Ｋ個未満のシェアからは元データの情報を得られないという性質を持つ秘密分散法である。ただし、K,NはK≦Nを満たす正整数である。(K,N)閾値秘密分散の具体例は、Shamir秘密分散（例えば、参考文献１等参照）や複製秘密分散（例えば、参考文献２，３等参照）である。
参考文献１：Adi Shamir, "How to share a secret," Communications of the ACM, Vol. 22, No. 11, pp. 612-613, 1979.
参考文献２：Mitsuru Ito, Akira Saito, and Takao Nishizeki, "Secret sharing scheme realizing general access structure," Electronics and Communications in Japan (Part III: Fundamental Electronic Science), Vol. 72, No. 9, pp. 56-64, 1989.
参考文献３：Ronald Cramer, Ivan Damgard, and Yuval Ishai, "Share conversion, pseudorandom secret-sharing and applications to secure computation," In Theory of Cryptography Conference, pp. 342-362. Springer, 2005.

以下、秘密計算による演算を例示する（例えば、非特許文献１等参照）。
＜等号判定＞
秘密計算による秘匿化情報[α₁],［α₂］の等号判定とは、α₁,α₂の秘匿化情報[α₁],［α₂］（例えば、シェア）を入力として用い、α₁=α₂のときにβ=T（真）であり、α₁=α₂でないときにβ=F（偽）である真偽値β∈{T,F}の秘匿化情報[β]（例えば、シェア）を出力する演算を意味する。ここで、TとFは互いに異なる値を表し（T≠F）、例えば、T=1かつF=0であってもよいし、T=0かつF=1であってもよい。この演算の実行を以下のように記述する。
[β]←E_Q([α₁],[α₂])

＜Group-by Count＞
秘密計算による秘匿化情報[A]のGroup-by Countとは、集合Aの秘匿化情報[A]を入力とし、秘密計算によって、同じ内容（例えば、同じ数値、同じ文字、同じ日時など）を表す要素ごとに集合Aの要素をグループ分けし、各グループG_pに属する要素が表す内容を示すキー情報k_pの秘匿化情報（秘匿化キー情報）[k_p]と、各グループG_pに属する要素の個数c_pの秘匿化情報（カウント結果）[c_p]とを得る処理を意味する。ここで、p=0,...,m-1であり、mはグループG₀,...,G_m-1の個数である。同じグループG_pに属する要素は同じ内容を表し、互いに異なるグループG_p1およびグループG_p2（ただし、p1,p2∈{0,...,m-1}）に属する要素は、互いに異なる内容を表す。すなわち、集合Aの要素はキー情報k₀,...,k_m-1の何れかを表し、集合Aの要素のうちキー情報k_pを表す要素の個数がc_pである。この処理の実行を以下のように記述する。
([k],[c])←GroupbyCount([A]) (1)
ここで[k]は列([k₀],...,[k_m-1])を表し、[c]は列([c₀],...,[c_m-1])を表す。
これを実現する実装方法が参考文献４等に開示されている。
参考文献４：菊池亮, 濱田浩気, 五十嵐大, 高橋元. “横断的動線分析を秘密計算でやってみよう（Secure cross-sector customer-flow invention），” In SCIS2020, pp. 1-8, 2020.

また、集合AのグループG₀,...,G_m-1の個数mを秘匿化するため、さらにダミー情報を含む[k]および[c]と、有効な情報とダミー情報とを区別するためのフラグの列[f]とが、Group-by Countで得られてもよい（例えば、参考文献４等参照）。すなわち、秘密計算による秘匿化情報[A]のGroup-by Countは、集合Aの秘匿化情報[A]を入力とし、秘密計算によって、列([f],[k],[c])を得る処理であってもよい。ここで、列[f]は、m個の有効フラグ[f₀],...,[f_m-1]およびn-m個のダミーフラグ[f_m],...,[f_n-1]を含む列である。nはmよりも大きな整数であり、f₀,...,f_m-1はB₁であり、f_m,...,f_n-1はB₀であり、B₁およびB₀は互いに異なる。B₁およびB₀はどのようなものであってもよいが、例えば、B₁=1かつB₀=0であってもよいし、B₁=0かつB₀=1であってもよい。秘匿化されている限り、有効フラグ[f₀],...,[f_m-1]とダミーフラグ[f_m],...,[f_n-1]との区別がつかないことが望ましい。列[k]は、m個の秘匿化キー情報[k₀],...,[k_m-1]およびn-m個のダミー情報[k_m],...,[k_n-1]を含む列である。秘匿化されている限り、秘匿化キー情報[k₀],...,[k_m-1]とダミー情報[k_m],...,[k_n-1]との区別がつかないことが望ましい。例えば、ダミー情報[k_m],...,[k_n-1]は、ランダムに選択された情報（例えば、乱数）であってもよいし、ランダムに選択された情報の秘匿化情報であってもよい。列[c]は、m個のカウント結果[c₀],...,[c_m-1]およびn-m個のダミー情報[c_m],...,[c_n-1]を含む列である。秘匿化されている限り、カウント結果[c₀],...,[c_m-1]とダミー情報[c_m],...,[c_n-1]との区別がつかないことが望ましい。例えば、ダミー情報[c_m],...,[c_n-1]は、ランダムに選択された情報（例えば、乱数）であってもよいし、ランダムに選択された情報の秘匿化情報であってもよい。また、p=0,...,m-1について、有効フラグ[f_p]と秘匿化キー情報[k_p]とカウント結果[c_p]とが互いに対応付けられ、q=m,...,n-1について、ダミーフラグ[f_q]とダミー情報[k_q]とダミー情報[c_q]とが互いに対応付けられている。この場合、秘密計算による秘匿化情報[A]のGroup-by Countは、以下のように記述される。
([f],[k],[c])←GroupbyCount([A]) (2)

［第１実施形態］
次に、本発明の第１実施形態を説明する。
＜構成＞
図１に例示するように、第１実施形態の秘密計算システム１は、ネットワークを通じて通信可能に構成されたＷ個の秘密計算装置１１－０，…，１１－（Ｗ－１）を有する。ただし、Ｗは１以上の整数である。例えば、秘密計算装置１１－０，…，１１－（Ｗ－１）が秘密分散に基づく秘密計算を行う場合にはＷは２以上の整数であり、準同型暗号に基づく秘密計算を行う場合にはＷは１以上の整数である。

図２に例示するように、秘密計算装置１１－ｗ（ただし、ｗ＝０，…，Ｗ－１）は、入力部１１１－ｗ、結合部１１２－ｗ、カウント部１１３－ｗ、等号判定部１１４－ｗ、出力フラグ付与部１１５－ｗ、制御部１１８－ｗ、および記憶部１１９－ｗを有する。秘密計算装置１１－ｗは、制御部１１８－ｗの制御に基づいて各処理を実行し、秘密計算装置１１－ｗへ入力されたデータ、および各処理で得られたデータは記憶部１１９－ｗに格納され、必要に応じて読み出されて他の処理に用いられる。

＜処理＞
秘密計算装置１１－ｗ（ただし、ｗ＝０，…，Ｗ－１）は、秘密計算により、L個の集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}を秘匿化したまま、集合X₀,…,X_L-1の積集合∩_0≦i≦L-1X_iの演算結果の秘匿化情報を表すデータ構造の秘匿化演算結果[Z]を得て出力する。具体例を示すと、例えば、L=3であり、r(0)=4,r(1)=2,r(2)=2であり、3個の集合X₀,X₁,X₂の要素がアルファベットを表し、X₀={a,b,e,g},X₁={b,e},X₂={a,e}である場合、集合X₀,X₁,X₂の積集合∩_0≦i≦2X_iは{e}となり、秘密計算装置１１－ｗは[e]を表す秘匿化演算結果[Z]を得て出力する。図３を用い、当該秘密計算装置１１－ｗの秘密計算処理を説明する。

秘密計算装置１１－ｗの入力部１１１－ｗには、L個の集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}の秘匿化情報[X₀],...,[X_L-1]が入力される。上記の具体例では、[X₀]={[a],[b],[e],[g]},[X₁]={[b],[e]},[X₂]={[a],[e]}が入力される。[X₀],...,[X_L-1]は、Ｗ個の秘密計算装置１１－０，…，１１－（Ｗ－１）の何れかから送られたものであってもよいし、図示していないその他の装置から送られたものであってもよい（ステップＳ１１１－ｗ）。

[X₀],...,[X_L-1]は結合部１１２－ｗに入力される。結合部１１２－ｗは、[X₀],...,[X_L-1]の要素を結合した秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]の列[U]を得て出力する。例えば、結合部１１２－ｗは、秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]を縦に並べた以下の列[U]を得て出力する。

例えば、上記の具体例の場合、
[X₀]={[a],[b],[e],[g]},[X₁]={[b],[e]},[X₂]={[a],[e]}
であり、結合部１１２－ｗは、以下の式(3)の列[U]を得て出力する。

[X₀],...,[X_L-1]の個数Lは等号判定部１１４－ｗに送られ、列[U]はカウント部１１３－ｗに送られる（ステップＳ１１２－ｗ）。

カウント部１１３－ｗには列[U]が入力される。カウント部１１３－ｗは、列[U]の秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]を用い、秘密計算によって、カウント結果[c₀],...,[c_m-1]の列[c]=([c₀],...,[c_m-1])を得て出力する。ただし、j(i)=0,...,r(i)-1であり、mが１以上の整数であり、k₀,...,k_m-1が互いに異なるキー情報であり、p=0,...,m-1である。各要素x_i,j(i)はキー情報k₀,...,k_m-1の何れかを表し、要素x_0,0,...,x₀,_r(0)-1,…,x_L-1,0,...,x_L-1,_r(L-1)-1のうちキー情報k_pを表す要素の個数がc_pである。
さらにカウント部１１３－ｗが、秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]を用い、秘密計算によって、秘匿化キー情報[k₀],...,[k_m-1]の列[k]=([k₀],...,[k_m-1])を得てもよい。すなわち、カウント部１１３－ｗが、例えば、以下の式(4)の列([k],[c])を得て出力してもよい。
([k],[c])=([k₀],…,[k_m-1],[c₀],…,[c_m-1]) (4)
例えば、カウント部１１３－ｗは、式(1)に示したGroup-by Countによって、以下のように列([k],[c])を得てもよい。
([k],[c])←GroupbyCount([U]) (5)
例えば、式(3)に例示した列[U]の場合、式(5)によって以下の列([k],[c])が得られる。
([k],[c])=([a],[b],[e],[g],[2],[2],[3],[1]) (6)
ここで、[ｋ]=([a],[b],[e],[g]),[c]=([2],[2],[3],[1])である。
キー情報k₀,...,k_m-1に対応する列[k]=([k₀],...,[k_m-1])は出力フラグ付与部１１５－ｗに送られ、列[c]=([c₀],...,[c_m-1])は等号判定部１１４－ｗに送られる（ステップＳ１１３－ｗ）。

等号判定部１１４－ｗには、[X₀],...,[X_L-1]の個数Lおよび列[c]=([c₀],...,[c_m-1])が入力される。等号判定部１１４－ｗは、個数Lおよびカウント結果[c₀],...,[c_m-1]を用い、秘密計算によって、等号判定結果[eq₀],...,[eq_m-1]を得て出力する。ただし、c_p=Lのときeq_p=Tであり、c_p=Lでないときにeq_p=Fであり、TおよびFが互いに異なる。例えば、T=1かつF=0であってもよいし、T=0かつF=1であってもよい。例えば、等号判定部１１４－ｗは、p=0,...,m-1について（すなわち、[c_p]∈[c]について）、以下の計算を行う（例えば、p=0,...,m-1について並列に計算を行う）。
[eq_p]←E_Q([c_p],L)
例えば、式(6)に例示した列[c]の場合、T=1かつF=0とすると、以下の式(7)に示す等号判定結果が得られる。
[eq₀]=[0],[eq₁]=[0],[eq₂]=[1],[eq₃]=[0],[eq₄]=[0] (7)
等号判定結果[eq₀],...,[eq_m-1]の列[eq]は出力フラグ付与部１１５－ｗに送られる（ステップＳ１１４－ｗ）。

出力フラグ付与部１１５－ｗには、列[k]=([k₀],...,[k_m-1])および列[eq]=([eq₀],...,[eq_m-1])が入力される。出力フラグ付与部１１５－ｗは、p=0,...,m-1について、互いに対応付けられた秘匿化キー情報[k_p]および等号判定結果[eq_p]を含む秘匿化演算結果[Z]=([eq],[k])を出力する。例えば、出力フラグ付与部１１５－ｗは、以下の秘匿化演算結果[Z]を出力する。

例えば、式(6)に例示した[k]=([a],[b],[e],[g])および式(7)に例示した[eq₀]=[0],[eq₁]=[0],[eq₂]=[1],[eq₃]=[0],[eq₄]=[0]の場合、以下の秘匿化演算結果[Z]が出力される。

この秘匿化演算結果[Z]では、集合X₀,X₁,X₂の積集合∩_0≦i≦2X_iである{e}に対応する[e]に[1]が対応付けられ、その他の[a][b][g]に[0]が対応付けられている。

＜本実施形態の特徴＞
集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}について、同じ集合X_ｉに属する要素x_i,0,...,x_i,_r(i)-1がそれぞれ表す内容に重複はないことを仮定すると、カウント部１１３－ｗで得られたカウント結果[c_p]に対応する要素の個数c_p（キー情報k_pを表す要素）が集合X₀,…,X_L-1の個数Lと等しいということは、集合X₀,…,X_L-1のそれぞれに同じキー情報k_pを表す要素が１個ずつ含まれていたとに他ならない。そのため、等号判定部１１４－ｗで[eq_p]=[T]（例えば、[1]）となるキー情報k_pは、集合X₀,…,X_L-1の積集合∩_0≦i≦L-1X_iの演算結果である集合の要素である。そのため、互いに対応付けられた秘匿化キー情報[k_p]および等号判定結果[eq_p]を含む秘匿化演算結果[Z]=([eq],[k])のデータ構造は、積集合∩_0≦i≦L-1X_iの演算結果の秘匿化情報を表している。

本実施形態の方法は、集合X₀,…,X_L-1の個数Lが2であっても、3以上であってもそのまま適用でき、３個以上の集合X₀,…,X_L-1の秘匿化情報をも、直接入力として扱うことが可能であり、当該３個以上X₀,…,X_L-1の集合の積集合演算結果の秘匿化情報を直接得ることも可能である。カウント部１１３－ｗの処理は、集合X₀,…,X_L-1を結合したUの秘匿化情報[U]に対して実行されるものであり、Lの値にかかわらず、１度のGroup-by Count等によって直接実行できる。また、等号判定部１１４－ｗで比較されるLはビット数が少ない(log₂(L))ため計算コストも小さい。[c_p]とLとの等号判定にはpに関する順序依存がないため、p=0,...,m-1について並列に計算することが可能であり、高速に計算可能である。特に、本実施形態の方法は、集合X₀,…,X_L-1の個数が大きい場合や、実行時間の長さの影響が大きい環境、例えば遅延の大きなネットワーク環境において特に有効である。

なお、秘匿化演算結果[Z]は、Zを復元するために用いられてもよいし、後続の秘密計算の被演算子として用いられてもよい。

［第２実施形態］
次に、本発明の第２実施形態を説明する。第１実施形態のカウント部１１３－ｗで得られる列[ｋ]=([k₀],...,[k_m-1])はキー情報k₀,...,k_m-1を秘匿したものであり、列[c]=([c₀],...,[c_m-1])は要素x_0,0,...,x₀,_r(0)-1,…,x_L-1,0,...,x_L-1,_r(L-1)-1のうちキー情報k₀,...,k_m-1にそれぞれ一致する要素の個数c₀,...,c_m-1を秘匿したものである。そのため、キー情報k₀,...,k_m-1自体および要素の個数c₀,...,c_m-1自体は秘匿されているが、[k₀],...,[k_m-1]の個数mおよび[c₀],...,[c_m-1]の個数m、すなわち集合X₀,…,X_L-1の要素がm個のグループに区分けされることは秘匿されていない。これを秘匿するためにダミー情報が付加されてもよい。以下では、第1実施形態との相違点を中心に説明し、既に説明した事項については同じ参照番号や記号を用いて説明を簡略化する。

＜構成＞
図１に例示するように、第２実施形態の秘密計算システム２は、ネットワークを通じて通信可能に構成されたＷ個の秘密計算装置２１－０，…，２１－（Ｗ－１）を有する。ただし、Ｗは１以上の整数である。例えば、秘密計算装置２１－０，…，２１－（Ｗ－１）が秘密分散に基づく秘密計算を行う場合にはＷは２以上の整数であり、準同型暗号に基づく秘密計算を行う場合にはＷは１以上の整数である。

図２に例示するように、秘密計算装置２１－ｗ（ただし、ｗ＝０，…，Ｗ－１）は、入力部１１１－ｗ、結合部１１２－ｗ、カウント部２１３－ｗ、等号判定部２１４－ｗ、出力フラグ付与部２１５－ｗ、制御部１１８－ｗ、および記憶部１１９－ｗを有する。秘密計算装置２１－ｗは、制御部１１８－ｗの制御に基づいて各処理を実行し、秘密計算装置１１－ｗへ入力されたデータ、および各処理で得られたデータは記憶部１１９－ｗに格納され、必要に応じて読み出されて他の処理に用いられる。

＜処理＞
秘密計算装置２１－ｗの入力部１１１－ｗには、L個の集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}の秘匿化情報[X₀],...,[X_L-1]が入力される（ステップＳ１１１－ｗ）。

[X₀],...,[X_L-1]は結合部１１２－ｗに入力される。結合部１１２－ｗは、[X₀],...,[X_L-1]の要素を結合した秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]の列[U]を得て出力する（ステップＳ１１２－ｗ）。

カウント部２１３－ｗには列[U]が入力される。カウント部２１３－ｗは、列[U]の秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]を用い、秘密計算によって、列([f],[k],[c])を得て出力する。列[f]は、m個の有効フラグ[f₀],...,[f_m-1]およびn-m個のダミーフラグ[f_m],...,[f_n-1]を含む列であり、f₀,...,f_m-1はB₁であり、f_m,...,f_n-1はB₀であり、B₁およびB₀が互いに異なる。ここで、nはmよりも大きな整数である。列[k]は、m個の秘匿化キー情報[k₀],...,[k_m-1]およびn-m個のダミー情報[k_m],...,[k_n-1]を含む列である。ダミー情報[k_m],...,[k_n-1]に対応するk_m,...,k_n-1のそれぞれは、キー情報k₀,...,k_m-1のいずれかに一致していてもよいし、キー情報k₀,...,k_m-1のいずれとも一致しなくてもよい。列[c]は、m個のカウント結果[c₀],...,[c_m-1]およびn-m個のダミー情報[c_m],...,[c_n-1]を含む列である。p=0,...,m-1について、有効フラグ[f_p]と秘匿化キー情報[k_p]とカウント結果[c_p]とが互いに対応付けられている。ダミー情報[c_m],...,[c_n-1]に対応するc_m,...,c_n-1はそれぞれLと相違する。また、q=m,...,n-1について、ダミーフラグ[f_q]とダミー情報[k_q]とダミー情報[c_q]とが互いに対応付けられている。例えば、カウント部２１３－ｗは、以下の式(9)の列([f],[k],[c])を得て出力する。
([f],[k],[c])=([B₁],…,[B₁],[B₀],…,[B₀],[k₀],…,[k_m-1],[k_m],…,[k_n-1],[c₀],…,[c_m-1],[c_m],…,[c_n-1])
例えば、カウント部２１３－ｗは、式(2)に示したGroup-by Countによって、以下のように列([f],[k],[c])を得てもよい。
([f],[k],[c])←GroupbyCount([U]) (9)
例えば、m=4かつn=5であり、式(3)に例示した列[U]の場合、式(9)によって以下の列([f],[k],[c])が得られる。
([f],[k],[c])=([1],[1],[1],[1],[0],[a],[b],[e],[g],[*],[2],[2],[3],[1],[*]) (10)
ここで、
[f]=([1],[1],[1],[1],[0]),
[k]=([a],[b],[e],[g],[*]),
[c]=([2],[2],[3],[1],[*])
であり、[*]はダミー情報を表す。
列[k]=([k₀],...,[k_m-1],[k_m],...,[k_n-1])は出力フラグ付与部２１５－ｗに送られ、列[c]=([c₀],...,[c_m-1],[c_m],...,[c_n-1])は等号判定部２１４－ｗに送られる（ステップＳ２１３－ｗ）。

等号判定部２１４－ｗには、[X₀],...,[X_L-1]の個数Lおよび列[c]=([c₀],...,[c_m-1],[c_m],...,[c_n-1])が入力される。等号判定部２１４－ｗは、列([f],[k],[c])を用い、秘密計算によって、等号判定結果[eq₀],...,[eq_m-1]およびダミー情報[eq_m],...,[eq_n-1]を得、これらを含む列[eq]=([eq₀],...,[eq_m-1],[eq_m],...,[eq_n-1])を得て出力する。p=0,...,m-1についての[eq₀],...,[eq_m-1]は第１実施形態と同一である。q=m,...,n-1についての[eq_m],...,[eq_n-1]は、eq_m,...,eq_n-1の秘匿化情報である。ただし、c_q=Lのときeq_q=Tであり、c_q=Lでないときにeq_q=Fであり、q=m,...,n-1についてのTおよびFはp=0,...,m-1についてのものと同一であり、TおよびFが互いに異なる。前述のように、c_m,...,c_n-1はそれぞれLと一致しないため、eq_m=...=eq_n-1=Fであり、([eq_m],...,[eq_n-1])=([F],...,[F])である。
例えば、等号判定部２１４－ｗは、u=0,...,n-1について（すなわち、[c_u]∈[c]について）、以下の計算を行う（例えば、u=0,...,n-1について並列に計算を行う）。
[eq_u]←E_Q([c_u],L)
例えば、式(10)に例示した列[c]の場合、T=1かつF=0とすると、以下の式(11)に示す等号判定結果が得られる。
[eq₀]=[0],[eq₁]=[0],[eq₂]=[1],[eq₃]=[0],[eq₄]=[0],[eq₅]=[0] (11)
等号判定結果[eq₀],...,[eq_n-1]の列[eq]は出力フラグ付与部２１５－ｗに送られる（ステップＳ２１４－ｗ）。

出力フラグ付与部２１５－ｗには、列[k]=([k₀],...,[k_n-1])および列[eq]=([eq₀],...,[eq_n-1])が入力される。出力フラグ付与部２１５－ｗは、p=0,...,m-1について互いに対応付けられた秘匿化キー情報[k_p]および等号判定結果[eq_p]、および、q=m,...,n-1について互いに対応付けられたダミー情報[k_q]およびダミー情報[eq_q]を含む秘匿化演算結果[Z]=([eq],[k])を出力する。例えば、出力フラグ付与部２１５－ｗは、以下の秘匿化演算結果[Z]を出力する。

例えば、式(10)に例示した[k]=([a],[b],[e],[g],[*])および式(11)に例示した[eq₀]=[0],[eq₁]=[0],[eq₂]=[1],[eq₃]=[0],[eq₄]=[0],[eq₅]=[0]の場合、以下の秘匿化演算結果[Z]が出力される。

この秘匿化演算結果[Z]では、集合X₀,X₁,X₂の積集合∩_0≦i≦2X_iである{e}に対応する[e]に[1]が対応付けられ、その他の[a][b][g][*]に[0]が対応付けられている。

＜本実施形態の特徴＞
集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}について、同じ集合X_ｉに属する要素x_i,0,...,x_i,_r(i)-1がそれぞれ表す内容に重複はないことを過程すると、カウント部２１３－ｗで得られたカウント結果[c_p]（ただし、p=0,...,m-1）に対応する要素の個数c_p（キー情報k_pを表す要素）が集合X₀,…,X_L-1の個数Lと等しいということは、集合X₀,…,X_L-1のそれぞれに同じキー情報k_pを表す要素が１個ずつ含まれていたとに他ならない。また、ダミー情報[c_m],...,[c_n-1]に対応するc_m,...,c_n-1はそれぞれLと相違する。そのため、等号判定部２１４－ｗで[eq_u]=[T]（ただし、u=0,...,n-1）となるキー情報k_uは、集合X₀,…,X_L-1の積集合∩_0≦i≦L-1X_iの演算結果である集合の要素である。また、ダミー情報[k_m],...,[k_n-1]に対応するk_m,...,k_n-1のそれぞれは、集合X₀,…,X_L-1の実際のキー情報k₀,...,k_m-1のいずれとも一致しない。そのため、互いに対応付けられた秘匿化キー情報[k_u]および等号判定結果[eq_u]を含む秘匿化演算結果[Z]=([eq],[k])のデータ構造は、積集合∩_0≦i≦L-1X_iの演算結果の秘匿化情報を表している。

本実施形態の方法は、集合X₀,…,X_L-1の個数Lが2であっても、3以上であってもそのまま適用でき、３個以上の集合X₀,…,X_L-1の秘匿化情報をも、直接入力として扱うことが可能であり、当該３個以上X₀,…,X_L-1の集合の積集合演算結果の秘匿化情報を直接得ることも可能である。カウント部２１３－ｗの処理は、集合X₀,…,X_L-1を結合したUの秘匿化情報[U]に対して実行されるものであり、Lの値にかかわらず、１度のGroup-by Count等によって直接実行できる。また、等号判定部２１４－ｗで比較されるLはビット数が少ない(log₂(L))ため計算コストも小さい。[c_u]とLとの等号判定にはuに関する順序依存がないため、u=0,...,n-1について並列に計算することが可能であり、高速に計算可能である。本実施形態の方法も、集合X₀,…,X_L-1の個数が大きい場合や、実行時間の長さの影響が大きい環境、例えば遅延の大きなネットワーク環境において特に有効である。さらに、本実施形態で得られる列([f],[k],[c])、列[eq]、秘匿化演算結果[Z]は、いずれもダミー情報を含み、集合X₀,…,X_L-1の要素がm個のグループに区分けされることも秘匿されている。よって、本実施形態の方法はより安全性が高い。

なお、秘匿化演算結果[Z]は、Zを復元するために用いられてもよいし、後続の秘密計算の被演算子として用いられてもよい。例えば、参考文献５等に開示された方法によって秘匿化演算結果[Z]からダミー情報に対応する無効な要素（行）を削除し、得られた結果を他のデータベース演算に利用してもよい。
参考文献５：須藤弘貴, 五十嵐大，“行数のみ開示する秘密計算データベース管理システムの実装と評価，” In SCIS2021, pp. 1-6, 2021.

［ハードウェア構成］
各実施形態における秘密計算装置１１－ｗ，２１－ｗ，は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。すなわち、各実施形態における秘密計算装置１１－ｗ，２１－ｗは、例えば、それぞれが有する各部を実装するように構成された処理回路（processing circuitry）を有する。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、単独で処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。

図４は、各実施形態における秘密計算装置１１－ｗ，２１－ｗのハードウェア構成を例示したブロック図である。図４に例示するように、この例の秘密計算装置１１－ｗ，２１－ｗは、ＣＰＵ（Central Processing Unit）１０ａ、入力部１０ｂ、出力部１０ｃ、ＲＡＭ（Random Access Memory）１０ｄ、ＲＯＭ（Read Only Memory）１０ｅ、補助記憶装置１０ｆ及びバス１０ｇを有している。この例のＣＰＵ１０ａは、制御部１０ａａ、演算部１０ａｂ及びレジスタ１０ａｃを有し、レジスタ１０ａｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１０ｂは、データが入力される入力端子、キーボード、マウス、タッチパネル等である。また、出力部１０ｃは、データが出力される出力端子、ディスプレイ、所定のプログラムを読み込んだＣＰＵ１０ａによって制御されるＬＡＮカード等である。また、ＲＡＭ１０ｄは、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、所定のプログラムが格納されるプログラム領域１０ｄａ及び各種データが格納されるデータ領域１０ｄｂを有している。また、補助記憶装置１０ｆは、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、所定のプログラムが格納されるプログラム領域１０ｆａ及び各種データが格納されるデータ領域１０ｆｂを有している。また、バス１０ｇは、ＣＰＵ１０ａ、入力部１０ｂ、出力部１０ｃ、ＲＡＭ１０ｄ、ＲＯＭ１０ｅ及び補助記憶装置１０ｆを、情報のやり取りが可能なように接続する。ＣＰＵ１０ａは、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１０ｆのプログラム領域１０ｆａに格納されているプログラムをＲＡＭ１０ｄのプログラム領域１０ｄａに書き込む。同様にＣＰＵ１０ａは、補助記憶装置１０ｆのデータ領域１０ｆｂに格納されている各種データを、ＲＡＭ１０ｄのデータ領域１０ｄｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１０ｄ上のアドレスがＣＰＵ１０ａのレジスタ１０ａｃに格納される。ＣＰＵ１０ａの制御部１０ａａは、レジスタ１０ａｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１０ｄ上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１０ａｂに順次実行させ、その演算結果をレジスタ１０ａｃに格納していく。このような構成により、秘密計算装置１１－ｗ，２１－ｗの機能構成が実現される。

上述のプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。

このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ－ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。上述のように、このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

各実施形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

なお、本発明は上述の実施形態に限定されるものではない。例えば、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

本発明は、秘密計算によって、2個以上の集合に対する積和演算を行う用途に適用することができる。例えば、秘密計算によってRDBMS(Relational DataBase Management System)で積和演算を行う用途に本発明を利用することができる。

１ 秘密計算システム
１１－ｗ，２１－ｗ 秘密計算装置
１１３－ｗ，カウント部２１３－ｗ
１１４－ｗ，２１４－ｗ 等号判定部
１１５－ｗ，２１５－ｗ 出力フラグ付与部

Claims (7)

1. L個の集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}を秘匿化したまま、前記集合X₀,…,X_L-1の積集合の秘匿化情報を表す秘匿化演算結果を得る秘密計算装置であって、
   Lが２以上の整数であり、i=0,...,L-1であり、r(i)が１以上の整数であり、j(i)=0,...,r(i)-1であり、mが１以上の整数であり、k₀,...,k_m-1が互いに異なるキー情報であり、p=0,...,m-1であり、[α]がαの秘匿化情報であり、
   (A)各要素x_i,j(i)は前記キー情報k₀,...,k_m-1の何れかを表し、要素x_0,0,...,x₀,_r(0)-1,…,x_L-1,0,...,x_L-1,_r(L-1)-1のうちキー情報k_pを表す要素の個数がc_pであり、
   秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]を用い、秘密計算によって、カウント結果[c₀],...,[c_m-1]を得るカウント部と、
   (B)c_p=Lのときeq_p=Tであり、c_p=Lでないときにeq_p=Fであり、TおよびFが互いに異なり、
   前記カウント結果[c₀],...,[c_m-1]を用い、秘密計算によって、等号判定結果[eq₀],...,[eq_m-1]を得る等号判定部と、
   (C)互いに対応付けられた秘匿化キー情報[k_p]および等号判定結果[eq_p]を含む前記秘匿化演算結果を出力する出力フラグ付与部と、
   を有する秘密計算装置。
2. 請求項１の秘密計算装置であって、
   前記カウント部は、
   前記秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]を用い、秘密計算によって、さらに秘匿化キー情報[k₀],...,[k_m-1]を得る、秘密計算装置。
3. 請求項２の秘密計算装置であって、
   nがmよりも大きな整数であり、
   (A)前記カウント部は、列([f],[k],[c])を得、
   列[f]は、m個の有効フラグ[f₀],...,[f_m-1]およびn-m個のダミーフラグ[f_m],...,[f_n-1]を含む列であり、f₀,...,f_m-1はB₁であり、f_m,...,f_n-1はB₀であり、B₁およびB₀が互いに異なり、
   列[k]は、m個の秘匿化キー情報[k₀],...,[k_m-1]およびn-m個のダミー情報[k_m],...,[k_n-1]を含む列であり、
   列[c]は、m個の前記カウント結果[c₀],...,[c_m-1]およびn-m個のダミー情報[c_m],...,[c_n-1]を含む列であり、
   p=0,...,m-1について、有効フラグ[f_p]と秘匿化キー情報[k_p]とカウント結果[c_p]とが互いに対応付けられ、
   q=m,...,n-1について、ダミーフラグ[f_q]とダミー情報[k_q]とダミー情報[c_q]とが互いに対応付けられ、
   (B)前記等号判定部は、前記列([f],[k],[c])を用い、秘密計算によって、前記等号判定結果[eq₀],...,[eq_m-1]およびダミー情報[eq_m],...,[eq_n-1]を得、
   (C)前記出力フラグ付与部は、p=0,...,m-1について互いに対応付けられた前記秘匿化キー情報[k_p]および前記等号判定結果[eq_p]、および、q=m,...,n-1について互いに対応付けられたダミー情報[k_q]およびダミー情報[eq_q]を含む、前記秘匿化演算結果を出力する、秘密計算装置。
4. 請求項１から３の何れかの秘密計算装置であって、
   Ｌが３以上の整数である、秘密計算装置。
5. 請求項１から４の何れかの秘密計算装置を有する秘密計算システム。
6. L個の集合X₀={x_0,0,...,x₀,_r(0)-1},…,X_L-1={x_L-1,0,...,x_L-1,_r(L-1)-1}を秘匿化したまま、前記集合X₀,…,X_L-1の積集合の秘匿化情報を表す秘匿化演算結果を得る秘密計算装置の秘密計算方法であって、
   Lが２以上の整数であり、i=0,...,L-1であり、r(i)が１以上の整数であり、j(i)=0,...,r(i)-1であり、mが１以上の整数であり、k₀,...,k_m-1が互いに異なるキー情報であり、p=0,...,m-1であり、[α]がαの秘匿化情報であり、
   (A)各要素x_i,j(i)は前記キー情報k₀,...,k_m-1の何れかを表し、要素x_0,0,...,x₀,_r(0)-1,…,x_L-1,0,...,x_L-1,_r(L-1)-1のうちキー情報k_pを表す要素の個数がc_pであり、
   カウント部において、秘匿化要素[x_0,0],...,[x₀,_r(0)-1],...,[x_L-1,0],...,[x_L-1,_r(L-1)-1]を用い、秘密計算によって、カウント結果[c₀],...,[c_m-1]を得るカウントステップと、
   (B)c_p=Lのときeq_p=Tであり、c_p=Lでないときにeq_p=Fであり、TおよびFが互いに異なり、
   等号判定部において、前記カウント結果[c₀],...,[c_m-1]を用い、秘密計算によって、等号判定結果[eq₀],...,[eq_m-1]を得る等号判定ステップと、
   (C)出力フラグ付与部において、互いに対応付けられた秘匿化キー情報[k_p]および等号判定結果[eq_p]を含む前記秘匿化演算結果を出力する出力フラグ付与ステップと、
   を有する秘密計算方法。
7. 請求項１から４の何れかの秘密計算装置としてコンピュータを機能させるためのプログラム。

Images