(57)【特許請求の範囲】
【請求項１】
クライアント装置とサーバ装置とを有し、
前記クライアント装置は、
B={0,1}, i=0,…,n-1, n≧1とし、κ-1(κ≧2)ビットの第１ランダムビットをWi,0∈Bκ-1とし、κ-1ビットの第２ランダムビットをWi,1∈Bκ-1とし、1ビットの第３ランダムビットをci∈Bとし、前記第３ランダムビットciの反転ビットをci-∈Bとし、前記第１ランダムビットWi,0と前記第３ランダムビットciとの組に対応する秘匿情報PWi,0と、前記第２ランダムビットWi,1と前記反転ビットci-との組に対応する秘匿情報PWi,1とを得るランダム化部と、
前記ランダム化部で得られたすべての前記秘匿値PWi,0,PWi,1(i=0,…,n-1)を前記サーバ装置で特定するためのサーバ用秘匿情報を生成するサーバ用秘匿情報生成部と、
前記ランダム化部で得られた前記秘匿値PWi,0,PWi,1(i=0,…,n-1)のうち、n個の入力ビットa(i)∈B (i=0,…,n-1)にそれぞれ対応する秘匿値PWi,a(i)(i=0,…,n-1)を前記クライアント装置のみで特定するためのクライアント用秘匿情報を生成するクライアント用秘匿情報生成部と、を有し、
前記サーバ装置は、
前記サーバ用秘匿情報から特定される前記秘匿値PWi,0,PWi,1(i=0,…,n-1)を用い、論理回路を構成する論理素子G(L)(L=0,...,Lmax-1, Lmax≧1)に対するs(L)(s(L)≧1)個の入力ビットx(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせと、それに対する出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとが関連付けられた真理値表T(L)を、秘匿値PWp(L),x(p(L)) (p(L)=r(L;0),…,r(L;s(L)-1))に対応する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせと、前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bに対応するκ-1ビットの第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと1ビットの第６ランダムビットck(L)∈Bとの排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと、が関連付けられた歪曲真理値表DT(L)に変換し、当該歪曲真理値表DT(L)の集合を含む歪曲回路情報を生成する歪曲回路生成部を有し、
p(L)∈{0,…,n-1}の場合、前記秘匿値PWp(L),x(p(L))が前記サーバ用秘匿情報から特定される前記秘匿値PWi,0,PWi,1(i=0,…,n-1)の何れかであり、かつ、前記第４ランダムビットcp(L)∈Bが前記第３ランダムビットci(i=p(L))であり、かつ、前記反転ビットcp(L)-∈Bが前記反転ビットci-(i=p(L))であり、
p(L)が{0,…,n-1}の要素でない場合、前記秘匿値PWp(L),x(p(L))が別の論理素子G(PL)(PL≠L, PL=0,...,Lmax-1)に対応する歪曲回路情報の第５ランダムビットWk(PL),g(L;x(r(PL)),…,x(r(PL)+s(PL)-1))∈Bκ-1と第６ランダムビットck(PL)∈Bとの組に対応する値であり、かつ、前記第４ランダムビットcp(L)∈Bが前記第６ランダムビットck(PL)∈Bであり、かつ、前記反転ビットcp(L)-∈Bが前記第６ランダムビットck(PL)∈Bの反転ビットであり、
前記クライアント装置は、
歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに対応する情報を用いて前記歪曲真理値表DT(L)を検索し、前記歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに一致する前記第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせに対応付けられた前記排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを得る歪曲素子演算処理を各L(L=0,...,Lmax-1)について実行する歪曲回路計算部を有し、
p(L)∈{0,…,n-1}の場合、前記歪曲入力ビットy(p(L))∈Bが、前記クライアント用秘匿情報から特定される秘匿値PWi,a(i)(i= p(L))に対応する前記第３ランダムビットci又は前記反転ビットci-であり、
p(L)が{0,…,n-1}の要素でない場合、前記歪曲入力ビットy(p(L))∈Bが、別の歪曲真理値表DT(PL)に対する歪曲素子演算処理で得られた排他的論理和xor(x(r(PL)),…,x(r(PL)+s(PL)-1))である、秘匿データ処理システム。
【請求項２】
請求項１の秘匿データ処理システムであって、
前記クライアント用秘匿情報は、前記秘匿値PWi,a(i)(i=0,…,n-1)を共通鍵暗号方式に則って暗号化して得られる暗号文であり、
前記サーバ装置は、
前記サーバ用秘匿情報と前記クライアント用秘匿情報とを記憶する記憶部と、
前記クライアント用秘匿情報を出力する出力部とを有し、
前記クライアント装置は、
前記クライアント用秘匿情報の入力を受け付ける入力部を有し、
前記歪曲回路計算部は、
前記クライアント用秘匿情報を復号するための共通鍵を用い、前記入力部に入力された前記クライアント用秘匿情報から前記秘匿値PWi,a(i)(i=0,…,n-1)を復号する、秘匿データ処理システム。
【請求項３】
請求項２の秘匿データ処理システムであって、
前記クライアント装置は、第１クライアント装置と第２クライアント装置とを有し、
前記第１クライアント装置は、前記ランダム化部と前記サーバ用秘匿情報生成部と前記クライアント用秘匿情報生成部とを有し、
前記第２クライアント装置は、前記入力部と前記歪曲回路計算部とを有する、秘匿データ処理システム。
【請求項４】
請求項３の秘匿データ処理システムであって、
前記第２クライアント装置は、前記論理回路を特定する論理回路情報を出力する論理回路情報出力部を有し、
前記サーバ装置は、前記論理回路情報の入力を受け付ける論理回路情報入力部を有し、
前記論理素子G(L)は、前記論理回路情報によって特定される前記論理回路を構成するものである、秘匿データ処理システム。
【請求項５】
サーバ装置との間で秘匿データ処理を行うクライアント装置であって、
B={0,1}, i=0,…,n-1, n≧1とし、κ-1(κ≧2)ビットの第１ランダムビットをWi,0∈Bκ-1とし、κ-1ビットの第２ランダムビットをWi,1∈Bκ-1とし、1ビットの第３ランダムビットをci∈Bとし、前記第３ランダムビットciの反転ビットをci-∈Bとし、前記第１ランダムビットWi,0と前記第３ランダムビットciとの組に対応する秘匿情報PWi,0と、前記第２ランダムビットWi,1と前記反転ビットci-との組に対応する秘匿情報PWi,1とを得るランダム化部と、
前記ランダム化部で得られたすべての前記秘匿値PWi,0,PWi,1(i=0,…,n-1)を前記サーバ装置で特定するためのサーバ用秘匿情報を生成するサーバ用秘匿情報生成部と、
前記ランダム化部で得られた前記秘匿値PWi,0,PWi,1(i=0,…,n-1)のうち、n個の入力ビットa(i)∈B (i=0,…,n-1)にそれぞれ対応する秘匿値PWi,a(i)(i=0,…,n-1)を前記クライアント装置のみで特定するためのクライアント用秘匿情報を生成するクライアント用秘匿情報生成部と、
論理回路を構成する論理素子G(L)(L=0,...,Lmax-1, Lmax≧1)にs(L)(s(L)≧1)個の入力ビットx(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))が入力された場合に当該論理素子G(L)から出力される出力ビットをg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとし、秘匿値PWp(L),x(p(L))(p(L)=r(L;0),…,r(L;s(L)-1))に対応する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせと、前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bに対応するκ-1ビットの第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと1ビットの第６ランダムビットck(L)∈Bとの排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと、が関連付けられた歪曲真理値表DT(L)の集合を含む情報を歪曲回路情報とし、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに対応する情報を用いて前記歪曲真理値表DT(L)を検索し、前記歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに一致する前記第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせに対応付けられた前記排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを得る歪曲素子演算処理を各L(L=0,...,Lmax-1)について実行する歪曲回路計算部と、を有し、
p(L)∈{0,…,n-1}の場合、前記秘匿値PWp(L),x(p(L))が前記サーバ用秘匿情報から特定される前記秘匿値PWi,0,PWi,1(i=0,…,n-1)の何れかであり、かつ、前記第４ランダムビットcp(L)∈Bが前記第３ランダムビットci(i=p(L))であり、かつ、前記反転ビットcp(L)-∈Bが前記反転ビットci-(i=p(L))であり、かつ、前記歪曲入力ビットy(p(L))∈Bが、前記クライアント用秘匿情報から特定される秘匿値PWi,a(i)(i=p(L))に対応する前記第３ランダムビットci又は前記反転ビットci-であり、
p(L)が{0,…,n-1}の要素でない場合、前記秘匿値PWp(L),x(p(L))が別の論理素子G(PL)(PL≠L, PL=0,...,Lmax-1)に対応する歪曲回路情報の第５ランダムビットWk(PL),g(L;x(r(PL)),…,x(r(PL)+s(PL)-1))∈Bκ-1と第６ランダムビットck(PL)∈Bとの組に対応する値であり、かつ、前記第４ランダムビットcp(L)∈Bが前記第６ランダムビットck(PL)∈Bであり、かつ、前記反転ビットcp(L)-∈Bが前記第６ランダムビットck(PL)∈Bの反転ビットであり、かつ、前記歪曲入力ビットy(p(L))∈Bが、別の歪曲真理値表DT(PL)に対する歪曲素子演算処理で得られた排他的論理和xor(x(r(PL)),…,x(r(PL)+s(PL)-1))である、クライアント装置。
【請求項６】
サーバ装置との間で秘匿データ処理を行うクライアント装置であって、
B={0,1}, i=0,…,n-1, n≧1とし、κ-1(κ≧2)ビットの第１ランダムビットをWi,0∈Bκ-1とし、κ-1ビットの第２ランダムビットをWi,1∈Bκ-1とし、1ビットの第３ランダムビットをci∈Bとし、前記第３ランダムビットciの反転ビットをci-∈Bとし、前記第１ランダムビットWi,0と前記第３ランダムビットciとの組に対応する秘匿情報PWi,0と、前記第２ランダムビットWi,1と前記反転ビットci-との組に対応する秘匿情報PWi,1とを得るランダム化部と、
前記ランダム化部で得られたすべての前記秘匿値PWi,0,PWi,1(i=0,…,n-1)を前記サーバ装置で特定するためのサーバ用秘匿情報を生成するサーバ用秘匿情報生成部と、
前記ランダム化部で得られた前記秘匿値PWi,0,PWi,1(i=0,…,n-1)のうち、n個の入力ビットa(i)∈B (i=0,…,n-1)にそれぞれ対応する秘匿値PWi,a(i)(i=0,…,n-1)を前記クライアント装置のみで特定するためのクライアント用秘匿情報を生成するクライアント用秘匿情報生成部と、
を有するクライアント装置。
【請求項７】
サーバ装置との間で秘匿データ処理を行うクライアント装置であって、
B={0,1}, i=0,…,n-1, n≧1とし、κ-1(κ≧2)ビットの第１ランダムビットをWi,0∈Bκ-1とし、κ-1ビットの第２ランダムビットをWi,1∈Bκ-1とし、1ビットの第３ランダムビットをci∈Bとし、前記第３ランダムビットciの反転ビットをci-∈Bとし、前記第１ランダムビットWi,0と前記第３ランダムビットciとの組に対応する秘匿情報をPWi,0とし、前記第２ランダムビットWi,1と前記反転ビットci-との組に対応する秘匿情報をPWi,1とし、前記秘匿値PWi,0,PWi,1(i=0,…,n-1)のうち、n個の入力ビットa(i)∈B (i=0,…,n-1)にそれぞれ対応する秘匿値PWi,a(i)(i=0,…,n-1)を前記クライアント装置のみで特定するための情報をクライアント用秘匿情報とし、論理回路を構成する論理素子G(L)(L=0,...,Lmax-1, Lmax≧1)にs(L)(s(L)≧1)個の入力ビットx(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))が入力された場合に当該論理素子G(L)から出力される出力ビットをg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとし、秘匿値PWp(L),x(p(L))(p(L)=r(L;0),…,r(L;s(L)-1))に対応する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせと、前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bに対応するκ-1ビットの第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと1ビットの第６ランダムビットck(L)∈Bとの排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと、が関連付けられた歪曲真理値表DT(L)の集合を含む情報を歪曲回路情報とした場合における、
前記クライアント用秘匿情報の入力を受け付ける入力部と、
歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに対応する情報を用いて前記歪曲真理値表DT(L)を検索し、前記歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに一致する前記第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせに対応付けられた前記排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを得る歪曲素子演算処理を各L(L=0,...,Lmax-1)について実行する歪曲回路計算部とを有し、
p(L)∈{0,…,n-1}の場合、前記秘匿値PWp(L),x(p(L))が前記サーバ用秘匿情報から特定される前記秘匿値PWi,0,PWi,1(i=0,…,n-1)の何れかであり、かつ、前記第４ランダムビットcp(L)∈Bが前記第３ランダムビットci(i=p(L))であり、かつ、前記反転ビットcp(L)-∈Bが前記反転ビットci-(i=p(L))であり、かつ、前記歪曲入力ビットy(p(L))∈Bが、前記クライアント用秘匿情報から特定される秘匿値PWi,a(i)(i=p(L))に対応する前記第３ランダムビットci又は前記反転ビットci-であり、
p(L)が{0,…,n-1}の要素でない場合、前記秘匿値PWp(L),x(p(L))が別の論理素子G(PL)(PL≠L, PL=0,...,Lmax-1)に対応する歪曲回路情報の第５ランダムビットWk(PL),g(L;x(r(PL)),…,x(r(PL)+s(PL)-1))∈Bκ-1と第６ランダムビットck(PL)∈Bとの組に対応する値であり、かつ、前記第４ランダムビットcp(L)∈Bが前記第６ランダムビットck(PL)∈Bであり、かつ、前記反転ビットcp(L)-∈Bが前記第６ランダムビットck(PL)∈Bの反転ビットであり、かつ、前記歪曲入力ビットy(p(L))∈Bが、別の歪曲真理値表DT(PL)に対する歪曲素子演算処理で得られた排他的論理和xor(x(r(PL)),…,x(r(PL)+s(PL)-1))である、クライアント装置。
【請求項８】
請求項１から４の何れかの秘匿データ処理システムが有するサーバ装置。
【請求項９】
クライアント装置で、B={0,1}, i=0,…,n-1, n≧1とし、κ-1(κ≧2)ビットの第１ランダムビットをWi,0∈Bκ-1とし、κ-1ビットの第２ランダムビットをWi,1∈Bκ-1とし、1ビットの第３ランダムビットをci∈Bとし、前記第３ランダムビットciの反転ビットをci-∈Bとし、前記第１ランダムビットWi,0と前記第３ランダムビットciとの組に対応する秘匿情報PWi,0と、前記第２ランダムビットWi,1と前記反転ビットci-との組に対応する秘匿情報PWi,1とを得るランダム化ステップと、
前記ランダム化ステップで得られたすべての前記秘匿値PWi,0,PWi,1(i=0,…,n-1)を前記サーバ装置で特定するためのサーバ用秘匿情報を、前記クライアント装置で生成するサーバ用秘匿情報生成ステップと、
前記ランダム化ステップで得られた前記秘匿値PWi,0,PWi,1(i=0,…,n-1)のうち、n個の入力ビットa(i)∈B (i=0,…,n-1)にそれぞれ対応する秘匿値PWi,a(i)(i=0,…,n-1)を前記クライアント装置のみで特定するためのクライアント用秘匿情報を、前記クライアント装置で生成するクライアント用秘匿情報生成ステップと、
前記サーバ装置で、前記サーバ用秘匿情報から特定される前記秘匿値PWi,0,PWi,1(i=0,…,n-1)を用い、論理回路を構成する論理素子G(L)(L=0,...,Lmax-1, Lmax≧1)に対するs(L)(s(L)≧1)個の入力ビットx(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせと、それに対する出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとが関連付けられた真理値表T(L)を、秘匿値PWp(L),x(p(L))(p(L)=r(L;0),…,r(L;s(L)-1))に対応する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせと、前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bに対応するκ-1ビットの第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと1ビットの第６ランダムビットck(L)∈Bとの排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと、が関連付けられた歪曲真理値表DT(L)に変換し、当該歪曲真理値表DT(L)の集合を含む歪曲回路情報を生成する歪曲回路生成ステップと、
前記クライアント装置で、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに対応する情報を用いて前記歪曲真理値表DT(L)を検索し、前記歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに一致する前記第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせに対応付けられた前記排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は前記出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを得る歪曲素子演算処理を各L(L=0,...,Lmax-1)について実行する歪曲回路計算ステップと、を有し、
p(L)∈{0,…,n-1}の場合、前記秘匿値PWp(L),x(p(L))が前記サーバ用秘匿情報から特定される前記秘匿値PWi,0,PWi,1(i=0,…,n-1)の何れかであり、かつ、前記第４ランダムビットcp(L)∈Bが前記第３ランダムビットci(i=p(L))であり、かつ、前記反転ビットcp(L)-∈Bが前記反転ビットci-(i=p(L))であり、かつ、前記歪曲入力ビットy(p(L))∈Bが、前記クライアント用秘匿情報から特定される秘匿値PWi,a(i)(i=p(L))に対応する前記第３ランダムビットci又は前記反転ビットci-であり、
p(L)が{0,…,n-1}の要素でない場合、前記秘匿値PWp(L),x(p(L))が別の論理素子G(PL)(PL≠L, L=0,...,Lmax-1)に対応する歪曲回路情報の第５ランダムビットWk(PL),g(L;x(r(PL)),…,x(r(PL)+s(PL)-1))∈Bκ-1と第６ランダムビットck(PL)∈Bとの組に対応する値であり、かつ、前記第４ランダムビットcp(L)∈Bが前記第６ランダムビットck(PL)∈Bであり、かつ、前記反転ビットcp(L)-∈Bが前記第６ランダムビットck(PL)∈Bの反転ビットであり、かつ、前記歪曲入力ビットy(p(L))∈Bが、別の歪曲真理値表DT(PL)に対する歪曲素子演算処理で得られた排他的論理和xor(x(r(PL)),…,x(r(PL)+s(PL)-1))である、秘匿データ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘匿データを処理する技術に関し、特に秘匿回路計算技術に関する。
【背景技術】
【０００２】
秘匿回路計算では、入力データや論理回路が秘匿されたまま、当該入力データ及び論理回路に対応する論理演算処理が実行される。秘匿回路計算の従来技術として、非特許文献１に記載された２パーティ秘匿回路計算方式、非特許文献２に記載された３パーティ秘匿関数計算方式、及び非特許文献３に記載されたマルチパーティ秘匿回路計算方式などがある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】柴田賢介, 千田浩司, 五十嵐大, 山本太郎, 高橋克巳，“表計算ソフトをフロントエンドとした委託型2パーティ秘匿回路計算システム”， CSS2009, 2009.
【非特許文献２】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳， “軽量検証可能3 パーティ秘匿関数計算の再考”， CSS2010, 2010.
【非特許文献３】千田浩司, 谷口展郎, 山本剛, 岡崎聖人, 塩野入理, 金井敦， “エルガマル暗号に基づく秘匿回路計算の実装と応用”，CSS2005, pp. 475 - 480, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に開示された方式の処理効率は高い。しかし、非特許文献１に開示された方式はsemi-honestモデルに基づいているため、この方式では計算者の不正によってデータの秘匿性が損なわれる場合がある。非特許文献２に開示された方式の処理効率は高く、この方式では計算者によって行われた改ざんを検知できる。しかし、非特許文献２に開示された方式の実行には三者（３パーティ）が必要である。非特許文献３に開示された方式は二者（２パーティ）で実行でき、この方式では計算者よって行われた改ざんなどの不正も検知できる。しかし、非特許文献３に開示された方式では、処理全体で公開鍵暗号処理が実行されるため処理効率が悪い。
【０００５】
本発明が解決しようとする課題は、処理効率及び安全性が高い秘匿回路計算を二者で実行できる技術を提供することである。
【課題を解決するための手段】
【０００６】
クライアント装置は、B={0,1}, i=0,…,n-1, n≧1とし、κ-1(κ≧2)ビットの第１ランダムビットをWi,0∈Bκ-1とし、κ-1ビットの第２ランダムビットをWi,1∈Bκ-1とし、1ビットの第３ランダムビットをci∈Bとし、第３ランダムビットciの反転ビットをci-∈Bとし、第１ランダムビットWi,0と第３ランダムビットciとの組に対応する秘匿情報PWi,0と、第２ランダムビットWi,1と反転ビットci-との組に対応する秘匿情報PWi,1とを得る。クライアント装置は、得られたすべての秘匿値PWi,0,PWi,1(i=0,…,n-1)をサーバ装置で特定するためのサーバ用秘匿情報を生成する。クライアント装置は、得られた秘匿値PWi,0,PWi,1(i=0,…,n-1)のうち、n個の入力ビットa(i)∈B (i=0,…,n-1)にそれぞれ対応する秘匿値PWi,a(i)(i=0,…,n-1)をクライアント装置のみで特定するためのクライアント用秘匿情報を生成する。
【０００７】
サーバ装置は、サーバ用秘匿情報から特定される秘匿値PWi,0,PWi,1(i=0,…,n-1)を用い、論理回路を構成する論理素子G(L)(L=0,...,Lmax-1)に対するs(L)(s(L)≧1)個の入力ビットx(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせと、それに対する出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとが関連付けられた真理値表T(L)を、秘匿値PWp(L),x(p(L))(p(L)=r(L;0),…,r(L;s(L)-1))に対応する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせと、出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bに対応するκ-1ビットの第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと1ビットの第６ランダムビットck(L)∈Bとの排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと、が関連付けられた歪曲真理値表DT(L)を生成し、当該歪曲真理値表DT(L)の集合を含む歪曲回路情報を生成する。
【０００８】
クライアント装置は、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに対応する情報を用いて歪曲真理値表DT(L)を検索し、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに一致する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせに対応付けられた排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを得る歪曲素子演算処理を各L(L=0,...,Lmax-1)について実行する。
【０００９】
ただし、p(L)∈{0,…,n-1}の場合、秘匿値PWp(L),x(p(L))がサーバ用秘匿情報から特定される秘匿値PWi,0,PWi,1(i=0,…,n-1)の何れかであり、かつ、第４ランダムビットcp(L)∈Bが第３ランダムビットci(i=p(L))であり、かつ、反転ビットcp(L)-∈Bが反転ビットci-(i=p(L))であり、かつ、歪曲入力ビットy(p(L))∈Bが、クライアント用秘匿情報から特定される秘匿値PWi,a(i)(i=p(L))に対応する第３ランダムビットci又は反転ビットci-である。p(L)が{0,…,n-1}の要素でない場合、秘匿値PWp(L),x(p(L))が別の論理素子G(PL)(PL≠L, L=0,...,Lmax-1)に対応する歪曲回路情報の第５ランダムビットWk(PL),g(L;x(r(PL)),…,x(r(PL)+s(PL)-1))∈Bκ-1と第６ランダムビットck(PL)∈Bとの組に対応する値であり、かつ、第４ランダムビットcp(L)∈Bが第６ランダムビットck(PL)∈Bであり、かつ、反転ビットcp(L)-∈Bが第６ランダムビットck(PL)∈Bの反転ビットであり、かつ、歪曲入力ビットy(p(L))∈Bが、別の歪曲真理値表DT(PL)に対する歪曲素子演算処理で得られた排他的論理和xor(x(r(PL)),…,x(r(PL)+s(PL)-1))である。
【発明の効果】
【００１０】
本発明では、処理効率及び安全性が高い秘匿回路計算を二者で実行できる。
【図面の簡単な説明】
【００１１】
【図１】図１は、第１実施形態の秘匿データ処理システムの機能構成を説明するための図である。
【図２】図２は、第１実施形態の保存フェーズの処理を説明するための図である。
【図３】図３は、第１実施形態の計算フェーズの処理を説明するための図である。
【図４】図４は、論理回路の一例を説明するための図である。
【図５】図５は、第２実施形態の秘匿データ処理システムの機能構成を説明するための図である。
【図６】図６は、第３実施形態の秘匿データ処理システムの機能構成を説明するための図である。
【図７】図７は、第３実施形態の保存フェーズの処理を説明するための図である。
【図８】図８は、第３実施形態の計算フェーズの処理を説明するための図である。
【図９】図９は、本実施形態の性能と従来技術の性能との関係を説明するための図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施形態を説明する。
〔第１実施形態〕
＜構成＞
図１に例示するように、本形態の秘匿データ処理システム１は、クライアント装置１１０とサーバ装置１２０を有する。クライアント装置１１０は、入力部１１１と送信部１１２と受信部１１３と制御部１１５とランダム化部１１６とサーバ用秘匿情報生成部１１７とクライアント用秘匿情報生成部１１８と歪曲回路計算部１１９とを有する。サーバ装置１２０は、送信部１２２と受信部１２３と記憶部１２４と制御部１２５と歪曲回路生成部１２６とを有する。
【００１３】
クライアント装置１１０及びサーバ装置１２０は、例えばそれぞれ、特別なプログラムが、CPU(central processing unit)，RAM(random-access memory)，ROM(read-only memory)等を有する公知のコンピュータ又は専用のコンピュータに読み込まれ、実行されることで構築される特別な装置である。以下では説明を省略するが、この例の場合、クライアント装置１１０やサーバ装置１２０の各処理部（「***部」）で受信されたデータや得られたデータは、クライアント装置１１０やサーバ装置１２０の一時メモリ（図示せず）に逐一格納される。一時メモリに格納されたデータは、必要に応じて読み出され、クライアント装置１１０やサーバ装置１２０の処理部に入力され、そこでの演算処理に利用される。なお、クライアント装置１１０やサーバ装置１２０の処理部の少なくとも一部がハードウェアによって構成されてもよい。制御部１１５はクライアント装置１１０の処理を制御し、制御部１２５はサーバ装置１２０の処理を制御する。また、クライアント装置１１０はサーバ装置１２０に情報を送信でき、サーバ装置１２０はクライアント装置１１０に情報を送信できる。
【００１４】
＜処理＞
本形態の秘匿データ処理システム１によって行われる処理は、クライアント装置１１０がサーバ装置１２０にデータを預託する保存フェーズと、クライアント装置１１０とサーバ装置１２０とが協調して計算を行う計算フェーズとを含む。以下では、まず保存フェーズを説明し、次に計算フェーズを説明する。
【００１５】
＜保存フェーズ＞
図２に例示するように、クライアント装置１１０の入力部１１１にn(n≧1)個の入力ビットa(i)∈B (i=0,…,n-1, B={0,1})が入力される。入力ビットa(i) (i=0,…,n-1)はクライアント用秘匿情報生成部１１８に送られる（ステップＳ１０１）。
【００１６】
ランダム化部１１６は、各i=0,…,n-1に対し、以下のような、κ-1(κ≧2)ビットの第１ランダムビットWi,0∈Bκ-1、κ-1ビットの第２ランダムビットWi,1∈Bκ-1、1ビットの第３ランダムビットci∈B、及び第３ランダムビットciの反転ビットci-∈B（ci-=1(+)ci）を生成する。
Wi,0, Wi,1∈RBκ-1
ci∈RB
ただし、c∈RBは集合Bからランダムにcを選択することを表し、(+)は排他的論理和演算子を表す（ステップＳ１０２）。
【００１７】
ランダム化部１１６は、各i=0,…,n-1に対し、以下のような、第１ランダムビットWi,0と第３ランダムビットciとの組に対応する秘匿情報PWi,0と、第２ランダムビットWi,1と反転ビットci-との組に対応する秘匿情報PWi,1とを生成して出力する。
PWi,0=(Wi,0, ci)
PWi,1=(Wi,1, ci-)
秘匿情報PWi,0, PWi,1(i=0,…,n-1)は、サーバ用秘匿情報生成部１１７及びクライアント用秘匿情報生成部１１８に入力される（ステップＳ１０３）。
【００１８】
サーバ用秘匿情報生成部１１７は、以下のような、ランダム化部１１６で得られたすべての秘匿値PWi,0,PWi,1(i=0,…,n-1)をサーバ装置１２０で特定するためのサーバ用秘匿情報Es(Ds)を生成する。ただし、{PWi,0,PWi,1}i=0,…,n-1は、i=0,…,n-1に対応するPWi,0,PWi,1を要素とする集合を意味する。
Es(Ds)
Ds={PWi,0,PWi,1}i=0,…,n-1
例えば、サーバ用秘匿情報生成部１１７は、Dsを暗号化して得られるサーバ装置１２０で復号可能な暗号文をサーバ用秘匿情報Es(Ds)とする。この暗号文を復号するための鍵はサーバ装置１２０の歪曲回路生成部１２６に設定されている。なお、サーバ装置１２０がサーバ用秘匿情報Es(Ds)を復号してDsを得ることができるのであれば、Dsを暗号化するための暗号化方式は限定されない。しかし一般に、共通鍵暗号方式を用いてDsを暗号化するための演算量は、公開鍵暗号方式を用いてDsを暗号化するための演算量よりも小さい。そのため、好ましくは、共通鍵暗号方式を用いてDsを暗号化して得られる暗号文がサーバ用秘匿情報Es(Ds)とされる。或いは、安全な通信路（セキュアチャネル）を介してクライアント装置１１０からサーバ装置１２０に情報を送信できるのであれば、この安全な通信路を経由してクライアント装置１１０からサーバ装置１２０にDsを送信するための情報が、サーバ用秘匿情報Es(Ds)とされてもよい。安全な通信路は、クライアント装置１１０とサーバ装置１２０との間の専用通信回線であってもよいし、通信情報が暗号化されるように設定された通信路であってもよい（ステップＳ１０４）。
【００１９】
クライアント用秘匿情報生成部１１８は、以下のような、ランダム化部１１６で得られた秘匿値PWi,0,PWi,1(i=0,…,n-1)のうち、n個の入力ビットa(i)∈B (i=0,…,n-1)にそれぞれ対応する秘匿値PWi,a(i)(i=0,…,n-1)をクライアント装置１１０のみで特定するためのクライアント用秘匿情報Ec(Dc)を生成する。ただし、{PWi,a(i)}i=0,…,n-1は、i=0,…,n-1に対応するPWi,a(i)を要素とする集合を意味する。
Ec(Dc)
Dc={PWi,a(i)}i=0,…,n-1
例えば、クライアント用秘匿情報生成部１１８は、Dcを暗号化して得られる、クライアント装置１１０のみが復号可能な暗号文をクライアント用秘匿情報Ec(Dc)とする。例えばクライアント用秘匿情報は、共通鍵暗号方式に則ってDcを暗号化して得られる暗号文である。この場合のクライアント用秘匿情報生成部１１８は、クライアント装置１１０の共通鍵を用い、共通鍵暗号方式に則ってDcを暗号化してクライアント用秘匿情報Ec(Dc)を生成する。この共通鍵は歪曲回路計算部１１９でも利用可能であり、歪曲回路計算部１１９はこの共通鍵を用いてクライアント用秘匿情報Ec(Dc)を復号できる（ステップＳ１０５）。
【００２０】
ステップＳ１０４で得られたサーバ用秘匿情報Es(Ds)及びクライアント用秘匿情報Ec(Dc)は送信部１１２に入力される。送信部１１２は、サーバ用秘匿情報Es(Ds)及びクライアント用秘匿情報Ec(Dc)をサーバ装置１２０に送信する（ステップＳ１０６）。
【００２１】
サーバ用秘匿情報Es(Ds)及びクライアント用秘匿情報Ec(Dc)は、サーバ装置１２０の受信部１２３で受信され（ステップＳ１０７）、記憶部１２４に記憶される（ステップＳ１０８）。
【００２２】
＜計算フェーズ＞
図３に例示するように、クライアント装置１１０の入力部１１１に、Lmax(Lmax≧1)個の論理素子G(L)(L=0,...,Lmax-1)から構成される論理回路を表す論理回路情報ＬＣが入力される。論理素子G(L)は、s(L)(s(L)≧1)個の入力ビットx(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))に対し、論理演算結果を表す出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを出力する素子である。gはBs(L)の元をBの元に写す関数であり、論理素子G(L)の処理を表す（g: Bs(L)→B）。論理素子G(L)の例は、ＡＮＤゲート、ＯＲゲート、ＸＯＲゲート、ＮＯＴゲートなどである。論理回路情報ＬＣの例は、論理素子G(L)(L=0,...,Lmax-1)に対応する真理値表T(L)からなる集合と、論理素子G(L)(L=0,...,Lmax-1)の入出力関係を表す情報とを含む情報である。真理値表T(L)の例は、s(L)(s(L)≧1)個の入力ビットx(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせと、それに対する出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとが関連付けられた表である。例えば、ＡＮＤゲートである論理素子の真理値表T(L)は以下のようになる。
(x(0),x(1))    g(L;x(0),x(1))
(0,0)          g(L;0,0)=0
(0,1)          g(L;0,1)=0
(1,0)          g(L;1,0)=0
(1,1)          g(L;1,1)=1
入出力関係を表わす情報の例は、論理回路への入力ビットa(i)(i=0,…,n-1)∈Bがどの論理素子G(L1)の入力ビットとなるかを表す情報と、各論理素子G(L)の出力ビットがそれぞれどの論理素子G(L2)の入力ビット又は論理回路からの出力ビットになるかを表す情報とを含む情報である。
【００２３】
図４に例示する論理回路を用いて具体例を示す。図４の論理回路は、ＡＮＤゲートである論理素子G(0),G(2),G(4)、ＮＯＴゲートである論理素子G(1),G(3)、及びＯＲゲートである論理素子G(5)を含み、α,β∈Bを入力としてγ,δ∈Bを出力する半加算回路である。この論理回路はLmax=6、n=6を満たし、この論理回路への入力ビットはa(0)-a(5)(a(0)=a(2)=a(4)=α, a(1)=a(3)=a(5)=β)である。この例の論理回路情報ＬＣは、各論理素子G(0)-G(5)に対応する真理値表T(0)-T(5)からなる集合と論理素子G(0)-G(5)の入出力関係を表す情報とを含む。論理素子G(0)-G(5)の入出力関係を表す情報の例は、a(0), a(1)が論理素子G(0)の入力ビットとなること、a(2)が論理素子G(1)の入力ビットとなること、a(3)が論理素子G(2)の一方の入力ビットとなること、a(4)が論理素子G(4)の一方の入力ビットとなること、a(5)が論理素子G(3)の入力ビットとなること、論理素子G(1)の出力ビットが論理素子G(2)の他方の入力ビットとなること、論理素子G(3)の出力ビットが論理素子G(4)の他方の入力ビットとなること、論理素子G(2)の出力ビットと論理素子G(4)の出力ビットとが論理素子G(5)の入力ビットとなること、論理素子G(0)の出力ビットが論理回路の出力ビットγとなること、及び、論理素子G(5)の出力ビットが論理回路の出力ビットδとなることを表す情報である（ステップＳ１１１）。
【００２４】
論理回路情報ＬＣは送信部１１２に入力され、送信部１１２は論理回路情報ＬＣをサーバ装置１２０に送信する（ステップＳ１１２）。論理回路情報ＬＣは、サーバ装置１２０の受信部１２３で受信され、歪曲回路生成部１２６に入力される（ステップＳ１１３）。
【００２５】
歪曲回路生成部１２６は、記憶部１２４からサーバ用秘匿情報Es(Ds)を読み込み、サーバ用秘匿情報Es(Ds)からDsを復元する。例えば、サーバ用秘匿情報Es(Ds)が暗号文なのであれば、歪曲回路生成部１２６は、鍵を用いてサーバ用秘匿情報Es(Ds)を復号してDs={PWi,0,PWi,1}i=0,…,n-1を得る。或いは、サーバ用秘匿情報Es(Ds)が安全な通信路を介して送信されたのであれば、歪曲回路生成部１２６は、サーバ用秘匿情報Es(Ds)からDs={PWi,0,PWi,1}i=0,…,n-1を得る（ステップＳ１１４）。
【００２６】
記憶部１２４から読み出されたクライアント用秘匿情報Ec(Dc)は送信部１２２に入力される。送信部１２２（「出力部」に相当）は、クライアント用秘匿情報Ec(Dc)をクライアント装置１１０に送信する（ステップＳ１１５）。クライアント用秘匿情報Ec(Dc)は、クライアント装置１１０の受信部１１３（「入力部」に相当）で受信され、歪曲回路計算部１１９に入力される（ステップＳ１１６）。歪曲回路計算部１１９は、クライアント用秘匿情報Ec(Dc)からDc={PWi,a(i)}i=0,…,n-1を復元する。例えば、クライアント用秘匿情報Ec(Dc)が暗号文であれば、歪曲回路計算部１１９は、クライアント用秘匿情報Ec(Dc)を復号してDc={PWi,a(i)}i=0,…,n-1を得る。例えば、クライアント用秘匿情報Ec(Dc)が共通鍵暗号方式の暗号文であれば、歪曲回路計算部１１９は、共通鍵を用いてクライアント用秘匿情報Ec(Dc)を復号してDc={PWi,a(i)}i=0,…,n-1を得る（ステップＳ１１７）。
【００２７】
サーバ装置１２０の歪曲回路生成部１２６は、Ds={PWi,0,PWi,1}i=0,…,n-1を用い、論理回路情報ＬＣが表す各真理値表T(L)(L=0,...,Lmax-1)を歪曲真理値表DT(L)にそれぞれ変換し、歪曲真理値表DT(L)(L=0,...,Lmax-1)の集合を含む歪曲回路情報を生成する。真理値表T(L)に対応する歪曲真理値表DT(L)は、秘匿値PWp(L),x(p(L)) (p(L)=r(L;0),…,r(L;s(L)-1))に対応する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせと（「ラベル」と呼ぶ）、出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bに対応するκ-1ビットの第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと1ビットの第６ランダムビットck(L)∈Bとの排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとが関連付けられた表である。例えば、論理回路の出力端（最終段）の論理素子を除く論理素子G(L)に対応する歪曲真理値表DT(L)では、ラベルと、第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))とが関連付けられる。例えば、最終段の論理素子G(L)に対応する歪曲真理値表DT(L)では、ラベルと、第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとが関連付けられる。歪曲真理値表DT(L)でラベルに関連付けられる値を「歪曲真理値」と呼ぶ。
【００２８】
歪曲回路生成部１２６は、各歪曲真理値表DT(L)を生成する際に、第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1及び第６ランダムビットck(L)∈Bをランダムに生成する。
p(L)∈{0,…,n-1}の場合、秘匿値PWp(L),x(p(L))はサーバ用秘匿情報Es(Ds)から特定される秘匿値PWi,0,PWi,1(i=0,…,n-1)の何れかであり、かつ、第４ランダムビットcp(L)∈Bは第３ランダムビットci(i=p(L))であり、かつ、反転ビットcp(L)-∈Bは反転ビットci-(i=p(L))である。
p(L)が{0,…,n-1}の要素でない場合、秘匿値PWp(L),x(p(L))は別の論理素子G(PL)(PL≠L, PL=0,...,Lmax-1)に対応する歪曲回路情報の第５ランダムビットWk(PL),g(L;x(r(PL)),…,x(r(PL)+s(PL)-1))∈Bκ-1と第６ランダムビットck(PL)∈Bとの組に対応する値であり、かつ、第４ランダムビットcp(L)∈Bは第６ランダムビットck(PL)∈Bであり、かつ、反転ビットcp(L)-∈Bは第６ランダムビットck(PL)∈Bの反転ビットである。
【００２９】
［最終段の論理素子を除く論理素子G(L)に対応する歪曲真理値表DT(L)の一例］
最終段の論理素子を除く論理素子G(L)に対応する歪曲真理値表DT(L)の一例を示す。
cr(L;0),...,cr(L;s(L)-1),(Wk(L),g(L;0,…,0),g(L;0,…,0)(+)ck(L))
(+)F(Wr(L;0),0,cr(L;s(L)-1))(+)F(Wr(L;0)+1,0,cr(L;0))(+)…(+)F(Wr(L;s(L)-1),0,cr(L;s(L)-2))
cr(L;0),...,cr(L;s(L)-1)-,(Wk(L),g(L;0,…,1),g(L;0,…,1)(+)ck(L))
(+)F(Wr(L;0),0,cr(L;s(L)-1)-)(+)F(Wr(L;1),0,cr(L;0))(+)…(+)F(Wr(L;s(L)-1),1,cr(L;s(L)-2))
...
cr(L;0)-,...,cr(L;s(L)-1)-,(Wk(L),g(L;1,…,1),g(L;1,…,1)(+)ck(L))
(+)F(Wr(L;0),1,cr(L;s(L)-1)-)(+)F(Wr(L;1),1,cr(L;0)-)(+)…(+)F(Wr(L;s(L)-1),1,cr(L;s(L)-2)-)
ただし、(+)は排他的論理和演算子を表し、W∈Bκ-1,c∈Bについての(W,c)はWとcとのビット連結値を表す。F(W,c)∈BκはW∈Bκ-1,c∈Bの入力に対してκビットのF(W,c)∈Bκを出力する擬似ランダム関数である。F(W,c)の例は、W∈Bκ-1とc∈Bとビット連結値のハッシュ値を出力するハッシュ関数である。
s(L)=2の論理素子G(L)に対応する歪曲真理値表DT(L)の例を以下に示す。
cr(L;0),cr(L;1),(Wk(L),g(L;0,0),g(L;0,0)(+)ck(L))(+)F(Wr(L;0),0,cr(L;1))(+)F(Wr(L;1),0,cr(L;0))
cr(L;0),cr(L;1)-,(Wk(L),g(L;0,1),g(L;0,1)(+)ck(L))(+)F(Wr(L;0),0,cr(L;1)-)(+)F(Wr(L;1),1,cr(L;0))
cr(L;0)-,cr(L;1),(Wk(L),g(L;1,0),g(L;1,0)(+)ck(L))(+)F(Wr(L;0),1,cr(L;1))(+)F(Wr(L;1),0,cr(L;0)-)
cr(L;0)-,cr(L;1)-,(Wk(L),g(L;1,1),g(L;1,1)(+)ck(L))(+)F(Wr(L;0),1,cr(L;1)-)(+)F(Wr(L;1),1,cr(L;0)-)
【００３０】
［最終段の論理素子G(L)に対応する歪曲真理値表DT(L)の一例］
最終段の論理素子G(L)に対応する歪曲真理値表DT(L)の一例を示す。
cr(L;0),...,cr(L;s(L)-1),(Wk(L),g(L;0,…,0),g(L;0,…,0))
(+)F(Wr(L;0),0,cr(L;s(L)-1))(+)F(Wr(L;1),0,cr(L;0))(+)…(+)F(Wr(L;s(L)-1),0,cr(L;s(L)-2))
cr(L;0),...,cr(L;s(L)-1)-,(Wk(L),g(L;0,…,1),g(L;0,…,1))
(+)F(Wr(L;0),0,cr(L;s(L)-1)-)(+)F(Wr(L;1),0,cr(L;0))(+)…(+)F(Wr(L;s(L)-1),1,cr(L;s(L)-2))
...
cr(L;0)-,...,cr(L;s(L)-1)-,(Wk(L),g(L;1,…,1),g(L;1,…,1))
(+)F(Wr(L;0),1,cr(L;s(L)-1)-)(+)F(Wr(L;1),1,cr(L;0)-)(+)…(+)F(Wr(L;s(L)-1),1,cr(L;s(L)-2)-)
s(L)=2の論理素子G(L)に対応する歪曲真理値表DT(L)の例を以下に示す。
cr(L;0),cr(L;1),(Wk(L),g(L;0,0),g(L;0,0))(+)F(Wr(L;0),0,cr(L;1))(+)F(Wr(L;1),0,cr(L;0))
cr(L;0),cr(L;1)-,(Wk(L),g(L;0,1),g(L;0,1))(+)F(Wr(L;0),0,cr(L;1)-)(+)F(Wr(L;1),1,cr(L;0))
cr(L;0)-,cr(L;1),(Wk(L),g(L;1,0),g(L;1,0))(+)F(Wr(L;0),1,cr(L;1))(+)F(Wr(L;1),0,cr(L;0)-)
cr(L;0)-,cr(L;1)-,(Wk(L),g(L;1,1),g(L;1,1))(+)F(Wr(L;0),1,cr(L;1)-)(+)F(Wr(L;1),1,cr(L;0)-)
【００３１】
［図４の論理回路に対応する歪曲真理値表DT(L)の例］
図４の論理回路が含む論理素子G(L)に対応する歪曲真理値表DT(L)を例示する。この例の論理回路ではLmax=6、n=6である。
［論理素子G(0)に対応する歪曲真理値表DT(0)の例（最終段）:s(0)=2, p(0)=0,1］
c0,c1,(Wk(0),g(0;0,0),g(0;0,0))(+)F(W0,0,c1)(+)F(W1,0,c0)
c0,c1-,(Wk(0),g(0;0,1),g(0;0,1))(+)F(W0,0,c1-)(+)F(W1,1,c0)           …(1)
c0-,c1,(Wk(0),g(0;1,0),g(0;1,0))(+)F(W0,1,c1)(+)F(W1,0,c0-)
c0-,c1-,(Wk(0),g(0;1,1),g(0;1,1))(+)F(W0,1,c1-)(+)F(W1,1,c0-)
0,1∈{0,…,5}であるため、c0,c0-,c1,c1-,W0,0,W0,1,W1,0,W1,1は、サーバ用秘匿情報Es(Ds)から特定される秘匿値PW0,0=(W0,0, c0), PW0,1=(W0,1, c0-), PW1,0=(W1,0, c1), PW1,1=(W1,1, c1-)から得られる。Wk(0),0, Wk(0),1はランダムに生成される。
【００３２】
［論理素子G(1)に対応する歪曲真理値表DT(1)の例:s(1)=1, p(1)=2］
c2,(Wk(1),g(1;0),g(1;0)(+)ck(1))(+)F(W2,0,c2)           …(2)
c2-,(Wk(1),g(1;1),g(1;1)(+)ck(1))(+)F(W2,1,c2-)
2∈{0,…,5}であるため、c2,c2-,W2,0,W2,1は、サーバ用秘匿情報Es(Ds)から特定される秘匿値PW2,0=(W2,0, c2), PW2,1=(W2,1, c2-)から得られる。Wk(1),0, Wk(1),1, ck(1)はランダムに生成される。
【００３３】
［論理素子G(2)に対応する歪曲真理値表DT(2)の例:s(2)=2, p(2)=3,6］
c6,c3,(Wk(2),g(2;0,0),g(2;0,0)(+)ck(2))(+)F(W6,0,c3)(+)F(W3,0,c6)
c6,c3-,(Wk(2),g(2;0,1),g(2;0,1)(+)ck(2))(+)F(W6,0,c3-)(+)F(W3,1,c6)           …(3)
c6-,c3,(Wk(2),g(2;1,0),g(2;1,0)(+)ck(2))(+)F(W6,1,c3)(+)F(W3,0,c6-)
c6-,c3-,(Wk(2),g(2;1,1),g(2;1,1)(+)ck(2))(+)F(W6,1,c3-)(+)F(W3,1,c6-)
3∈{0,…,5}であるため、c3,c3-,W3,0,W3,1は、サーバ用秘匿情報Es(Ds)から特定される秘匿値PW3,0=(W3,0, c3), PW3,1=(W3,1, c3-)である。6∈{0,…,5}ではなく、c6,c6-,W6,0,W6,1は、歪曲真理値表DT(1)の生成時に用いられたck(1), Wk(1),0, Wk(1),1から得られ、以下の関係を満たす。
W6,0=Wk(1),0, W6,1=Wk(1),1, c6=ck(1), c6-=ck(1)-           …(4)
Wk(2),0, Wk(2),1, ck(2)はランダムに生成される。
【００３４】
［論理素子G(3)に対応する歪曲真理値表DT(3)の例:s(3)=1, p(3)=5］
c5,(Wk(3),g(3;0),g(3;0)(+)ck(3))(+)F(W5,0,c5)           …(5)
c5-,(Wk(3),g(3;1),g(3;1)(+)ck(3))(+)F(W5,1,c5-)
5∈{0,…,5}であるため、c5,c5-,W5,0,W5,1は、サーバ用秘匿情報Es(Ds)から特定される秘匿値PW5,0=(W5,0, c5), PW5,1=(W5,1, c5-)から得られる。Wk(3),0, Wk(3),1, ck(3)はランダムに生成される。
【００３５】
［論理素子G(4)に対応する歪曲真理値表DT(4)の例:s(4)=2, p(4)=4,7］
c4,c7,(Wk(4),g(4;0,0),g(4;0,0)(+)ck(4))(+)F(W4,0,c7)(+)F(W7,0,c4)
c4,c7-,(Wk(4),g(4;0,1),g(4;0,1)(+)ck(4))(+)F(W4,0,c7-)(+)F(W7,1,c4)  …(6)
c4-,c7,(Wk(4),g(4;1,0),g(4;1,0)(+)ck(4))(+)F(W4,1,c7)(+)F(W7,0,c4-)
c4-,c7-,(Wk(4),g(4;1,1),g(4;1,1)(+)ck(4))(+)F(W4,1,c7-)(+)F(W7,1,c4-)
4∈{0,…,5}であるため、c4,c4-,W4,0,W4,1は、サーバ用秘匿情報Es(Ds)から特定される秘匿値PW4,0=(W4,0, c4), PW4,1=(W4,1, c4-)である。7∈{0,…,5}ではなく、c7,c7-,W7,0,W7,1は、歪曲真理値表DT(3)の生成時に用いられたck(3), Wk(3),0, Wk(3),1から得られ、以下の関係を満たす。
W7,0=Wk(3),0, W7,1=Wk(3),1, c7=ck(3), c7-=ck(3)-           …(7)
Wk(4),0, Wk(4),1, ck(4)はランダムに生成される。
【００３６】
［論理素子G(5)に対応する歪曲真理値表DT(5)の例（最終段）:s(5)=2, p(5)=8,9］
c8,c9,(Wk(5),g(5;0,0),g(5;0,0))(+)F(W8,0,c9)(+)F(W9,0,c8)
c8,c9-,(Wk(5),g(5;0,1),g(5;0,1))(+)F(W8,0,c9-)(+)F(W9,1,c8)           …(8)
c8-,c9,(Wk(5),g(5;1,0),g(5;1,0))(+)F(W8,1,c9)(+)F(W9,0,c8-)
c8-,c9-,(Wk(5),g(5;1,1),g(5;1,1))(+)F(W8,1,c9-)(+)F(W9,1,c8-)
8,9∈{0,…,5}ではなく、c8,c8-,W8,0,W8,1は歪曲真理値表DT(2)の生成時に用いられたck(2), Wk(2),0, Wk(2),1から得られ、c9,c9-,W9,0,W9,1は歪曲真理値表DT(4)の生成時に用いられたck(4), Wk(4),0, Wk(4),1から得られ、以下の関係を満たす。
W8,0=Wk(2),0, W8,1=Wk(2),1, c8=ck(2), c8-=ck(2)-           …(9)
W9,0=Wk(4),0, W9,1=Wk(4),1, c9=ck(4), c9-=ck(4)-           …(10)
Wk(5),0, Wk(5),1はランダムに生成される。
【００３７】
歪曲回路生成部１２６で生成された歪曲真理値表DT(L)(L=0,...,Lmax-1)の集合を含む歪曲回路情報は送信部１２２に入力される。また、記憶部１２４から読み出されたクライアント用秘匿情報Ec(Dc)が送信部１２２に入力される。送信部１２２（「出力部」に相当）は、歪曲回路情報とクライアント用秘匿情報Ec(Dc)とをクライアント装置１１０に送信する（ステップＳ１１９）。
【００３８】
歪曲回路情報とクライアント用秘匿情報Ec(Dc)とは、クライアント装置１１０の受信部１１３（「入力部」に相当）に受信され、歪曲回路計算部１１９に入力される（ステップＳ１２０）。
【００３９】
歪曲回路計算部１１９は、クライアント用秘匿情報Ec(Dc)から秘匿値PWi,a(i)(i=0,…,n-1)を復元する。例えば、歪曲回路計算部１１９は、クライアント用秘匿情報Ec(Dc)を復号するための共通鍵を用い、入力されたクライアント用秘匿情報Ec(Dc)から秘匿値PWi,a(i)(i=0,…,n-1)を復号する。
【００４０】
次に歪曲回路計算部１１９は、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせ（「歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに対応する情報」に相当）を用い、歪曲回路情報に含まれる歪曲真理値表DT(L)を検索し、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに一致する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせに対応付けられた排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを得る歪曲素子演算処理を各L(L=0,...,Lmax-1)について実行する。
p(L)∈{0,…,n-1}に対応する歪曲入力ビットy(p(L))∈Bは、クライアント用秘匿情報から特定される秘匿値PWi,a(i)(i= p(L))に対応する第３ランダムビットci又は反転ビットci-である。{0,…,n-1}の要素ではないp(L)に対応する歪曲入力ビットy(p(L))∈Bは、別の歪曲真理値表DT(PL)に対する歪曲素子演算処理で得られた排他的論理和xor(x(r(PL)),…,x(r(PL)+s(PL)-1))である。
歪曲真理値表DT(L)に対応する歪曲素子演算処理は、その歪曲素子演算処理に必要な歪曲入力ビットy(p(L))が得られれば実行できる。歪曲素子演算処理に必要な歪曲入力ビットy(p(L))が得られるのであれば、歪曲素子演算処理の実行順序に限定はない。すべてのL(L=0,...,Lmax-1)について歪曲素子演算処理が実行されることで論理回路の出力ビットが得られる。
【００４１】
［図４の論理回路に対する歪曲素子演算処理の例示］
保存フェーズで入力された入力ビットがa(0)=a(2)=a(4)=1, a(1)=a(3)=a(5)=0であった場合の例を示す。
歪曲回路計算部１１９は、クライアント用秘匿情報Ec(Dc)から、秘匿値PW0,1=(W0,1,c0-), PW1,0=(W1,0,c1), PW2,1=(W2,1,c2-), PW3,0=(W3,0,c3), PW4,1=(W4,1,c4-), PW5,0=(W5,0,c5)を復元する。
【００４２】
[歪曲真理値表DT(0)の歪曲素子演算処理の例示]
式(1)の歪曲真理値表DT(0)に対応する歪曲入力ビットはy(0),y(1)である。p(0)=0,1∈{0,…,5}が満たされる。そのため歪曲入力ビットy(0)はPW0,1=(W0,1, c0-)に対応するc0-であり、歪曲入力ビットy(1)はPW1,0=(W1,0, c1)に対応するc1である。歪曲回路計算部１１９は、歪曲真理値表DT(0)で、歪曲入力ビットy(0)=c0-, y(1)=c1からなる組み合わせに一致するc0-, c1に対応付けられたg(0;1,0)を得る。式(1)の例では、歪曲回路計算部１１９は、PW0,1=(W0,1, c0-)及びPW1,0=(W1,0, c1)を用いてF(0)=F(W0,1,c1)(+)F(W1,0,c0-)を計算し、さらに以下の計算を行う。
(Wk(0),g(0;1,0),g(0;1,0))(+)F(W0,1,c1)(+)F(W1,0,c0-)(+)F(0)=(Wk(0),g(0;1,0),g(0;1,0))
これにより、歪曲回路計算部１１９は、c0-, c1に対応付けられたg(0;1,0)を得て、これをγとして出力する。論理素子G(0)はＡＮＤゲートであるため、g(0;1,0)=0が満たされる。
【００４３】
[歪曲真理値表DT(1)の歪曲素子演算処理の例示]
式(2)の歪曲真理値表DT(1)に対応する歪曲入力ビットはy(2)である。p(1)=2∈{0,…,5}が満たされる。そのため歪曲入力ビットy(2)はPW2,1=(W2,1,c2-)に対応するc2-である。歪曲回路計算部１１９は、歪曲真理値表DT(1)で、歪曲入力ビットy(2)=c2-に一致するc2-に対応付けられたWk(1),g(1;1)とg(1;1)(+)ck(1)を得る。式(2)の例では、歪曲回路計算部１１９は、PW2,1=(W2,1,c2-)を用いてF(1)=F(W2,1,c2-)を計算し、さらに以下の計算を行う。
(Wk(1),g(1;1),g(1;1)(+)ck(1))(+)F(W2,1,c2-)(+)F(1)=(Wk(1),g(1;1),g(1;1)(+)ck(1))
これにより、歪曲回路計算部１１９は、c2-に対応付けられたWk(1),g(1;1)とg(1;1)(+)ck(1)を得る。論理素子G(1)はＮＯＴゲートであるためg(1;1)=0が満たされ、Wk(1),g(1;1)=Wk(1),0，g(1;1)(+)ck(1)=ck(1)が満たされる。
【００４４】
[歪曲真理値表DT(2)の歪曲素子演算処理の例示]
式(3)の歪曲真理値表DT(2)に対応する歪曲入力ビットはy(6),y(3)である。6∈{0,…,5}は満たされないが3∈{0,…,5}は満たされる。そのため、歪曲入力ビットy(6)は、歪曲真理値表DT(1)の歪曲素子演算処理で得られた排他的論理和g(1;1)(+)ck(1)=ck(1)であり、歪曲入力ビットy(3)はPW3,0=(W3,0, c3)に対応するc3である。式(4)に示すようにc6=ck(1)が満たされ、歪曲回路計算部１１９は、歪曲真理値表DT(2)で、歪曲入力ビットy(6)=ck(1)=c6, y(3)=c3からなる組み合わせに一致するc6, c3に対応付けられたWk(2),g(2;0,0)及びg(2;0,0)(+)ck(2)を得る。式(3)の例では、歪曲回路計算部１１９は、歪曲真理値表DT(1)の歪曲素子演算処理で得られたW6,0=Wk(1),c6=ck(1)及び入力されたPW3,0=(W3,0,c3)を用いてF(2)=F(W6,0,c3)(+)F(W3,0,c6)を計算し、さらに以下の計算を行う。
(Wk(2),g(2;0,0),g(2;0,0)(+)ck(2))(+)F(W6,0,c3)(+)F(W3,0,c6)(+)F(2)
=(Wk(2),g(2;0,0),g(2;0,0)(+)ck(2))
これにより、歪曲回路計算部１１９は、c6, c3に対応付けられたWk(2),g(2;0,0)及びg(2;0,0)(+)ck(2)を得る。論理素子G(2)はＡＮＤゲートであるため、g(2;0,0)=0が満たされ、Wk(2),g(2;0,0)=Wk(2),0及びg(2;0,0)(+)ck(2)=ck(2)が満たされる。
【００４５】
[歪曲真理値表DT(3)の歪曲素子演算処理の例示]
式(5)の歪曲真理値表DT(3)に対応する歪曲入力ビットはy(5)である。p(3)=5∈{0,…,5}が満たされる。そのため歪曲入力ビットy(5)はPW5,0=(W5,0,c5)に対応するc5である。歪曲回路計算部１１９は、歪曲真理値表DT(3)で、歪曲入力ビットy(5)=c5に一致するc5に対応付けられたWk(3),g(3;0)とg(3;0)(+)ck(3)を得る。式(5)の例では、歪曲回路計算部１１９は、PW5,0=(W5,0,c5)を用いてF(3)=F(W5,0,c5)を計算し、さらに以下の計算を行う。
(Wk(3),g(3;0),g(3;0)(+)ck(3))(+)F(W5,0,c5)(+)F(3)=(Wk(3),g(3;0),g(3;0)(+)ck(3))
これにより、歪曲回路計算部１１９は、c5に対応付けられたWk(3),g(3;0)とg(3;0)(+)ck(3)を得る。論理素子G(3)はＮＯＴゲートであるためg(3;0)=1が満たされ、Wk(3),g(3;0)=Wk(3),1，g(3;0)(+)ck(3)=ck(3)-が満たされる。
【００４６】
[歪曲真理値表DT(4)の歪曲素子演算処理の例示]
式(6)の歪曲真理値表DT(4)に対応する歪曲入力ビットはy(4),y(7)である。4∈{0,…,5}は満たされるが7∈{0,…,5}は満たされない。そのため、歪曲入力ビットy(4)はPW4,1=(W4,1,c4-)に対応するc4-であり、歪曲入力ビットy(7)は歪曲真理値表DT(3)の歪曲素子演算処理で得られた排他的論理和g(3;0)(+)ck(3)=ck(3)-である。式(7)に示すようにc7-=ck(3)-が満たされ、歪曲回路計算部１１９は、歪曲真理値表DT(4)で、歪曲入力ビットy(4)=c4-, y(7)=ck(3)-=c7-からなる組み合わせに一致するc4-, c7-に対応付けられたWk(4),g(4;1,1)及びg(4;1,1)(+)ck(4)を得る。式(6)の例では、歪曲回路計算部１１９は、入力されたPW4,1=(W4,1,c4-)及び歪曲真理値表DT(3)の歪曲素子演算処理で得られたWk(3),g(3;0)=Wk(3),1，g(3;0)(+)ck(3)=ck(3)-を用いてF(4)=F(W4,1,c7-)(+)F(W7,1,c4-)を計算し、さらに以下の計算を行う。
(Wk(4),g(4;1,1),g(4;1,1)(+)ck(4))(+)F(W4,1,c7-)(+)F(W7,1,c4-)(+)F(4)
=(Wk(4),g(4;1,1),g(4;1,1)(+)ck(4))
これにより、歪曲回路計算部１１９は、c4-, c7-に対応付けられたWk(4),g(4;1,1)及びg(4;1,1)(+)ck(4)を得る。論理素子G(2)はＡＮＤゲートであるため、g(4;1,1)=1が満たされ、Wk(4),g(4;1,1)=Wk(4),1及びg(4;1,1)(+)ck(4)=ck(4)-が満たされる。
【００４７】
[歪曲真理値表DT(5)の歪曲素子演算処理の例示]
式(8)の歪曲真理値表DT(5)に対応する歪曲入力ビットはy(8),y(9)である。8,9∈{0,…,5}は満たされない。歪曲入力ビットy(8)は歪曲真理値表DT(2)の歪曲素子演算処理で得られた排他的論理和g(2;0,0)(+)ck(2)=ck(2)であり、歪曲入力ビットy(9)は歪曲真理値表DT(4)の歪曲素子演算処理で得られた排他的論理和g(4;1,1)(+)ck(4)=ck(4)-である。式(9)に示すようにck(2)=c8が満たされ、式(10)に示すようにck(4)-=c9-が満たされる。歪曲回路計算部１１９は、歪曲真理値表DT(5)で、歪曲入力ビットy(8)=ck(2)=c8, y(9)=ck(4)-=c9-からなる組み合わせに一致するc8, c9-に対応付けられたg(5;0,1)を得る。式(8)の例では、歪曲回路計算部１１９は、歪曲真理値表DT(2)の歪曲素子演算処理で得られたWk(2),g(2;0,0)=Wk(2),0及びg(2;0,0)(+)ck(2)=ck(2)、及び歪曲真理値表DT(4)の歪曲素子演算処理で得られたWk(4),g(4;1,1)=Wk(4),1及びg(4;1,1)(+)ck(4)=ck(4)-を用いてF(5)=F(W8,0,c9-)(+)F(W9,1,c8)を計算し、さらに以下の計算を行う。
(Wk(5),g(5;0,1),g(5;0,1))(+)F(W8,0,c9-)(+)F(W9,1,c8)(+)F(5)
=(Wk(5),g(5;0,1),g(5;0,1))
これにより、歪曲回路計算部１１９は、c8, c9-に対応付けられたg(5;0,1)を得て、これをδとして出力する。G(5)はＯＲゲートであるため、g(5;0,1)=1が満たされる（ステップＳ１２１）。
【００４８】
〔第２実施形態〕
第２実施形態は第１実施形態の変形例である。第２実施形態では、保存フェーズの処理を行うクライアント装置と計算フェーズの処理を行うクライアント装置とが相違する。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する処理部や処理ステップについては第１実施形態で使用された記号を引用して説明を省略する。互いに異なる処理主体によって行われる同一の処理内容に対応するステップには同一の記号が割り当てられている（以下の他の実施形態についても同様）。
【００４９】
＜構成＞
図５に例示するように、本形態の秘匿データ処理システム２は、クライアント装置２１０−１（「第１クライアント装置」に相当）と、クライアント装置２１０−２（「第２クライアント装置」に相当）と、サーバ装置２２０を有する。この例のクライアント装置２１０−１は、入力部１１１と送信部１１２と制御部２１５−１とランダム化部１１６とサーバ用秘匿情報生成部１１７とクライアント用秘匿情報生成部１１８とを有する。この例のクライアント装置２１０−２は、入力部２１１と送信部２１２と受信部２１３と制御部２１５−２と歪曲回路計算部１１９とを有する。サーバ装置２２０は、送信部２２２と受信部２２３と記憶部１２４と制御部１２５と歪曲回路生成部１２６とを有する。
【００５０】
クライアント装置２１０−１，２及びサーバ装置２２０は、例えばそれぞれ、特別なプログラムが、公知のコンピュータ又は専用のコンピュータに読み込まれ、実行されることで構築される特別な装置である。以下では説明を省略するが、この例の場合、クライアント装置２１０−１，２やサーバ装置２２０の各処理部（「***部」）で受信されたデータや得られたデータは、クライアント装置２１０−１，２やサーバ装置２２０の一時メモリ（図示せず）に逐一格納される。一時メモリに格納されたデータは、必要に応じて読み出され、クライアント装置２１０−１，２やサーバ装置２２０の処理部に入力され、そこでの演算処理に利用される。なお、クライアント装置２１０−１，２やサーバ装置２２０の処理部の少なくとも一部がハードウェアによって構成されてもよい。制御部２１５−１はクライアント装置２１０−１の処理を制御し、制御部２１５−２はクライアント装置２１０−２の処理を制御し、制御部２２５はサーバ装置２２０の処理を制御する。クライアント装置２１０−１，２はサーバ装置２２０に情報を送信でき、サーバ装置２２０はクライアント装置２１０−２に情報を送信できる。
【００５１】
＜処理＞
本形態では、クライアント装置２１０−１とサーバ装置２２０との間で保存フェーズの処理が実行され、クライアント装置２１０−２とサーバ装置２２０との間で計算フェーズの処理が実行される。
【００５２】
＜保存フェーズ＞
保存フェーズでは、クライアント装置２１０−１が第１実施形態で説明したステップＳ１０１−Ｓ１０６（図２）の処理を実行する。クライアント装置２１０−１から送信されたサーバ用秘匿情報Es(Ds)及びクライアント用秘匿情報Ec(Dc)は、サーバ装置２２０の受信部２１３で受信され（ステップＳ１０７）、記憶部１２４に記憶される（ステップＳ１０８）。
【００５３】
＜計算フェーズ＞
計算フェーズでは、クライアント装置２１０−２の入力部２１１に、Lmax(Lmax≧1)個の論理素子G(L)(L=0,...,Lmax-1)から構成される論理回路を表す論理回路情報ＬＣが入力され（ステップＳ１１１）、送信部２１２（「論理回路情報出力部」に相当）が論理回路情報ＬＣをサーバ装置２２０に送信する（ステップＳ１１２）。論理回路情報ＬＣは、サーバ装置１２０の受信部２２３（「論理回路情報入力部」に相当）で受信され、歪曲回路生成部１２６に入力される（ステップＳ１１３）。歪曲回路生成部１２６は、サーバ用秘匿情報Es(Ds)からDs={PWi,0,PWi,1}i=0,…,n-1を得る（ステップＳ１１４）。送信部２２２（「出力部」に相当）は、クライアント用秘匿情報Ec(Dc)をクライアント装置２１０−２に送信する（ステップＳ１１５）。クライアント用秘匿情報Ec(Dc)は、クライアント装置２１０−２の受信部２１３（「入力部」に相当）で受信され、歪曲回路計算部１１９に入力される（ステップＳ１１６）。歪曲回路計算部１１９は、クライアント用秘匿情報Ec(Dc)からDc={PWi,a(i)}i=0,…,n-1を復元する（ステップＳ１１７）。サーバ装置２２０の歪曲回路生成部１２６は、第１実施形態と同様に、Ds={PWi,0,PWi,1}i=0,…,n-1を用い、論理回路情報ＬＣが表す各真理値表T(L)(L=0,...,Lmax-1)を歪曲真理値表DT(L)にそれぞれ変換し、歪曲真理値表DT(L)(L=0,...,Lmax-1)の集合を含む歪曲回路情報を生成する（ステップＳ１１８）。送信部２２２（「出力部」に相当）は、歪曲回路情報とクライアント用秘匿情報Ec(Dc)とをクライアント装置２１０−２に送信する（ステップＳ１１９）。歪曲回路情報とクライアント用秘匿情報Ec(Dc)とは、クライアント装置２１０−２の受信部２１３（「入力部」に相当）で受信され、歪曲回路計算部１１９に入力される（ステップＳ１２０）。歪曲回路計算部１１９は、第１実施形態と同様に、クライアント用秘匿情報Ec(Dc)から秘匿値PWi,a(i)(i=0,…,n-1)を復元し、歪曲回路情報に含まれる各歪曲真理値表DT(L)(L=0,...,Lmax-1)に対する歪曲素子演算処理を実行し、演算結果を表す出力ビットを出力する（ステップＳ１２１）。
【００５４】
〔第３実施形態〕
第３実施形態は第１実施形態の変形例である。本形態では、保存フェーズの処理時に、クライアント装置からサーバ装置にサーバ用秘匿情報Es(Ds)は送信されるが、クライアント用秘匿情報Ec(Dc)が送信されない。クライアント用秘匿情報Ec(Dc)は、クライアント装置に格納される。計算フェーズの処理時には、クライアント装置は、クライアント装置に記憶されたクライアント用秘匿情報Ec(Dc)を用いて歪曲素子演算処理を実行する。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する部分や処理については第１実施形態で使用された記号を引用して説明を省略する。
【００５５】
＜構成＞
図６に例示するように、本形態の秘匿データ処理システム３は、クライアント装置３１０とサーバ装置３２０を有する。クライアント装置３１０は、入力部１１１と送信部３１２と受信部３１３と記憶部３１４と制御部１１５とランダム化部１１６とサーバ用秘匿情報生成部１１７とクライアント用秘匿情報生成部１１８と歪曲回路計算部３１９とを有する。サーバ装置３２０は、送信部３２２と受信部３２３と記憶部３２４と制御部１２５と歪曲回路生成部１２６とを有する。
【００５６】
クライアント装置３１０及びサーバ装置３２０は、例えばそれぞれ、特別なプログラムが、公知のコンピュータ又は専用のコンピュータに読み込まれ、実行されることで構築される特別な装置である。以下では説明を省略するが、この例の場合、クライアント装置３１０やサーバ装置３２０の各処理部（「***部」）で受信されたデータや得られたデータは、クライアント装置３１０やサーバ装置３２０の一時メモリ（図示せず）に逐一格納される。一時メモリに格納されたデータは、必要に応じて読み出され、クライアント装置３１０やサーバ装置３２０の処理部に入力され、そこでの演算処理に利用される。なお、クライアント装置３１０やサーバ装置３２０の処理部の少なくとも一部がハードウェアによって構成されてもよい。制御部１１５はクライアント装置３１０の処理を制御し、制御部１２５はサーバ装置３２０の処理を制御する。また、クライアント装置３１０はサーバ装置３２０に情報を送信でき、サーバ装置３２０はクライアント装置３１０に情報を送信できる。
【００５７】
＜処理＞
本形態の秘匿データ処理システム３によって行われる処理は、クライアント装置３１０がサーバ装置３２０にデータを預託する保存フェーズと、クライアント装置３１０とサーバ装置３２０とが協調して計算を行う計算フェーズとを含む。以下では、まず保存フェーズを説明し、次に計算フェーズを説明する。
【００５８】
＜保存フェーズ＞
図７に示すように、クライアント装置３１０が第１実施形態で説明したステップＳ１０１−Ｓ１０５と同一の処理を実行する。本形態のクライアント用秘匿情報Ec(Dc)はDcを秘匿するための情報（暗号文等）でなくてもよい。例えば、本形態のクライアント用秘匿情報Ec(Dc)はDcそのものであってもかまわない。本形態で生成されたクライアント用秘匿情報Ec(Dc)は記憶部３１４に記憶される（ステップＳ３０５）。送信部３１２は、サーバ用秘匿情報Es(Ds)をサーバ装置３２０に送信する（ステップＳ３０６）。サーバ用秘匿情報Es(Ds)は、サーバ装置３２０の受信部３２３で受信され（ステップＳ１０７）、記憶部３２４に記憶される（ステップＳ１０８）。
【００５９】
＜計算フェーズ＞
図８に示すように、記憶部３１４に記憶されたクライアント用秘匿情報Ec(Dc)がクライアント装置３１０の歪曲回路計算部３１９に入力される。歪曲回路計算部３１９は、第１実施形態と同様に、クライアント用秘匿情報Ec(Dc)からDc={PWi,a(i)}i=0,…,n-1を復元する（ステップＳ３１０）。クライアント装置３１０の入力部１１１に、Lmax(Lmax≧1)個の論理素子G(L)(L=0,...,Lmax-1)から構成される論理回路を表す論理回路情報ＬＣが入力される（ステップＳ１１１）。論理回路情報ＬＣは送信部３１２に入力され、送信部３１２は論理回路情報ＬＣをサーバ装置３２０に送信する（ステップＳ１１２）。論理回路情報ＬＣは、サーバ装置３２０の受信部３２３で受信され、歪曲回路生成部１２６に入力される（ステップＳ１１３）。サーバ装置３２０は、第１実施形態で説明したステップＳ１１４，Ｓ１１８，Ｓ１１９の処理と同一の処理を実行し、クライアント装置３１０は第１実施形態で説明したステップＳ１２０の処理と同一の処理を実行する。
歪曲回路計算部１１９は、クライアント用秘匿情報Ec(Dc)から秘匿値PWi,a(i)(i=0,…,n-1)を復元する。クライアント用秘匿情報Ec(Dc)が第１実施形態と同様に構成されている場合、この処理は第１実施形態と同様に行われる。一方、クライアント用秘匿情報Ec(Dc)がDcを秘匿するための情報でない場合、歪曲回路計算部１１９は、クライアント用秘匿情報Ec(Dc)からDcを得る。次に歪曲回路計算部１１９は、第１実施形態と同様の歪曲素子演算処理を各L(L=0,...,Lmax-1)について実行する（ステップＳ３２１）。
【００６０】
〔各実施形態の特徴〕
以下にこれまで説明した各実施形態の特徴を説明する。
［第１実施形態の特徴］
第１実施形態では、クライアント装置１１０がサーバ装置１２０にサーバ用秘匿情報Es(Ds)及びクライアント用秘匿情報Ec(Dc)を預託し、サーバ装置１２０がサーバ用秘匿情報Es(Ds)から得られるDsと論理回路に対応する論理回路情報とを用いて歪曲回路情報を生成し、クライアント装置１１０がクライアント用秘匿情報Ec(Dc)から得られるDcと生成された論理回路情報とを用いて秘匿回路計算を行う。ここで、クライアント用秘匿情報Ec(Dc)は、n個の入力ビットa(i)∈B (i=0,…,n-1)にそれぞれ対応する秘匿値PWi,a(i)(i=0,…,n-1)をクライアント装置１１０のみで特定するため情報である。すなわち、サーバ装置１２０はクライアント用秘匿情報Ec(Dc)からDcを得ることができない。よって、サーバ用秘匿情報Es(Ds)及びクライアント用秘匿情報Ec(Dc)がサーバ装置１２０に預託されたとしても、サーバ装置１２０が不正な秘匿回路計算を行ってその演算結果を得ることができない。第１実施形態の方法は以下の利点を持つ。
１．クライアント装置１１０は安全にサーバ装置１２０にデータを預託することができ、クライアント装置１１０にデータを格納するためのストレージを設ける必要がない。
２．不正な処理を行うサーバ装置１２０が用いられても、歪曲化前の入力ビットの値や秘匿回路計算の結果がサーバ装置１２０に知られることはない。
３．第１実施形態の秘匿データ処理方法は、クライアント装置１１０とサーバ装置１２０との二者で安全に実行できる２パーティモデルの枠組みで実行される。２パーティモデルは、秘匿回路計算を行うマルチパーティモデルの中で最も実現が容易なモデルである。
４．第１実施形態の秘匿データ処理方法には公開鍵暗号方式を用いる必要はない。そのため、第１実施形態の秘匿データ処理方法では、秘匿回路計算の演算速度が速い。
【００６１】
公開鍵暗号方式を用いた方法の処理時間と公開鍵暗号方式を用いない方法の処理時間との違いは、非特許文献３の方法を実行した場合の処理時間の実測値と非特許文献１の方法を実行した場合の処理時間の実測値とを比較することで考察できる。
公開鍵暗号を用いる非特許文献３の方法の２パーティでの処理時間の合計は、論理素子１ゲートあたり13.78msである。ただし、各パーティはそれぞれXeon（登録商標）2.8GHzのマイクロプロセッサを４台用いて計算を行った。公開鍵暗号を用いない非特許文献１の方法の２パーティでの処理時間の合計は、論理素子１ゲートあたり11.14sである。ただし、各パーティはそれぞれCore（登録商標） 2 Duo 2.53GHzのマイクロプロセッサを１台用いて計算を行った。
これらの結果から、公開鍵暗号方式を用いた方法の処理時間は公開鍵暗号方式を用いない方法の処理時間の1000倍程度となることがわかる（Xeon 2.8GHzのマイクロプロセッサを４台用いたマシン環境のほうが、Core 2 Duo 2.53GHzのマイクロプロセッサを１台用いたマシン環境よりも性能が高い）。特に従来、２パーティしか許されず、サーバ装置が不正な処理を行う可能性を否定できないような環境では、非特許文献３のような公開鍵暗号方式を用いた方法を用いるしかなかった。第１実施形態の方法がこのような環境で使用されることで、このような環境において従来の約1000倍の高速化が可能となる。
【００６２】
一般にマルチパーティプロトコルでは、パーティ数が多いほど、重い公開鍵暗号処理の比率を上げるほど、強い攻撃者に対するセキュリティを実現できる。以下に非特許文献１−３の方法と「A.C. Yao., "How to generate and exchange secrets," Proc. of FOCS '86, pp.162-167, IEEE Press, 1986.」に記載された方法（以下「Yao」と呼ぶ）について、パーティ数と、malicious対応（セキュリティ強度）と、公開鍵暗号処理の要否との関係を示す。
【表１】
0005498429.tif 000002
このように、例えば、非特許文献３のような計算の全過程で公開鍵暗号処理を行うプロトコルであれば、２パーティで改ざんの検出と秘匿性とを実現できる（malicious対応プロトコル）。Yaoの歪曲回路計算のような計算の初段だけに公開鍵暗号方式を用いるプロトコルの場合、改ざんの検出も秘匿性も実現できず、２パーティのsemi-honest対応プロトコルとなる。非特許文献１の２パーティプロトコルでは公開鍵暗号処理は用いられないが、初段の計算をクライアント装置が行う必要があり、厳密には３パーティのsemi-honest 対応プロトコルとなる。４パーティ以上であれば、公開鍵暗号処理を用いずにmalicious対応プロトコルを構成できることが知られている。
【００６３】
図９は［表１］に示したこのような関係を、横軸を［malicious対応］の程度、縦軸を［公開鍵暗号処理］の必要性として表現したグラフである。図９において「＃１」は非特許文献１のプロトコルを表し、「＃２」は非特許文献２のプロトコルを表し、「＃３」は非特許文献３のプロトコルを表し、「＃Yao」はYaoのプロトコルを表す。「＃EMB」は第１実施形態の方法を表す。[BL1]は従来の２パーティプロトコルの性能の限界を表し、[BL2]は従来の３パーティプロトコルの性能の限界を表す。図９から判るように、本形態では、公開鍵暗号方式を用いる必要がないにもかかわらず、２パーティで改ざんの検出と秘匿性とを実現できることが判る
【００６４】
［第２実施形態の特徴］
第２実施形態も第１実施形態と同様な特徴を備える。さらに第２実施形態では、クライアント装置２１０−１が保存フェーズを行い、クライアント装置２１０−２が計算フェーズを行う。この形態ではクライアント装置２１０−１はサーバ用秘匿情報Es(Ds)とクライアント用秘匿情報Ec(Dc)とを自由に設定でき、クライアント装置２１０−２が論理回路を自由に設定できる。これにより、クライアント装置２１０−１は自らが定めた入力ビットに対応する秘匿回路計算を行う権限のみをクライアント装置２１０−２に与えることになる。すなわち、クライアント装置２１０−２は秘匿回路計算の対象となる論理回路を自由に設定できるが、その秘匿回路計算の対応する入力ビットを自由に選択することはできない。仮にクライアント装置２１０−２がクライアント用秘匿情報Ec(Dc)に対応する入力ビット以外の入力ビットに対応する秘匿回路計算を行ったとしても、正しい結果は得られない。
【００６５】
［第３実施形態の特徴］
第３実施形態も第１実施形態と同様な特徴を備える。さらに、第３実施形態ではクライアント用秘匿情報Ec(Dc)を生成するための暗号化処理が不要となる。
【００６６】
〔その他の変形例〕
本発明は上述の実施の形態に限定されるものではない。
例えば、歪曲回路情報が第１−３実施形態と異なる構成の歪曲真理値表DT(L)を含んでもよい。前述のように歪曲真理値表DT(L)は、秘匿値PWp(L),x(p(L)) (p(L)=r(L;0),…,r(L;s(L)-1))に対応する第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせと、出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bに対応するκ-1ビットの第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bと1ビットの第６ランダムビットck(L)∈Bとの排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとが関連付けられた表である。
【００６７】
第１−３実施形態では、第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせそのもの（ラベル）が歪曲真理値表DT(L)の一部とされ、当該ラベルと、第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとが関連付けられていた。
これに対して第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとを含む情報をラベルに対応する順序で配列したものを歪曲真理値表DT(L)とすることで、第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせと、第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と、排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとの関連付けがなされてもよい。このような歪曲真理値表DT(L)は、第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせ（ラベル）そのものを含む必要がない。すなわち第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとを含む情報の配列順序がラベルとしての機能を果たす。
【００６８】
s(L)個の入力ビットx(p(L))(p(L)=r(L;0),…,r(L;s(L)-1))に対応するs(L)個の第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせ(p(L)=r(L;0),…,r(L;s(L)-1))は、0以上2s(L)-1以下の整数のビット表現値に一対一対応させることができる。例えばs(L)=2, cr(L;0)=0, cr(L;1)=1の場合、２個のcp(L)又cp(L)- からなる組み合わせ(p(L)=r(L;0),r(L;1))は、以下のように0以上3以下の整数のビット表現値に一対一対応させることができる。
cr(L;0),cr(L;1): cr(L;0)+cr(L;1)*21=2
cr(L;0),cr(L;1)- : cr(L;0)+cr(L;1)-*21=0
cr(L;0)-,cr(L;1) : cr(L;0)-+cr(L;1)*21=3
cr(L;0)-,cr(L;1)-: cr(L;0)-+cr(L;1)-*21=1
一般化すると、s(L)個の第４ランダムビットCRp(L)∈{cp(L),cp(L)-} (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせは、以下のような0以上2s(L)-1以下の整数のビット表現値に一対一対応させることができる。
CRr(L;0)+CRr(L;1)*21+…+CRr(L;s(L)-1)*2s(L)-1          …(11)
【００６９】
そのため、s(L)個の第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせ（ラベル）に対応する整数に応じた順序で、当該ラベルに対応する第５ランダムビットWk(L),g(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bκ-1と排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bとを含む情報をソートして配列したものが歪曲真理値表DT(L)とされてもよい。例えば、c0=0, c1=1の場合、式(1)に例示した歪曲真理値表DT(0)が以下のように置き換えられてもよい。
(Wk(0),g(0;0,1),g(0;0,1))(+)F(W0,0,c1-)(+)F(W1,1,c0)
(Wk(0),g(0;0,0),g(0;0,0))(+)F(W0,0,c1)(+)F(W1,0,c0)           …(12)
(Wk(0),g(0;1,1),g(0;1,1))(+)F(W0,1,c1-)(+)F(W1,1,c0-)
(Wk(0),g(0;1,0),g(0;1,0))(+)F(W0,1,c1)(+)F(W1,0,c0-)
【００７０】
このようにラベルに対応する順序で上記の情報を配列したものを歪曲真理値表DT(L)とすることで、歪曲真理値表DT(L)がラベルそのものを含まなくても、歪曲回路計算部は、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに対応する情報を用い、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに一致するラベルに対応付けられた排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを当該歪曲真理値表DT(L)から得ることができる。例えば、歪曲回路計算部は、歪曲入力ビットy(p(L))∈B (p(L)=r(L;0),…,r(L;s(L)-1))からなる組み合わせに対応する以下の整数に対応する位置に配列された排他的論理和xor(x(r(L;0)),…,x(r(L;s(L)-1)))又は出力ビットg(L;x(r(L;0)),…,x(r(L;s(L)-1)))∈Bを抽出することで、ラベルに対応する情報を得ることができる。
y(r(L;0))+r(r(L;1))*21+…+r(r(L;s(L)-1))*2s(L)-1          …(13)
【００７１】
また逆に、上述した順序に一対一対応する0以上2s(L)-1以下の整数からラベルを導出することは容易である。すなわち、当該0以上2s(L)-1以下の整数に対応する式(11)の各係数CRp(L)∈{cp(L),cp(L)-} (p(L)=r(L;0),…,r(L;s(L)-1))の組み合わせCRr(L;0),…,CRr(L;s(L)-1))が、s(L)個の第４ランダムビットcp(L)∈B又はその反転ビットcp(L)-∈Bからなる組み合わせ（ラベル）となる。式(1)などから分るように、ラベルCRr(L;0),…,CRr(L;s(L)-1))[CRp(L)∈{cp(L),cp(L)-} (p(L)=r(L;0),…,r(L;s(L)-1))]に対応するg(L;x(r(L;0)),…,x(r(L;s(L)-1)))のx(r(L;0)),…,x(r(L;s(L)-1)のそれぞれは、CRp(L)=cp(L)ならばx(p(L))=0、CRp(L)=cp(L)-ならばx(p(L))=1である。よって、x(p(L))は以下を満たす。
x(p(L))=cp(L)(+)CRp(L)(p(L)=r(L;0),…,r(L;s(L)-1))
そのため、この変形例の歪曲真理値表DT(L)のCRr(L;0)+CRr(L;1)*21+…+CRr(L;s(L)-1)*2s(L)-1+1番目に配列される要素は、
【数１】
0005498429.tif 000003
とxor(cr(L;0)(+)CRr(L;0),…, cr(L;s(L)-1)(+)CRr(L;s(L)-1))又はg(cr(L;0)(+)CRr(L;0),…, cr(L;s(L)-1)(+)CRr(L;s(L)-1))とが関連付けられたものとしてソート無しで得られる。例えば、式(12)のCRr(0;0)+CRr(0;1)*21+1番目に配列される要素は以下のように得られる。
【数２】
0005498429.tif 000004
【００７２】
また、第２実施形態において、クライアント装置２１０−１とサーバ装置１２０とによって、クライアント装置２１０−２の入力部２１１に入力可能な論理回路情報ＬＣが限定され、ステップＳ１１３で許容されない論理回路情報ＬＣがサーバ装置１２０で受信された場合に、サーバ装置１２０がその後の処理を拒否することとしてもよい。この場合、サーバ装置１２０とクライアント装置２１０−２とが結託しない限り、クライアント装置２１０−２は許容されていない論理回路情報ＬＣに対応する論理回路の計算を行うことができない。
【００７３】
その他、サーバ装置とクライアント装置とが通信によって情報の受け渡しを行うのではなく、可搬型記録媒体を介して情報の受け渡しを行ってもよい。
【００７４】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７５】
１−３  秘匿データ処理システム
１１０−３１０  クライアント装置
１２０−３２０  サーバ装置
【図１】
0005498429.tif 000005
【図２】
0005498429.tif 000006
【図３】
0005498429.tif 000007
【図４】
0005498429.tif 000008
【図５】
0005498429.tif 000009
【図６】
0005498429.tif 000010
【図７】
0005498429.tif 000011
【図８】
0005498429.tif 000012
【図９】
0005498429.tif 000013