(57)【要約】      （修正有）【課題】べき乗計算のような大きな計算コストを必要とすることなく、複数の機関がもつデータを入力として、入力データの内容を秘匿したまま所定の演算を行い、得られた演算結果を利用する方法を提供する。【解決手段】秘匿演算変換システム１において、データ処理装置は、複数の機関がもつデータを入力として、ある演算を行った時と同じ結果が得られることが保証された別の演算を秘匿に実施して秘密情報を公平に取得する。更に、取得した秘密情報の機密性を根拠として、双方の秘密データの機密性を完全に守りながら、安価な計算コストにより秘匿演算を行う。【選択図】図１
2020016739.tif 000002
【特許請求の範囲】
【請求項１】
２以上のデータ処理装置で構成され、前記データ処理装置はそれぞれの秘密データを記憶する秘密データ記憶手段と、それぞれの出力データを記憶する出力データ記憶手段と、前記秘密データ、前記出力データ、前記秘密データに対して適用したい変換前演算型Aと前記出力データに対して適用したい変換後演算型Bの組み合わせを指定する演算変換方式型をそれぞれの交渉秘密情報として記憶する交渉秘密情報記憶手段と、前記秘密データを入力として、他の前記データ処理装置と連携して、前記出力データを秘匿に計算する演算処理手段と、を有し、
前記演算処理手段は、前記秘密データと他の前記データ処理装置が記憶する秘密データを入力として前記変換前演算型Aの演算を行ったときの結果と、前記出力データと前記他のデータ
処理装置の出力データを入力として前記変換後演算型Bを行ったときの結果が同じであることを保証する、
ことを特徴とする秘匿演算変換システム。
【請求項２】
前記変換前演算型Aが加算であり、前記変換後演算型Bが乗算である、請求項１に記載の秘匿演算変換システム。
【請求項３】
前記変換前演算型Aが乗算であり、前記変換後演算型Bが加算である、請求項１に記載の秘匿演算変換システム。
【請求項４】
前期演算処理手段は、実際の演算処理に先だって一部の演算処理を事前に実施する、請求項１に記載の秘匿演算変換システム。
【請求項５】
前記演算処理手段が、前記秘密データと、当該演算処理に先だってなされた演算処理の結果として前記交渉秘密情報記憶部に記憶されている前記交渉秘密情報を用いて、出力データを計算する、請求項１〜３のいずれか一項に記載の秘匿演算変換システム。
【請求項６】
前記交渉秘密情報記憶手段が、前記秘密データと前記交渉秘密情報を用いて得られた出力データを新たな交渉秘密情報として記憶する、請求項５に記載の秘匿演算経変換システム。
【請求項７】
前期演算処理手段は、前記変換前演算型Aが加算であり前記変換後演算型Bが乗算である演算処理と、前記変換前演算型Aが乗算であり前記変換後演算型Bが加算である演算処理とを組み合わせて、底とべき指数の両方を秘密データとし前記変換前演算型Aがべき乗算であり前記変換後演算型Bが乗算または加算である演算変換処理を行う、請求項１〜６のいずれか一項に記載の秘匿演算変換システム。
【請求項８】
それぞれの秘密データを記憶する秘密データ記憶ステップと、それぞれの出力データを記憶する出力データ記憶ステップと、前記交渉秘密情報をそれぞれ記憶する交渉秘密情報記憶ステップと、前記秘密データを入力として、他の前記データ処理装置と連携して、前記演算変換方式型に従って、前記出力データを秘匿に計算する演算処理ステップを有し、
前記演算処理ステップは、前記秘密データと他のデータ処理装置の秘密データを入力として前記変換前演算型Aの演算を行った時の結果と前記出力データと他のデータ処理装置のもつ出力データを入力として前記変換後演算型Bの演算を行った時の結果が同じ値であることを保証する、
ことを特徴とする秘匿演算変換方法。
【請求項９】
前記変換前演算型Aが加算であり、前記変換後演算型Bが乗算である、請求項８に記載の秘匿演算変換方法。
【請求項１０】
前記変換前演算型Aが乗算であり、前記変換後演算型Bが加算である、請求項８に記載の秘匿演算変換方法。
【請求項１１】
前記演算処理ステップは、実際の演算処理に先だって、一部の演算処理を事前に実施する、請求項８に記載の秘匿演算変換方法。
【請求項１２】
前記演算処理ステップが、前記秘密データと、当該演算処理に先だってなされた演算処理の結果として前記交渉秘密情報記憶部に記憶されている前記交渉秘密情報を用いて、出力データを計算する、請求項８〜１０のいずれか一項に記載の秘匿演算変換方法。
【請求項１３】
前記交渉秘密情報記憶ステップが、前記秘密データと前記交渉秘密情報を用いて得られた出力データを新たな交渉秘密情報として記憶する、請求項１２に記載の秘匿演算変換方法。
【請求項１４】
前記演算処理ステップは、前記変換前演算型Aが加算であり前記変換後演算型Bが乗算である演算処理と、前記変換前演算型Aが乗算であり前記変換後演算型Bが加算である演算処理とを組み合わせて、底とべき指数の両方を秘密データとし前記変換前演算型Aがべき乗算であり前記変換後演算型Bが乗算または加算である演算変換処理を行う請求項８〜１３のいずれか一項に記載の秘匿演算変換方法。
【請求項１５】
他のコンピュータと連携してデータを処理するコンピュータによって使用されるプログラムであって、それぞれの秘密データを記憶する秘密データ記憶ステップと、それぞれの出力データを記憶する出力データ記憶ステップと、前記交渉秘密情報をそれぞれ記憶する交渉秘密情報記憶ステップと、前記秘密データを入力として、他の前記データ処理装置と連携して、前記演算変換方式型に従って、前記出力データを秘匿に計算する演算処理ステップを有し、
前記演算処理ステップは、前記秘密データと他のデータ処理装置の秘密データを入力として前記変換前演算型Aの演算を行った時の結果と前記出力データとたのデータ処理装置のもつ出力データを入力として前記変換後演算型Bの演算を行った時の結果が同じ値であることを保証する、
ことを特徴とする秘匿演算変換プログラム。
【請求項１６】
前記変換前演算型Aが加算であり、前記変換後演算型Bが乗算である、請求項１５に記載の秘匿演算変換プログラム。
【請求項１７】
前記変換前演算型Aが乗算であり、前記変換後演算型Bが加算である、請求項１５に記載の秘匿演算変換プログラム。
【請求項１８】
前記演算処理ステップは、実際の演算処理に先だって、一部の演算処理を事前に実施する、請求項１５に記載の秘匿演算変換プログラム。
【請求項１９】
前記演算処理ステップが、前記秘密データと、当該演算処理に先だってなされた演算処理の結果として前記交渉秘密情報記憶部に記憶されている前記交渉秘密情報を用いて、出力データを秘匿に計算する、請求項１５〜１７のいずれか一項に記載の秘匿演算変換プログラム。
【請求項２０】
前記交渉秘密情報記憶ステップが、前記秘密データと前記交渉秘密情報を用いて得られた出力データを新たな交渉秘密情報として記憶する、請求項２１に記載の秘匿演算変換プログラム。
【請求項２１】
前記演算処理ステップは、前記変換前演算型Aが加算であり前記変換後演算型Bが乗算である演算処理と、前記変換前演算型Aが乗算であり前記変換後演算型Bが加算である演算処理とを組み合わせて、底とべき指数の両方を秘密データとし前記変換前演算型Aがべき乗算であり前記変換後演算型Bが乗算または加算である演算変換処理を行う請求項１５〜２０のいずれか一項に記載の秘匿演算変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は複数の機関がそれぞれ保持している秘密データを入力として演算Aを行ったときの結果と同じ結果を得ることができる別の演算Bに対する複数の入力を秘匿に計算し、各々の機関に秘密出力として返す秘匿演算変換システム、秘匿演算変換方法、および、秘匿演算変換プログラムに関する。
【背景技術】
【０００２】
複数の機関がもつデータを入力として入力データの内容を秘匿したまま所定の演算を行い、得られた演算結果を利用する方法が知られている。例えば、２つの機関がもつデータをn個のデータブロックからなるデータベクトルX=(X1,X2,…,Xn)、Y=(Y1,Y2,…,Yn)とし、各ベクトル位置i (1≦i≦n) のベクトル要素どうしを乗算した結果XiYiを全て加算した結果Σ1≦i≦n XiYi（以下、内積値と略記することがある。）を求めることで相関ルールを導出する方法が非特許文献１に示されている。
【０００３】
以下、図２６を用いて、非特許文献１に示された、オンラインショップP1（以下、機関P1と略記することがある。）とオンラインショップP2（以下、機関P2と略記することがある。）が顧客の物品購入の相関関係を顧客とのプライバシー同意契約に違反することなく、導出する方法について説明する。
【０００４】
最初に機関P1と機関P2は図２と図３に示すような「クレジットカード番号表」を用意し、同じクレジット番号の顧客の利用金額を同じ位置に記録する２つのベクトル、「ベクトルX」と「ベクトルY」を用意する。
以降ではベクトルX、Yの長さnをベクトル次数と呼ぶ。
【０００５】
上記のベクトルXとベクトルYを入力とした内積値がある閾値より大きい場合には機関P1と機関P2の顧客の購買行動には正の相関関係があると判断することができ、顧客の嗜好性が似ている可能性が高く、共同で商品開発することで、より顧客のニーズにあう商品を開発できる可能性がある。
【０００６】
このとき、機関P1と機関P2がそれぞれ、多くの人数の購買情報からなるベクトルX、ベクトルYを作成した上で、ベクトルX、ベクトルYの内容を相互に明らかにせず、各々が内積値のみを計算できれば顧客と機関間にあるプライバシー合意契約に抵触しない。
【０００７】
図２６において、機関P1と機関P2の双方が共通情報として、n×nの係数行列Cと、ベクトルX及びベクトルYをベクトル次数がｎより小さいｒ個のベクトルに分割する分割個数rを予め知っているとする。機関P1ではベクトルXの各要素Xi(i=1,2,・・・,n)に係数行列Cと機関P1がランダムに定めたn個の乱数Ri(i=1,2,・・・,n)を用いて計算した値を加算することによりベクトルXを秘匿した形に変形したベクトルCA=(CA1,CA2,…,CAn)、CAi=Xi+Ci,1×R1+Ci,2×R2+・・・+Ci,n×Rnを機関P2に渡す。機関P2では、Cの転置行列であるCT を用いて、CTYなるn次元のベクトルに同じ値がn/r個ずつ連続するn次元のベクトル＜R1’, R1’,…,R1’, R2’,…,R2’,…,Rr’,…Rr’＞を加算して作成したベクトルCB=(CB1,CB2,…,CBn)、CBi=C1,i×Y1+C2,i×Y２+…+Cn,i×Yn+R1’、・・・、CBn/r=C1,n/r×Y1+C2,n/r×Y２+…+Cn,n/r×Yn+R1’、 CBn/r+1=C1,(n/r+1)×Y1+C2,(n/r+1)×Y２+…+Cn,(n/r+1)×Yn+R2’、・・・、CB2n/r=C1,2n/r×Y1+C2,2n/r×Y２+…+Cn,2n/r×Yn+R2’、・・・, CB(r−1)n/r+1=C1, ((r−1)n/r+1)×Y1+C2, ((r−1)n/r+1)×Y２+…+Cn, ((r−1)n/r+1)×Yn+Rr’、・・・、CBn=C1,n×Y1+C2,n×Y２+…+Cn,n×Yn+Rr’、を求めて、機関P1に送信する。また、機関P2は、ベクトルCAと自身のもつベクトルYの内積CA・Yを計算する。機関P1は自己の乱数ベクトルR=＜R1,R2,…,Rn＞と受信したベクトルCBの内積R・CBを計算し、マイナス１を乗算してΦ＝−R・CBを計算する。次に、機関P1は自己の乱数ベクトルRをn/r個ずつ加算し、r次元のベクトルDA=（DA1、DA2、・・・、DAr） 、DA1=R1+R2+・・・+Rn/r、DA2=Rn/r+1+Rn/r+2+・・・+R2n/r、・・・、DAr=R(r-1)n/r+1+R(r-1)n/r+2+・・・+Rnを計算し、機関P2へ送信する。機関P2は先に計算した内積値CA・Yと自己のもつr次元のベクトルR’=＜R1’,R2’,…,Rr’＞と機関P1より受信したr次元ベクトルDAとの内積の値DA・R’を加算することで値Ψ=CA・Y+DA・R’を計算する。機関P1と機関P2は値ΦとΨを交換してΦ＋Ψを求めることで内積値を求めることができる。
【０００８】
上記の手法では複数の秘匿データの加算後の結果のみを知らせることで加算前の値を復元できない状態に保ち、各ベクトルの値の安全性を保証できるように見えるが、問題がある。すなわち、機関P1は機関P2より受信した情報を用いて、ベクトルYに関して成り立つ情報を得ることができ、少なくともベクトルYに関して成り立つ半分の情報を明らかにできてしまう。例えば、機関P１は機関P2がCB1からCBn/rの情報を作成するのに同じR1’という乱数を利用していることを知っている。そこで、CB1−CB2＝(C1,1-C2,1)Y1+(C1,2-C2,2)Y2+・・・+(C1,n−C2,n)Yn の関係式が成り立つことが分かる。このような異なるn個の関係式があれば、機関P1はベクトルYの情報全てを明らかにできてしまう。図２６の方法では、機関P1は少なくとのn/2個の関係式を作成することができる。
また、ベクトルXを機関P1が繰り返し用いた場合、機関P2がベクトルXに関する情報を引き出すことができるという安全上の問題がある。また、n/r回のn次元のベクトルの送受信を必要としており、安全性を向上させようとすると大量の情報を送受信することとなり効率上の問題もある。
【０００９】
上記の問題を解決するため、非特許文献２では公開鍵暗号方式を用いた秘匿計算プロトコルが提案されている。この方法では１つの平文を複数の異なる暗号文に暗号化可能な確率暗号で、かつ、暗号文に対し演算を実施することで平文に対する演算も実行できる準同型性をもつ確率公開鍵暗号方式を用いている。
【００１０】
ここで、公開鍵暗号方式とは暗号化するときに使う鍵と復号するときに使う鍵が異なるため、暗号化に利用する鍵を公開することで、誰でも暗号文を作成できるが、復号は復号するための鍵（秘密鍵）を知っている人以外には困難となる非対称な鍵を用いる暗号方式である。また、確率暗号とは、同一の平文を同一の鍵で暗号化すると必ず同一の暗号文を生成するRSA暗号方式のような確定暗号とは異なり、暗号化ごとに異なる乱数を利用可能なため、同じ平文であっても鍵の種類と同程度の数の暗号文に変換可能な暗号方式である。上記の性質を満たす公開鍵暗号方式の１つにElGamal暗号方式（以下、ElGamal方式と略記することがある。）がある。確率公開鍵暗号方式を使った秘匿ベクトル内積計算方法では、暗号文に対して、演算を適用することで平文に演算を施せるという準同型性を利用し、かつ、確率的に暗号文を変化させることで、暗号文に対してどのような計算が行われたかを特定することを困難にしながら、平文に対して演算を施して、秘匿ベクトルの内積を計算する。
【００１１】
以下、先の例と同じように機関P1と機関P2は図２、図３に示すような各顧客の利用金額を秘密データXi,Yi(i=1,2,・・・,n)として保持しているとする。
機関P1は自分の公開鍵K=g S (mod P) （ここで、gは原始元、Pは素数、Sは秘密鍵であり、以降、暗号文の計算では (mod P)を省略することがある。）を公開した上で、各顧客の利用金額Xiの暗号値(2XiKri, gri) （ここで、riは乱数とする）からなる暗号文ベクトルを作成し、機関P2に送信する。
【００１２】
機関P1より暗号文ベクトルを受け取った機関P2は暗号ベクトルの各i番目の暗号文の1項目、2項目ともにベクトル要素Yiを指数乗したのち、各暗号文の1項目の要素をすべて乗算し、2項目の要素同志を全て乗算した１つの暗号文（2X1Y1+X2Y2+・・・+XnYn Kr1Y1+r2Y2+・・・+rNYN, gr1Y1+r2Y2+・・・+rnYn）を作成し、最後に乱数Ψとrで撹乱した暗号文（2X1Y1+X2Y2+・・・+XNYN+Ψ Kr1Y1+r2Y2+・・・+rNYN+r, gr1Y1+r2Y2+・・・+rnYn+r）に変換して、変換後の暗号文を機関P1へ送信する。
暗号文を受け取った機関P1は暗号文2項組を自身の秘密鍵を用いて復号し、得られた平文の２の対数を求めることにより値Φ=Σ1≦i≦n XiYi + Rを得る。値Φと値Ψを機関P1、機関P2で交換することにより、互いに内積値を求めることができる。
【００１３】
しかしながら、非特許文献２の方法にも問題がある。機関P1はベクトル情報ごとにデータを暗号化する必要があり、その暗号化は指数乗の計算のような大きな計算コストを必要とする。また、機関P2もベクトル次数個の自己のもつ情報を乗算するために、暗号文を指数乗するという大きな計算コストを費やし、入力ベクトルの値に依存した大きなコストの計算が必要となる。さらに、乗算を指数乗にて計算しているため、値Φの上限はlog2Pとなり、例えば、Pが2048ビットの素数であるとすると値Φの上限は2048ビットとなり、正確な結果を得られる範囲が小さな値域の計算に限られる。
【００１４】
近年、非特許文献３の準同型性公開鍵暗号の一種であるPaillier暗号方式（以下、Paillier方式と略記することがある。）を用いて、秘匿計算を行う方法が一般的に用いられている。
Paillier方式では公開鍵を提供する公開者が秘密鍵となる２つの大きな素数ｐ、ｑを選定し、Ｎ＝ｐ×ｑを満たすＮと乱数ｋを選び、ｇ＝（１＋ｋＮ）ｍｏｄＮ２を満たすｇを求めることにより公開鍵Ｐｋ＝（Ｎ，ｇ）を作成する。
平文ｍを暗号化するには乱数ｒを用いて、Ｃ＝ｇｍｒＮｍｏｄＮを計算することで暗号文Ｃを作成する。一方、復号はｍ＝（Ｌ（ＣλｍｏｄＮ２）／Ｌ（ｇλｍｏｄＮ２））ｍｏｄＮを計算することで実行される。ここで、関数Ｌ（Ｕ）はＬ（Ｕ）＝（Ｕ−１）／Ｎと定義され、λはｐ−１とｑ−１の最小公倍数ｌｃｍ（ｐ−１、ｑ−１）と等しいとする。λはユークリッドの互除法により効率よく求めることができる。
【００１５】
Paillier方式で平文ｍ１を乱数ｒ１、公開鍵Ｐｋにより暗号化し暗号文Ｃ１を作成することをＣ１＝ＥＰｋ（ｍ１、ｒ１）と示すとする。暗号文Ｃ１を用いて、Ｃ２＝Ｃ１×ｇｍ２ ｍｏｄＮを計算するとＣ２はＣ２＝ｇｍ１＋ｍ２ｒ１Ｎ ｍｏｄＮ＝ＥＰｋ（ｍ１＋ｍ２、ｒ１）となり、加法準同型性を満たすことにより、暗号文Ｃ１を利用してｍ１にｍ２を加算した暗号文Ｃ２を作成できる。
同様に、暗号文Ｃ１を用いて、Ｃ３＝Ｃ１ｍ２ ｍｏｄＮを計算すると、Ｃ３はＣ３＝ｇｍ１ｍ２（ｒ１ｍ２）Ｎ  ｍｏｄ Ｎ＝ＥＰｋ（ｍ１ｍ２、ｒ１ｍ２）を満たし、乗法準同型性を満たすことより、Ｃ１を利用してｍ１にｍ２を乗算した暗号文Ｃ３を作成できる。
【００１６】
上記のようにPaillier方式ではElGamal方式と同様に、暗号文に乗算、累乗演算を適用することにより秘匿計算を実行することができる。暗号化においては乱数ｒを用いた計算ｒＮ、復号においてはＬ（ｇλ ｍｏｄＮ２）は平文が決定する以前に計算可能であるため、暗号化、復号ともに平文、暗号文に依存したべき乗計算１回を必要とし、復号では追加で除算を必要とする。指数部に平文ｍを表現するが、Paillier方式ではElGamal方式とは異なり、ｍがとり得る値域はＮの定数倍と大きな範囲である。
【００１７】
しかしながら、非特許文献３の方法にも問題がある。公開鍵暗号方式に基づくこの方法では、乗算を行う場合には入力決定後にべき乗演算を必要とし、さらにビット長の大きな除算を必要とすることより秘匿計算を実現するためには大きな計算コストを必要とする。
【００１８】
さらに、非特許文献２、非特許文献３の方法のような公開鍵暗号方式を用いる方法はそれぞれの仮定に基づいた相対的な機密性の保証しか行われていない。すなわち、非特許文献２で提案されている方法に用いられる可能性が高いElGamal方式はＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題と呼ばれる難しいと思われている問題が効率良く解けない限り安全だと証明されているが、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が本当に効率良く解くことができないかは現在までに証明されていない。同様に、非特許文献３で提案されている方法も、合成数剰余問題と呼ばれる難しいと思われている問題が効率良く解けない限り安全だと証明されているが、合成数剰余問題が効率良く解くことができないことは証明されていない。現在の計算機環境で合成数剰余問題の安全性を保証するには４０９６ビット長の鍵を用意する必要があり、将来的にも必要となる鍵長は指数関数的に大きくなり、計算コストが増大する可能性がある。また、量子コンピュータ等の新世代の計算機が開発された場合には、これらの仮定は維持できなくなると予測されている。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】Jaideep Vaidya and Chris Clifton, “Privacy preserving association rule mining in vertically partitioned data,” Proceeding of the 8th ACM SIGMOD International Conference on Knowledge Discovery and Data Mining (KDD2002), pp.639-644, 2002.
【非特許文献２】Bart Goethals, Sven Laur, Helger Lipman and Taneli Mielikainen, “On privacy scalar product computation for privacy-preserving data mining,” Proceeding of the 7th Annual Information Security and Cryptology (ICISC2004), pp.104-120, 2004.
【非特許文献３】Pascal Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” Proceeding of International Conference on the Theory and Applications of Cryptographic Techniques (EURO CRYPT’99), pp.223-238, 1999.
【発明の概要】
【発明が解決しようとする課題】
【００２０】
本発明はこれらの背景技術の問題点に鑑みてなされたものであり、従来の準同型性公開鍵暗号を利用した秘匿計算とは機密性の根拠が異なり、ある秘匿演算を別の秘匿演算に変換することにより、双方が同意した意味のある秘密情報（以下、交渉秘密情報と記すことがある。）を公平に得ることを可能とする。さらに、得られた交渉秘密情報の機密性を根拠として、秘密データの機密性を完全に守りながら、交渉秘密情報と秘密データを用いた安価なコストの計算により秘匿計算を行うことができる秘匿演算変換システムおよび秘匿演算変換方法を提供することを目的とする。
【課題を解決するための手段】
【００２１】
係る目的を解決するため、本発明の秘匿演算変換システムは、２以上のデータ処理装置で構成され、前記データ処理装置はそれぞれの秘密データを記憶する秘密データ記憶手段と、それぞれの出力データを記憶する出力データ記憶手段と、前記秘密データ、前記出力データ、前記秘密データに対して適用したい変換前演算型Aと前記出力データに対して適用したい変換後演算型Bの組み合わせを指定する演算変換方式型を交渉秘密情報として記憶する交渉秘密情報記憶手段と、前記秘密データを入力として、他の前記データ処理装置と連携して、前記出力データを秘匿に計算する演算処理手段と、を有し、
前記演算処理手段は、前記秘密データと他の前記データ処理装置が記憶する秘密データを入力として前記変換前演算型Aの演算を行ったときの結果と、前記出力データと前記他のデータ処理装置の出力データを入力として前記変換後演算型Bを行ったときの結果が同じであることを保証する、
ことを特徴とする。
【００２２】
前記変換前演算型Aは加算であり、前記変換後演算型Bは乗算であるとしてもよい。
【００２３】
前記変換前演算型Aは乗算であり、前記変換後演算型Bは加算であるとしてもよい。
【００２４】
前記演算処理手段は、実際の演算処理に先だって、一部の演算処理を事前に実施することとしてもよい。
【００２５】
前記演算処理手段は、前記秘密データと、当該演算処理に先だってなされた演算処理の結果として前記交渉秘密情報記憶部に記憶されている前記交渉秘密情報を用いて、出力データを計算することとしてもよい。
【００２６】
前記交渉秘密情報記憶手段は、前記秘密データと前記交渉秘密情報を用いて得られた出力データを新たな交渉秘密情報として記憶することとしてもよい。
【００２７】
前記演算処理手段は、前記変換前演算型Aが加算であり前記変換後演算型Bが乗算である演算処理と、前記変換前演算型Aが乗算であり前記変換後演算型Bが加算である演算処理とを組み合わせて、底とべき指数の両方を秘密データとし、前記変換前演算型Aがべき乗算であり前記変換後演算型Bが乗算または加算である演算変換処理を行うこととしてもよい。
【００２８】
係る目的を解決するため、本発明の秘匿演算変換方法は、前記データ処理装置はそれぞれの秘密データを記憶する秘密データ記憶ステップと、それぞれの出力データを記憶する出力データ記憶ステップと、前記交渉秘密情報を記憶する交渉秘密情報記憶ステップと、前記秘密データを入力として、他の前記データ処理装置と連携して、前記演算変換方式型に従って、前記出力データを秘匿に計算する演算処理ステップを有し、
前記演算処理ステップは、前記秘密データと他のデータ処理装置の秘密データを入力として前記変換前演算型Aの演算を行った時の結果と前記出力データと他のデータ処理装置のもつ出力データを入力として前記変換後演算型Bの演算を行った時の結果が同じ値であることを保証する、
ことを特徴とする。
【００２９】
前記変換前演算型Aは加算であり、前記変換後演算型Bは乗算であるとしてもよい。
【００３０】
前記変換前演算型Aは乗算であり、前記変換後演算型Bは加算であるとしてもよい。
【００３１】
前記演算処理ステップは、実際の演算処理に先だって、一部の演算処理を事前に実施することとしてもよい。
【００３２】
前記演算処理ステップは、前記秘密データと、当該演算処理に先だってなされた演算処理の結果として前記交渉秘密情報記憶部に記憶されている前記交渉秘密情報を用いて、出力データを計算することとしてもよい。
【００３３】
前記交渉秘密情報記憶ステップは、前記秘密データと前記交渉秘密情報を用いて得られた出力データを新たな交渉秘密情報として記憶することとしてもよい。
【００３４】
前記演算処理ステップは、前記変換前演算型Aが加算であり前記変換後演算型Bが乗算である演算処理と、前記変換前演算型Aが乗算であり前記変換後演算型Bが加算である演算処理とを組み合わせて、底とべき指数の両方を秘密データとし、前記変換前演算型Aがべき乗算であり前記変換後演算型Bが乗算または加算である演算変換処理を行うこととしてもよい。
【００３５】
係る目的を達成するため、本発明の秘匿演算変換プログラムは、他のコンピュータと連携してデータを処理するコンピュータによって使用されるプログラムであって、
前記データ処理装置はそれぞれの秘密データを記憶する秘密データ記憶ステップと、それぞれの出力データを記憶する出力データ記憶ステップと、前記交渉秘密情報を記憶する交渉秘密情報記憶ステップと、前記秘密データを入力として、他の前記データ処理装置と連携して、演算変換方式型に従って、前記出力データを秘匿に計算する演算処理ステップを有し、
前記演算処理ステップは、前記秘密データと他のデータ処理装置の秘密データを入力として前記変換前演算型Aの演算を行った時の結果と前記出力データとたのデータ処理装置のもつ出力データを入力として前記変換後演算型Bの演算を行った時の結果が同じ値であることを保証する、
ことを特徴とする。
【００３６】
前記変換前演算型Aは加算であり、前記変換後演算型Bは乗算であるとしてもよい。
【００３７】
前記変換前演算型Aは乗算であり、前記変換後演算型Bは加算であるとしてもよい。
【００３８】
前記演算処理ステップは、実際の演算処理に先だって、一部の演算処理を事前に実施することとしてもよい。
【００３９】
前記演算処理ステップは、前記秘密データと、当該演算処理に先だってなされた演算処理の結果として前記交渉秘密情報記憶部に記憶されている前記交渉秘密情報を用いて、出力データを計算することとしてもよい。
【００４０】
前記交渉秘密情報記憶ステップは、前記秘密データと前記交渉秘密情報を用いて得られた出力データを新たな交渉秘密情報として記憶することとしてもよい。
【００４１】
前記演算処理ステップは、前記変換前演算型Aが加算であり前記変換後演算型Bが乗算である演算処理と、前記変換前演算型Aが乗算であり前記変換後演算型Bが加算である演算処理とを組み合わせて、底とべき指数の両方を秘密データとし、前記変換前演算型Aがべき乗算であり前記変換後演算型Bが乗算または加算である演算変換処理を行うこととしてもよい。
【発明の効果】
【００４２】
本発明によれば、双方が同意した関係を満たす交渉秘密情報を公平に得ることを可能とする。さらに、得られた交渉秘密情報の機密性を根拠として、秘密データの機密性を完全に守りながら、秘密データと交渉秘密情報を用いた加算・乗算等の安価なコストの計算により秘匿計算を行う秘匿演算交換システムを実現することができる。
【図面の簡単な説明】
【００４３】
【図１】本発明の秘匿演算変換システムの構成を示すブロック図である。
【図２】複数の機関による事前の取り決めに基づいて決定されている顧客のカード番号の順序付けにより、機関Ｐ１がもつ顧客ごとの利用金額を列状に並べた表である。
【図３】複数の機関による事前の取り決めに基づいて決定されている顧客のカード番号の順序付けにより、機関Ｐ２がもつ顧客ごとの利用金額を列状に並べた表である。
【図４】本発明の秘匿演算変換システムの構成要素の機能を示す機能ブロック図である。
【図５】「演算変換処理（交渉秘密情報無加算乗算変換処理）」の手順の概要を説明するための処理概要図である。
【図６】ElGamal方式を利用した「演算変換処理（交渉秘密情報無加算乗算変換処理）」の手順の概要を説明する処理概要図である。
【図７】Paillier方式を利用した「演算変換処理（交渉秘密情報無加算乗算変換処理）」の手順の概要を説明する処理概要図である。
【図８】「演算変換処理（交渉秘密情報無乗算加算変換処理）」の手順の概要を説明するための処理概要図である。
【図９】ElGamal方式を利用した「演算変換処理（交渉秘密情報無乗算加算変換処理）」の手順の概要を説明する処理概要図である。
【図１０】Paillier方式を利用した「演算変換処理（交渉秘密情報無乗算加算変換処理）」の手順の概要を説明する処理概要図である。
【図１１】「演算変換処理（交渉秘密情報有変換処理）」の手順の概要を説明するための処理概略図である。
【図１２】「秘匿演算変換処理」の手順を説明するためのフローチャートである。
【図１３】「交渉秘密情報利用指定処理」の手順を説明するためのフローチャートである。
【図１４】「交渉秘密情報有演算変換処理」の手順を説明するためのフローチャートである。
【図１５】「交渉秘密情報有乗算加算変換処理」の手順を説明する処理概要図である。
【図１６】「交渉秘密情報有加算乗算変換処理」の手順を説明する処理概要図である。
【図１７】「交渉秘密情報無演算変換処理」の手順を説明するためのフローチャートである。
【図１８】「交渉秘密情報無乗算加算変換処理」で実施する演算方式の選定手順を説明するためのフローチャートである。
【図１９】「交渉秘密情報無加算乗算変換処理」で実施する演算方式の選定手順を説明するためのフローチャートである。
【図２０】「交渉秘密情報取得処理」の手順を説明するためのフローチャートである。
【図２１】「交渉秘密情報更新処理」の手順を説明するフローチャートである。
【図２２】図１３に示す「交渉秘密情報無演算変換処理」で実行される「二段階交渉秘密情報無加算乗算変換処理」の一例である入力前計算と分割を利用した処理を説明する処理概要図である。
【図２３】図１３に示す「交渉秘密情報無演算変換処理」で実行される「二段階交渉秘密情報無乗算加算変換処理」の一例である入力前計算と分割を利用した処理を説明する処理概要図である。
【図２４】「秘匿べき乗算加算演算変換処理（指数部乗算）」を説明する処理概要図である。
【図２５】「秘匿べき乗算加算演算変換処理（指数部加算）」を説明する処理概要図である。
【図２６】非特許文献１に示された秘匿内積計算方法の手順の概要を説明するための処理概念図である。
【発明を実施するための形態】
【００４４】
（本発明の構成）
本発明の秘匿演算変換システムは、機関P1もしくは機関P2のもつ秘密データＸ、秘密データＹについて、第三者の助けなしにある演算Ａを秘密データＸと秘密データＹに対して適用したときと同じ結果を得ることができる別の演算Ｂに対する入力の組合せOutputX、OutputYを秘匿に計算することで、機関P1、機関P2の双方が同意した意味のある秘匿情報を公平に得るための情報交換システムである。以下、秘匿演算変換システムの基本構成について図面を参照しながら説明する。
【００４５】
図１に示すように、本発明の秘匿演算変換システム１は、機関P1と機関P2それぞれに設置された２台のデータ処理装置１００と、それらを接続する通信線２００とで構成される。２台のデータ処理装置１００は通信線２００を通じて互いにデータを送受信することで連携して秘匿演算変換処理を実行する。
【００４６】
データ処理装置１００は、例えばＰＣサーバやメインフレームなどの中に構築され、制御部１１０、通信部１２０、記憶部１３０、操作部１４０、インタフェース部１５０、演算処理部１６０から構成される。
【００４７】
制御部１１０はＣＰＵ(Central Processing Unit) などで構成され、データ処理装置１００の各部を制御・統制する。すなわち、操作部１４０からの「秘匿演算変換処理開始信号」を受けて、前記演算Aと前記演算Bに対応して規定されている演算変換方式型（以下、Typeと略記することがある。）を指定し、記憶部１３０に予め格納されている演算処理に必要な情報を読み出して演算処理部１６０での演算処理を実行させ、必要に応じて演算処理部１６０での演算処理結果を記憶部１３０に格納する、秘匿演算変換に必要な情報を通信部１２０を介して相手機関に送出する、演算処理部１６０での演算結果をＩ／Ｆ部１５０を介して表示・出力する等の機能を担う。
【００４８】
通信部１２０はＬＡＮコネクタや送受信処理用のプロセッサなどから構成され、制御部１１０からの制御によって、通信線２００を通じて相手機関のデータ処理装置１００との通信を行う。
【００４９】
記憶部１３０はハードディスクやＲＡＭ（Random Access Memory）などの記憶装置から構成され、演算処理部１６０での演算処理に必要な、自己の秘密データ、演算変換処理方式データ等のデータが予め格納されており、必要に応じて演算処理部１６０での演算結果等も交渉秘密情報として格納する。
【００５０】
ここで「秘密データ」とは「顧客情報」や「秘密ベクトル」などの非公開の情報をいう。また、「顧客情報」とは各機関を利用した顧客の情報であり、「秘密ベクトル」とは、複数の機関が共通して知っているＩＤによって、顧客情報を並び替え、ある機関が持っている秘密ベクトルの各ベクトル位置の情報を提供顧客と別の機関が持っている秘密ベクトルの同じベクトル位置の情報を提供した顧客が同一となるように、双方の機関で共通した認識を得て整列された情報とする。
【００５１】
ここで「演算変換処理方式データ」とは、演算処理部１６０で実行される各種の秘匿演算処理方式を決定するためのデータであり、演算変換方式型Typeを指定する情報や交渉秘密情報利用有無を指定する情報等がある。
【００５２】
また、「交渉秘密情報」とは演算処理部１６０で演算処理を行うことにより得られた、双方が同意して作成された秘密情報であり、機関P1、機関P2が秘密データＸ，秘密データＹと出力データOutputX、OutputYを含む情報を、機関P1，機関P2双方が同じ索引Idを付けてそれぞれ記憶部１３０に記憶する秘密データSecretX[Id]、SecretY[Id]をいう。後に説明する「秘匿演算変換処理」では、記憶部１３０に記憶されている以前に作成された交渉秘密情報を利用して演算変換処理を行う場合もあるが、詳細は後述する。
【００５３】
操作部１４０はデータ処理装置１００の外面上に構成されている各種ボタンなどによって構成される。ユーザにより所定のボタンが押されると、制御部１１０に対し「秘匿演算変換処理開始通知」を送信する。秘匿演算変換処理開始通知は、秘匿演算変換処理を開始するためのトリガーとなる信号である。
【００５４】
Ｉ／Ｆ部１５０は例えばＵＳＢ（Universal Serial Bus）コネクタやビデオ出力端子などから構成され、外部の装置（例えばＰＣやモニタなど）へ処理結果を送信する。
【００５５】
（本発明の実施形態１）
以上、秘匿演算変換システム１の構成と各部の機能について説明したが、次に、図４を用いて、本発明の実施形態１に係る演算処理部１６０での「秘匿演算変換処理」と「交渉秘密情報取得処理」の概要について説明する。
なお、簡略化の為、図４では制御部１１０を割愛したが、各構成要素間の情報の授受、機関P1、機関P2間の送受信は、制御部１１０によって制御・統制されていることは勿論である。
【００５６】
演算処理部１６０での「秘匿演算変換処理」は操作部１４０からの「秘匿演算変換処理開始通知」により開始される。
機関P1及び機関P2の秘匿演算変換処理部１６１は連携して、自己の秘密データと相手機関の秘密データに演算Ａを適用して得られる結果と同じ結果を得られるような演算Ｂの入力の組OutputX、OutputYをそれぞれ秘匿に計算し、機関P1は自己の秘密出力データOutputXのみを、機関P2は自己の秘密データ出力OutputYのみを取得する。
【００５７】
機関P1の交渉秘密情報取得処理部１６２は、秘匿演算変換処理部１６１で取得した秘密出力データOutputX、秘密データＸ，演算変換方式型Typeを明記する情報（例えば、Type=1なら乗算から加算への変換を、Type≠1なら加算から乗算への変換を示す情報）をObjectXとしてまとめる。
同様に、機関P2の交渉秘密情報取得処理部１６２も秘密出力データOutputY、秘密データＹ、演算変換方式型TypeをObjectYとしてまとめる。
さらに、機関P1及び機関P2は連携して、ObjectXとObjectYに付ける、両機関で同一の索引Idを決定し、交渉秘密情報SecretX[Id]として、それぞれの記憶部１３０に格納する。
以下、秘匿演算変換処理部１６１での演算変換処理に使用された秘密データX、秘密データYと交渉秘密情報取得処理部１６２で記憶部１３０に格納された秘密データX、秘密データYを弁別する目的で、交渉秘密情報として記憶部１３０に格納された秘密データX、秘密データYを、それぞれ、演算変換入力InputX、演算変換入力InputYと記すことがある。
また、機関P1、機関P2で求められた秘密出力データOutputX、秘密出力データOutputYと交渉秘密情報取得処理部１６２で記憶部１３０に格納された秘密出力データOutputX、秘密出力データOutputYを弁別する目的で、交渉秘密情報として記憶部１３０に格納された秘密出力データOutputX、秘密出力データOutputYを、それぞれ演算変換出力OutputX、演算変換出力OutputYと記すことがある。
【００５８】
図５は秘匿演算変換処理部１６１での秘匿演算変換処理と交渉秘密情報取得処理部１６２での交渉秘密情報取得処理の一例を具体的に示したものであり、機関P1が保有する秘密データX、機関P2が保有する秘密データYについて、X＋Yを求めるための演算Aを別の演算Bに変えて実施する手順を示している。
機関P1の秘匿演算変換処理部１６１は（式１）、（式２）で示される、自己の秘密データXを含んだ値CA1,CA2,CA3,DA1,DA2,DA3を計算して機関P2に送信する。
（CA1、CA2、CA3）＝（α1KA1、α3KA1、gγ1）          （１）
（DA1、DA2、DA3）＝（α2KA２、α4KA2、gγ２）         （２）
ここに、α1、α2、α3、α4 は秘密データXをX = X1/X2 と表した時、X1=α1+α2、X2 = α3+α4の関係を満たす機関P1のみが知る乱数、KA1,KA2は機関P1及び機関P2が知る公開鍵Z（＝gx）と原始元g、機関P1のみが知る乱数γ1、γ2とを用いて、KA1=Zγ1、KA2=Zγ2と表せる値、xは機関P1の秘密鍵であり、予め機関P1の記憶部１３０に格納されている。
機関P2の秘匿演算変換処理部１６１は、機関P1からのCA1、CA2、CA3、DA1、DA2、DA3を受信して、（式３）、（式４）で示される、予め機関P2の記憶部１３０に格納されている秘密データY、自己の乱数Ψ、λ１、λ2、λ3、λ4、λ5、λ6、λ7、λ8、を含んだ値CB1、CB2、CB３、CB４、CB５、CB６、CB７、CB８、DB1、DB２、DB３、DB４、DB５、DB６、DB７、DB８を計算して機関P1に送信する。
（CB1、CB2、CB３、CB４、CB５、CB６、CB７、CB８）
＝（θ1Zλ１、θ2Zλ2、β1Zλ3、θ3Zλ4、β2Zλ5、β3Zλ6、θ4Zλ7、β4Zλ8）    （３）
（DB1、DB２、DB３、DB４、DB５、DB６、DB７、DB８）
＝（gλ1DA3、gλ2DA3、gλ3CA3、gλ4DA3、gλ5CA3、gλ6CA3、gλ7DA3、gλ8CA3、）
（４）
ここに、θ1、θ2、θ3、θ4、β1、β2、β3、β4は、秘密データYをY = Y2/Y1と表した時CA1Y1+CA2Y2=β1+β2+β3+β4、DA1Y1+DA2Y2＝θ1+θ2+θ3+θ4満たす値である。
機関P1では、機関P2からのデータCBi、DBiを受信して、（式５）で示される値OutputXを求める。
OutputX = Σ1≦i≦8 CBiDBi-x／X2
(=（Σ1≦i≦4βiCA3-1+Σ1≦i≦4θiDA3-1）／X2)）
（=（ΓB1CA3-1+ΓB2DA3-1 ）／X2））
（=（(α1Y１＋α3Y２)+ (α2Y１＋α4Y２)）／X2））
（=（(α1+α2) Y１＋(α3+α4) Y２)）／X2））
≡ （X1Y1+X2Y2）／X2                 （５）
機関P2では、（式６）で示される値OutputYを求める。
OutputY = １／Y1                           （６）
（式５）、（式６）から判るように、それぞれの機関で計算したOutputX、OutputYを交換し合うことで、（式７）によって、秘密データXと秘密データYを加算した値X+Yが求まる。
OutputX×OutputY ＝ （X1Y1+X2Y2）／（X2Y1）
（=X1/X2+Y2/Y1）
＝ X＋Y                  （７）
（式７）から判るように、図５に示した演算変換処理では、機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X＋Y）を行ったときと同じ結果を得ることができる演算B（OutputX×OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができる。
以下、（式１）から（式７）に示した演算変換方式を分割加算乗算演算変換法と略記することがある。
図５は、簡単のため、機関P1の秘密データXおよび機関P2の秘密データYが１次元の場合（XあるいはYのデータ数が１つの場合）を示したが、秘密データ数がnの場合は、CA1i,CA2i, CA3i, DA1i,DA2i,DA3i,CB1i,CB2i,CB3i,CB4i,CB5i,CB6i,CB7i,CB8i,
DB1i,DB2i,DB3i,DB4i,DB5i,DB6i,DB7i,DB8i（i=1,2,3,・・・n）について同様の計算と情報の交換を行うことでΣ1≦i≦n( Xi＋Yi)を求めることができる。
機関P1の交渉秘密情報取得処理部１６２では、演算変換入力InputX、演算変換出力OutputX、Type（図５では演算Aである加算を演算Bである乗算に変換したという情報）を含むObjectXを求め、交渉秘密情報SecretX[Id]として設定して、記憶部１３０に格納する。
同様に、機関P2の交渉秘密情報取得処理部１６２では、演算変換入力InputY、演算変換出力OutputY、演算変換処理の型Type（図５では演算Aである加算を演算Bである乗算に変換したという情報）を含むObjectYを求め、交渉秘密情報SecretY[Id]として設定して、記憶部１３０に格納する。
なお、交渉秘密情報SecretX[Id]と交渉秘密情報SecretY[Id]におけるIdは同一の番号としておく。
【００５９】
図５では機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X＋Y）を行ったときと同じ結果を得ることができる演算B（OutputX×OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができることを示した。
同様の演算変換は良く知られた、秘匿性に優れるElGamal方式を利用することでも実現可能であり、図６を用いて説明する。
図６において、機関P1の秘匿演算変換処理部１６１は（式８）、（式９）で示される、自己の秘密データXを含んだ値CA1、CA2を計算して機関P2に送信する。
CA1 = 2XPKγ1                  （８）
CA2 = gγ1                      （９）
ここに、ｇは機関P1、機関P2が共有する原始元、PK（＝ｇSK）は公開鍵、SKは機関P1の秘密鍵、γ1は機関P1のみが知る乱数であり、予め機関P1の記憶部１３０に格納されている。
機関P2の秘匿演算変換処理部１６１は機関P1からのCA1、CA2を受信して（式１０）、（式１１）で示される自己の秘密データYを含んだ値CB1、CB2を計算して機関P1に送る。
CB１=（2YCA1）1/ΨPKγ2         （１０）
CB2 =（CA2）1/Ψgγ2             （１１）
ここに、Ψ、γ2は機関P2のみが知る乱数であり、予め、機関P2の記憶部１３０に格納されている。
機関P1では、機関P2からのデータCB1、CB2を受信して、（式１２）で示される値OutputXを求める。
OutputX = log2(CB1／(CB2)SK)
（= log2(2（X+Y）／Ψ）PK(γ1+γ2)／Ψ／(g(γ1+γ2)/Ψ)SK)
（= Log2(2(X+Y)/Ψ) ）
（=（X+Y）／Ψ）            
≡ Φ                    （１２）
機関P2では、（式１３）で示される値OutputYを求める。
OutputY=Ψ                     （１３）
（式１２）、（式１３）から判るように、機関P1で計算したOutputXと機関P2のOutputYを交換し合うことで、（式１４）によって、秘密データXと秘密データYを加算した値X+Yが求まる。
OutputX×OutputY = Φ×Ψ
＝ X＋Y       （１４）
（式１４）から判るように、図６に示した演算変換処理では、機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X＋Y）を行ったときと同じ結果を得ることができる演算B（OutputX×OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができる。
以下、（式８）から（式１４）に示した演算変換方式をElGamal加算乗算演算変換法と略記することがある。
図６は、簡単のため、機関P1の秘密データXおよび機関P2の秘密データYが１次元の場合（XあるいはYのデータ数が１つの場合）を示したが、秘密データ数がnの場合は、CA1i,CA2i,CB1i,CB2i（i=1,2,3,・・・n）について同様の計算と情報の交換を行うことで
Σ1≦i≦n( Xi＋Yi)を求めることができる。
機関P1の交渉秘密情報取得処理部１６２では、演算変換入力InputX、演算変換出力OutputX、Type（図６では演算Aである加算を演算Bである乗算に変換したという情報）を含むObjectXを求め、交渉秘密情報SecretX[Id]として設定して、記憶部１３０に格納する。
同様に、機関P2の交渉秘密情報取得処理部１６２では、演算変換入力InputY、演算変換出力OutputY、Type（図６では演算Aである加算を演算Bである乗算に変換したという情報）を含むObjectYを求め、交渉秘密情報SecretY[Id]として設定して、記憶部１３０に格納する。
なお、交渉秘密情報SecretX[Id]と交渉秘密情報SecretY[Id]におけるIdは同一の番号としておく。
【００６０】
図６では機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X＋Y）を行ったときと同じ結果を得ることができる演算B（OutputX×OutputY）に対する複数の入力OutputX、OutputYを秘匿性に優れるElGamal方式を用いて計算できることを示した。
同様の演算変換は良く知られた、秘匿性に優れるPaillier方式を利用することでも実現可能であり、図７を用いて説明する。
図７において、機関P1の秘匿演算変換処理部１６１は（式１５）で示される、自己の秘密データXを含んだ値CA1を計算して機関P2に送信する。
CA1 = ｇXγ１NmodN              （１５）
ここに、γ１は機関P1のみが知る乱数、N、ｇは、N=p×q、g=(1+kN)modN2の関係を満たす公開鍵であり、予め、機関P1及び機関P2の記憶部１３０に格納されている。
なお、p,qは大きな素数であり、秘密鍵として、予め機関P1の記憶部１３０に格納されており、kは機関P1のみが知る乱数である。
機関P2の秘匿演算変換処理部１６１は機関P1からのCA1を受信して（式１６）で示される自己の秘密データYを含んだ値CB1を計算して機関P1に送る。
CB１ = (gYCA１)１/ΨmodN         （１６）
ここに、Ψは機関P2のみが知る乱数であり、予め、機関P2の記憶部１３０に格納されている。
機関P1では、機関P2からのデータCB1を受信して、（式１７）で示される値OutputXを求める。
OutputX = (L(CB1modN2／L(gλmodN2))modN
（= (X+Y)／Ψ）
≡ Φ              （１７）
ここに、λは機関P1のみが知る秘密鍵であり、大きな素数p,qについて（p-1）と（q-1）の最小公倍数であり、予め、機関P1の記憶部１３０に格納されている。
また、L(U)は、L(U)＝(U−１)／Nを満たす関数である。
機関P2では、（式１８）で示される値OutputYを求める。
OutputY=Ψ                （１８）
（式１７）、（式１８）から判るように、機関P1で計算したOutputXと機関P2のOutputYを交換し合うことで、（式１９）によって、秘密データXと秘密データYを加算した値X+Yが求まる。
OutputX×OutputY = Φ×Ψ
＝ X＋Y                   （１９）
（式１９）から判るように、図７に示した演算変換処理では、機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X＋Y）を行ったときと同じ結果を得ることができる演算B（OutputX×OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができる。
以下、（式１５）から（式１９）に示した演算変換方式をPaillier加算乗算演算変換法と略記することがある。
図７は、簡単のため、機関P1の秘密データXおよび機関P2の秘密データYが１次元の場合（XあるいはYのデータ数が１つの場合）を示したが、秘密データ数がnの場合は、CA1i、CB1i（i=1,2,3,・・・n）について同様の計算と情報の交換を行うことでΣ1≦i≦n( Xi＋Yi)を求めることができる。
機関P1の交渉秘密情報取得処理部１６２では、演算変換入力InputX、演算変換出力OutputX、Type（図７では演算Aである加算を演算Bである乗算に変換したという情報）を含むObjectXを求め、交渉秘密情報SecretX[Id]として設定して、記憶部１３０に格納する。
同様に、機関P2の交渉秘密情報取得処理部１６２では、演算変換入力InputY、演算変換出力OutputY、Type（図７では演算Aである加算を演算Bである乗算に変換したという情報）を含むObjectYを求め、交渉秘密情報SecretY[Id]として設定して、記憶部１３０に格納する。
なお、交渉秘密情報SecretX[Id]と交渉秘密情報SecretY[Id]におけるIdは同一の番号としておく。
【００６１】
以上、分割加算乗算演算変換法、ElGamal加算乗算演算変換法、Paillier加算乗算演算変換法による、機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X＋Y）を行ったときと同じ結果を得ることができる演算B（OutputX×OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算する方法について説明したが、これらの方式を組み合わせた演算変換の実行も可能であることは勿論である。
すなわち、例えば、秘密データX1と秘密データY1に関する演算時にはPaillier加算乗算演算変換法による演算変換を行い、秘密データX2,X3,X4,・・・と、秘密データY2,Y3,Y4,・・・に関する演算時には、分割加算乗算演算変換法による演算変換を行う等の任意の組み合わせも可能である。
【００６２】
図５では機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X＋Y）を行ったときと同じ結果を得ることができる演算B（OutputX×OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができることを示した。
次に、図８によって、機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X×Y）を行ったときと同じ結果を得ることができる演算B（OutputX＋OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができることを示す。
【００６３】
機関P1の秘匿演算変換処理部１６１は（式２０）、（式２１）で示される、自己の秘密データXを含んだ値CA1、CA2、CA3、DA1、DA2、DA3を計算して機関P2に送信する。
（CA1、CA2、CA3）＝（α1KA1、α3KA1、gγ1）          （２０）
（DA1、DA2、DA3）＝（α2KA２、α4KA2、gγ２）         （２１）
ここに、α1、α2はX=α1+α2の関係を満たす機関P1のみが知る乱数、α3、α4はα3+α4=1の関係を満たす機関P1のみが知る乱数、KA1,KA2は機関P1及び機関P2が知る公開鍵Z（＝gx）と原始元g、機関P1のみが知る乱数γ1、γ2とを用いて、KA1=Zγ1、KA2=Zγ2と表せる値、xは機関P1の秘密鍵であり、予め機関P1の記憶部１３０に格納されている。
機関P2の秘匿演算変換処理部１６１は、機関P1からのCA1、CA2、CA3、DA1、DA2、DA3を受信して、（式２２）、（式２３）で示される、予め機関P2の記憶部１３０に格納されている秘密データY、自己の乱数Ψ、λ１、λ2、λ3、λ4、λ5、λ6、λ7、λ8、を含んだ値CB1,CB2,CB３,CB４,CB５,CB６,CB７,CB８,DB1,DB２,DB３,DB４,DB５,DB６,DB７,DB８を計算して機関P1に送信する。
（CB1、CB2、CB３、CB４、CB５、CB６、CB７、CB８）
＝（θ1Zλ１、θ2Zλ2、β1Zλ3、θ3Zλ4、β2Zλ5、β3Zλ6、θ4Zλ7、β4Zλ8）  （２２）
（DB1、DB２、DB３、DB４、DB５、DB６、DB７、DB８）
＝（gλ1DA3、gλ2DA3、gλ3CA3、gλ4DA3、gλ5CA3、gλ6CA3、gλ7DA3、gλ8CA3、）
（２３）
ここに、θ1、θ2、θ3、θ4、β1、β2、β3、β4は、CA1Y+CA2Ψ=β1+β2+β3+β4、DA1Y+DA2Ψ＝θ1+θ2+θ3+θ4満たす値である。
機関P1では、機関P2からのデータCBi、DBiを受信して、（式２４）で示される値OutputXを求める。
OutputX = Σ1≦i≦8 CBiDBi-x
(= Σ1≦i≦8 CBiDBi-x =Σ1≦i≦4βiCA3-1+Σ1≦i≦4θiDA3-1=ΓB1CA3-1+ΓB2DA3-1 =(α1Y&#8722;α3ψ)+ (α2Y&#8722;α4ψ)=(α1+α2) Y&#8722;(α3+α4) ψ)
(=X×Y&#8722;ψ)
≡ Φ                   （２４）
機関P2では、（式２５）で示される値OutputYを求める。
OutputY = Ψ                   （２５）
（式２４）、（式２５）から判るように、それぞれの機関で計算したOutputX、OutputYを交換し合うことで、（式２６）によって、秘密データXと秘密データYを加算した値X+Yが求まる。
OutputX＋OutputY ＝ Φ＋Ψ
＝ X×Y     （２６）
（式２６）から判るように、図８に示した演算変換処理では、機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X×Y）を行ったときと同じ結果を得ることができる演算B（OutputX＋OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができる。
以下、（式２０）から（式２６）に示した演算変換方式を分割乗算加算演算変換法と略記することがある。
図８は、簡単のため、機関P1の秘密データXおよび機関P2の秘密データYが１次元の場合（XあるいはYのデータ数が１つの場合）を示したが、秘密データ数がnの場合は、
CA1i,CA2i, CA3i, DA1i,DA2i,DA3i,CB1i,CB2i,CB3i,CB4i,CB5i,CB6i,CB7i,CB8i,
DB1i,DB2i,DB3i,DB4i,DB5i,DB6i,DB7i,DB8i（i=1,2,3,・・・n）について同様の計算と情報の交換を行うことでΣ1≦i≦n( Xi×Yi)を求めることができる。
機関P1の交渉秘密情報取得処理部１６２では、演算変換入力InputX、演算変換出力OutputX、演算変換処理の型Type（図８では演算Aである乗算を演算Bである加算に変換したとする情報）を含むObjectXを求め、交渉秘密情報SecretX[Id]として設定して、記憶部１３０に格納する。
同様に、機関P2の交渉秘密情報取得処理部１６２では、演算変換入力InputY、演算変換出力OutputY、Type（図８では演算Aである乗算を演算Bである加算に変換したとする情報）を含むObjectYを求め、交渉秘密情報SecretY[Id]として設定して、記憶部１３０に格納する。
なお、交渉秘密情報SecretX[Id]と交渉秘密情報SecretY[Id]におけるIdは同一の番号としておく。
【００６４】
図８では機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X×Y）を行ったときと同じ結果を得ることができる演算B（OutputX＋OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができることを示した。
同様の演算変換は良く知られた、秘匿性に優れるElGamal方式を利用することでも実現可能であり、図９を用いて説明する。
【００６５】
図９は秘匿演算変換処理部１６１での秘匿演算変換処理と交渉秘密情報取得処理部１６２での交渉秘密情報取得処理の他の一例としてElGamal方式を利用した演算方法を示したものであり、機関P1が保有する秘密データX、機関P2が保有する秘密データYについて、演算A（X×Y）を別の演算B（OutputX+OutputY）に変えて実施する手順を示している。
機関P1の秘匿演算変換処理部１６１は（式２７）、（式２８）で示される、自己の秘密データXを含んだ値CA1,CA2を計算して機関P2に送信する。
CA1   =  2XPKγ１            （２７）
CA2  =  gγ１                 （２８）
ここに、ｇは機関P1、機関P2が共有する原始元、PK（＝ｇSK）は公開鍵、SKは機関P1の秘密鍵、γ1は機関P1のみが知る乱数であり、予め機関P1の記憶部１３０に格納されている。
機関P2の秘匿演算変換処理部１６１は、機関P1からのCA1、CA2を受信して（式２９）、（式３０）で示される自己の秘密データYを含んだ値CB1,CB2を計算して機関P1に送信する。
CB1   =  2-Ψ(CA1)YPKγ２      （２９）
CB2  =  (CA2)Ygγ２           （３０）
ここに、Ψ、γ2は機関P2のみが知る乱数であり、予め機関P2の記憶部１３０に格納されている。
機関P1では、機関P2からのデータCB1,CB2を受信して、（式３１）で示される値OutputXを求める。
OutputX  =  log2(CB1／(CB2)SK)
（=  log2(2（X×Y−Ψ）PK(γ1+γ2)Y／(g(γ１＋γ２)Y)SK)）
（=  log2(2(X×Y−Ψ)) ）
= X×Y−Ψ        （３１）
機関P2では、（式３２）で示される値OutputYを求める。
OutputY=Ψ                （３２）
（式３１）、（式３２）から判るように、機関P1で計算したOutputXと機関P2で計算したOutputYを交換し合うことで、（式３３）によって、秘密データXと秘密データYを乗算した値X×Yが求まる。
OutputX＋OutputY ＝ X×Y          （３３）
（式３３）から判るように、図９に示した演算変換処理では、機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X×Y）を行ったときと同じ結果を得ることができる演算B（OutputX＋OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができる。
以下、（式２７）から（式３３）に示した演算変換方式をElGamal乗算加算演算変換法と略記することがある。
図９は、簡単のため、機関P1の秘密データXおよび機関P2の秘密データYが１次元の場合（XあるいはYのデータ数が１つの場合）を示したが、秘密データ数がnの場合は、CA1i,
CA2i,CB1i,CB2i（i=1,2,3,・・・n）について同様の計算と情報の交換を行うことで
Σ1≦i≦n XiYiを求めることができる。
機関P1の交渉秘密情報取得処理部１６２では、演算変換入力InputX、演算変換出力OutputX、Type（図９では演算Aである乗算を演算Bである加算に変換したとする情報）を含むObjectXを求め、交渉秘密情報SecretX[Id]として設定して、記憶部１３０に格納する。
同様に、機関P2の交渉秘密情報取得処理部１６２では、演算変換入力InputY、演算変換出力OutputY、演算変換処理の型Type（図９では演算Aである乗算を演算Bである加算に変換したとする情報）を含むObjectYを求め、交渉秘密情報SecretY[Id]として設定して、記憶部１３０に格納する。
なお、交渉秘密情報SecretX[Id]と交渉秘密情報SecretY[Id]におけるIdは同一の番号としておく。
【００６６】
図９では機関P1、機関P2が保持している秘密データX,Yを入力として演算A（X×Y）を行ったときと同じ結果を得ることができる演算B（OutputX＋OutputY）に対する複数の入力OutputX、OutputYを秘匿性に優れるElGamal方式を用いて計算できることを示した。
同様の演算変換は良く知られた、秘匿性に優れるPaillier方式を利用することでも実現可能であり、図１０を用いて説明する。
図１０において、機関P1の秘匿演算変換処理部１６１は（式３４）で示される、自己の秘密データXを含んだ値CA1を計算して機関P2に送信する。
CA1 = ｇXγ1NmodN              （３４）
ここに、N、ｇは、N=p×q、g=(1+kN)modN2の関係を満たす公開鍵であり、予め、機関P1及び機関P2の記憶部１３０に格納されている。
なお、p,qは大きな素数であり、秘密鍵として、予め、機関P1の記憶部１３０に格納されており、kは機関P1のみが知る乱数である。
機関P2の秘匿演算変換処理部１６１は機関P1からのCA1を受信して（式３５）で示される自己の秘密データYを含んだ値CB1を計算して機関P1に送る。
CB１ = (g−ΨCA１)YmodN          （３５）
ここに、Ψは機関P2のみが知る乱数であり、予め、機関P2の記憶部１３０に格納されている。
機関P1では、機関P2からのデータCB1を受信して、（式３６）で示される値OutputXを求める。
OutputX = (L(CB1modN2／L(gλmodN2))modN
= (X×Y)−Ψ            （３６）
ここに、λは機関P1のみが知る秘密鍵であり、予め、機関P1の記憶部１３０に格納されている。
またL(U)は、L(U)＝（U−１）／Nを満たす関数である。
機関P2では、（式３７）で示される値OutputYを求める。
OutputY=Ψ                      （３７）
（式３６）、（式３７）から判るよに、機関P1で計算したOutputXと機関P2で計算したOutputYを交換し合うことで、（式３８）によって、秘密データXと秘密データYを加算した値X+Yが求まる。
OtputX＋OutputY ＝ X×Y        （３８）
（式３８）から判るように、図１０に示した演算変換処理では、機関P1、機関P2が保持している秘密データX、秘密データYを入力として演算A（X×Y）を行ったときと同じ結果を得ることができる演算B（OutputX＋OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算することができる。
以下、（式３４）から（式３８）に示した演算変換方式をPaillier乗算加算演算変換法と略記することがある。
図１０は、簡単のため、機関P1の秘密データXおよび機関P2の秘密データYが１次元の場合（XあるいはYのデータ数が１つの場合）を示したが、秘密データ数がnの場合は、CA1i,CB1i（i=1,2,3,・・・n）について同様の計算と情報の交換を行うことでΣ1≦i≦n( Xi×Yi)を求めることができる。
機関P1の交渉秘密情報取得処理部１６２では、演算変換入力InputX、演算変換出力OutputX、Type（図１０では演算Aである乗算を演算Bである加算に変換したとする情報）を含むObjectXを求め、交渉秘密情報SecretX[Id]として設定して、記憶部１３０に格納する。
同様に、機関P2の交渉秘密情報取得処理部１６２では、演算変換入力InputY、演算変換出力OutputY、演算変換処理の型Type（図１０では演算Aである乗算を演算Bである加算に変換したとする情報）を含むObjectYを求め、交渉秘密情報SecretY[Id]として設定して、記憶部１３０に格納する。
なお、交渉秘密情報SecretX[Id]と交渉秘密情報SecretY[Id]におけるIdは同一の番号としておく。
【００６７】
以上、分割乗算加算演算変換法、ElGamal乗算加算演算変換法、Paillier乗算加算演算変換法による、機関P1、機関P2が保持している秘密データX,Yを入力として演算A（X×Y）を行ったときと同じ結果を得ることができる演算B（OutputX＋OutputY）に対する複数の入力OutputX、OutputYを秘匿に計算する方法について説明したが、これらの方式を組み合わせた演算変換の実行も可能であることは勿論である。
すなわち、例えば、秘密データX1と秘密データY1に関する演算時にはPaillier乗算加算演算変換法による演算変換を行い、秘密データX2,X3,X4,・・・と、秘密データY2,Y3,Y4,・・・に関する演算時には、分割乗算加算演算変換法による演算変換を行う等の任意の組み合わせも可能である。
【００６８】
以上、実施形態１では、図５、図６、図７、図８、図９、図１０で説明した、分割加算乗算演算変換法、ElGamal加算乗算演算変換法、Paillier加算乗算演算変換法、分割乗算加算演算変換法、ElGamal乗算加算演算変換法、Paillier乗算加算演算変換法（以下、これらをプロトコル型PType、あるいはPTypeと略記することがある。）によって、機関P1、機関P2がそれぞれ保持している秘密データX、秘密データYを入力として演算A（X+YあるいはX×Y）を行ったときの結果と同じ結果を得ることができる別の演算B（OutputX×OutputYあるいはOutputX＋OutputY）に対する入力OutputX、OutputYを秘匿に計算し、各々の機関に秘密出力として返すことで、秘密データX、秘密データYを秘匿した状態で目的とする演算結果が取得できることが判ったが、一つの問題がある。
すなわち、それぞれの演算変換法では、機関P1、機関P2での秘匿演算変換部１６１での演算処理において、演算負荷の大きな「べき乗計算」を行っており、演算対象の秘密ベクトルX、秘密ベクトルYの次元ｎが大きくなると計算負荷の増大を招くことになり、システム全体の動作速度を低下させてしまう。
【００６９】
（本発明の実施形態２）
上記の問題点を解消するため、本発明の実施形態２では、図５、図６、図７、図８、図９、図１０で説明した、分割加算乗算演算変換法、ElGamal加算乗算演算変換法、Paillier加算乗算演算変換法、分割乗算加算演算変換法、ElGamal乗算加算演算変換法、Paillier乗算加算演算変換法のような、秘匿性に優れるが計算負荷の大きい演算法と、後述する、これらの演算時に記憶部１３０に格納された秘匿性の高い交渉秘密情報を用いて計算負荷の小さい演算行う演算法を組み合わせて、システム全体としての秘匿性と計算負荷のバランスの取れた秘匿演算変換処理を実行する。
【００７０】
図１１は実施形態２に係る演算処理部１６０でのデータ処理手続きの概略を示したものであり、大きく、秘匿演算変換処理部１６１での秘匿演算変換処理（以下、S1000と略記することがある。）と、それに続く、交渉秘密情報取得処理部１６２での交渉情報取得処理（以下、S2000と略記することがある。）に分けられる。
【００７１】
図１２は秘匿演算変換部処理１６１での処理手続きS1000の概略をフローチャートで示したものであり、秘匿演算変換処理部１６１は操作部１４０からの「秘匿演算変換処理開始通知」を受けて、S1100およびS1200で、記憶部１３０に予め蓄えられている変数Negotiationの値に基づいて、交渉秘密情報を利用した演算処理を行うか否かの判定を行い、後述する交渉秘密情報有演算変換処理（S1300）あるいは後述する交渉秘密情報無演算変換処理（S1400）に振り分ける。
【００７２】
図１３はS1100での交渉秘密情報使用指定処理の詳細を示したものである。
以下、簡略化の為、機関P1での処理動作についてのみ説明し、機関P2での機関P1と同様の処理動作の説明は割愛することがある。
また、以降の説明では、記憶部１３０に蓄えられている演算変換入力InputX、演算変換入力InputYを、それぞれ、InputX、InputYと略記することがある。
S1110では、演算の対象となる秘密データＸ、Type、交渉秘密情報を利用するか否かを示す変数Negotiationの値、PTypeの値（PTypeの値は、予め、分割加算乗算演算変換法あるいは分割乗算加算演算変換法の場合はPType=1、ElGamal加算乗算演算変換法あるいはElGamal乗算加算演算変換法の場合はPType=2、Paillier加算乗算演算変換法あるいはPaillier乗算加算演算変換法の場合はPType=3、と設定されている。）を記憶部１３０から読み出し、S1120でNegotiationの値が１か否かの判定を行う。Negotiationが１であれば、交渉秘密情報を利用する演算と判断し、交渉秘密情報Idを記憶部１３０より読み出し、Idを索引としてもつ交渉秘密情報SecretX[Id]（=（演算変換入力InputX、演算変換出力OutputX、Type））も読み出し、そのTypeをS_typeとする。S1140でSecretX[Id]中の交渉秘密情報のType（即ち、S_type）と当該演算で利用したい交渉秘密情報の型であるTypeが一致しているか否かの判定を行い、両者が一致している場合には、S1150で第１交渉情報Secret_In_XにInputX、第２交渉情報Secret_Out_XにOutputXを代入する。両者が一致していない場合には、S1160で、第１交渉情報Secret_In_XにOutputXを、第２交渉情報Secret_Out_XにInputXを代入する。
S1120でNegotiationが１でなければ、交渉秘密情報を利用しない演算と判断し、（図１２の）S1200にもどり、S1400で交渉秘密情報無演算変換処理を行う。
【００７３】
図１４はS1200で変数Negotiationが１であった場合の、S1300での交渉秘密情報有演算変換処理の前処理手順を示したものである。
S1300では秘密データＸ，第１交渉秘密情報Secret_In_X，第２交渉秘密情報Scret_Out_X，演算変換型Typeを入力として、演算変換結果OutputXを計算するが、S1310で演算変換が乗算から加算への変換か、加算から乗算への変換かを示すType値の判定を行い、Typeの値が１の場合には交渉秘密情報有乗算加算変換処理（S1320）に、そうでない場合には交渉秘密情報有加算乗算変換処理（S1330）に進む。
S1320あるいはS1330での演算処理の後、S1340に進む。
【００７４】
図１５を用いて、一例として、Type値が１である、演算Aが（X×Y）、演算Bが（OutputX＋OutputY）である場合に取得した交渉秘密情報を用いて、それと同じ演算変換方式である演算Aが（X×Y）、演算Bが（OutputX＋OutputY）である交渉秘密情報有乗算加算変換処を行うS1320での演算処理の手順を示す。
機関P1の秘匿演算変換部１６１は、自身の秘密データXと記憶部１３０に格納されている第１交渉秘密情報Secret_In_Xを用いて、（式３９）で示されるCAを作成し、機関P2に送る。
CA = X+Secret_In_X           （３９）
同様に、機関P2の秘匿演算変換部１６１は、自身の秘密データYと記憶部１３０に格納されている第１交渉秘密情報Secret_In_Yを用いて、（式４０）で示されるCBを作成し、機関P1に送る。
CB = Y+Secret_In_Y           （４０）
その後、機関P1、機関P2はそれぞれ、（式４１）、（式４２）で示される秘密出力OutputX、OutputYを計算する。
OutputX = CB・X+Secret_Out_X
（= (Y+Secret_In_Y)×X+Secret_Out_X）
（= X・Y+X・Secret_In_Y+Secret_Out_X）  
≡ Φ                 （４１）
OutputY = −CA×Secret_In_Y+Secret_Out_Y
（=−(X+Secret_In_X)×Secret_In_Y+Secret_Out_Y）
（=−X・Secret_In_Y−Secret_In_X・Secret_In_Y+Secret_Out_Y）
≡  Ψ                 （４２）
（式３９）、（式４０）、（式４１）、（式４２）において、Secret_In_X、Secret_Out_Xは機関P1の秘密情報、Secret_In_Y、Secret_Out_Yは機関P2の秘密情報であり、これらには、例えば（式２６）から判るように、（式４３）の関係が成立している。
Secret_In_X・Secret_In_Y=Secret_Out_X+Secret_Out_Y          （４３）
（式４１）、（式４２）、（式４３）から判るように、秘密出力OutputX、秘密出力OutputY、秘密データX、秘密データYには（式４４）に示される関係が成立しており、乗算から加算への変換が、交渉秘密情報を用いて簡便に実行されていることが判る。
X×Y ＝ OutputX＋OutputY                （４４）
【００７５】
図１５は、一例として、演算Aが（X×Y）、演算Bが（OutputX＋OutputY）である場合に取得した交渉秘密情報を用いて、それと同じ演算変換方式である演算Aが（X×Y）、演算Bが（OutputX＋OutputY）である交渉秘密情報有乗算加算変換処理を行う場合について説明したが、Typeの値が≠１である、演算Aが（X＋Y）、演算Bが（OutputX×OutputY）である場合に取得した交渉秘密情報を用いて、それとは演算変換方式が異なる演算Aが（X×Y）、演算Bが（OutputX＋OutputY）である交渉秘密情報有乗算加算変換処理を行うことも可能である。
この場合は、前述したようにSecret_In_X=OutputX、Secret_Out_X=X、Secret_In_Y=OutputY、Secret_Out_Y=Y、として（式３９）から（式４２）に相当する演算を行うことで、演算Aが（X＋Y）、演算Bが（OutputX×OutputY）である場合にはSecret_In_X＋Secret_In_Y=Secret_Out_X×Secret_Out_Y  という関係が成り立っていることから、同様に（式４４）が得られる。
【００７６】
図１６を用いて、一例として、Type値が≠１である、演算Aが（X＋Y）、演算Bが（OutputX×OutputY）である場合に取得した交渉秘密情報を用いて、それと同じ演算変換方式である演算Aが（X＋Y）、演算Bが（OutputX×OutputY）である交渉秘密情報有加算乗算変換処理を行うS1330での演算処理の手順を示す。
機関P1の秘匿演算変換部１６１は、自身の秘密データXと記憶部１３０に格納されている第１交渉秘密情報Secret_In_XとSecret_Out_Xを用いて、（式４５）で示されるCAを作成し、機関P2に送る。
CA =（X−Secret_In_X ）／（Secrt_Out_X）         （４５）
同様に、機関P2の秘匿演算変換部１６１は、自身の秘密データYと記憶部１３０に格納されている第１交渉秘密情報Secret_In_YとSecret_Out_Yを用いて、（式４６）で示されるCBを作成し、機関P1に送る。
CB =（Y−Secret_In_Y）／（CA+Secret_Out_Y）     （４６）
その後、機関P1、機関P2はそれぞれ、（式４７）、（式４８）で示される秘密出力OutputX、秘密出力OutputYを計算する。
OutputX = CB+Secret_Out_X
（= (Y−Secret_In_Y)／Ψ+Secret_Out_X）
≡ Φ                                      （４７）
OutputY = CA+Secret_Out_Y
（ =−(X+Secret_In_X)×Secret_In_Y+Secret_Out_Y）
（ =（X−Secret_In_X）／Secret_Out_X+Secret_Out_Y）
≡ Ψ                                      （４８）
（式４５）、（式４６）、（式４７）、（式４８）において、Secret_In_X、Secret_Out_Xは機関P1の秘密情報、Secret_In_Y、Secret_Out_Yは機関P2の秘密情報であり、これらには、例えば（式７）から判るように、（式４９）の関係が成立している。
Secret_In_X+Secret_In_Y = Scret_Out_X・Secret_Out_Y      （４９）
（式４７）、（式４８）、（式４９）から判るように、秘密出力OutputX、OutputY、秘密データX、秘密データYには（式５０）に示される関係が成立しており、加算から乗算への変換が、交渉秘密情報を用いて簡便に実行されていることが判る。
X＋Y＝OutputX×OtputY                （５０）
【００７７】
図１６は、一例として、演算Aが（X＋Y）、演算Bが（OutputX×OutputY）である場合に取得した交渉秘密情報を用いて、それと同じ演算変換方式である演算Aが（X＋Y）、演算Bが（OutputX×OutputY）である演算変換を行う場合について説明したが、Typeの値が１である、演算Aが（X×Y）、演算Bが（OutputX＋OutputY）である場合に取得した交渉秘密情報を用いて、それとは演算変換方式が異なる演算Aが（X＋Y）、演算Bが（OutputX×OutputY）である交渉秘密情報有加算乗算変換処理を行うことも可能である。
この場合は、前述したようにSecret_In_X=OutputX、Secret_Out_X=X、Secret_In_Y=OutputY、Secret_Out_Y=Y、として（式４５）から（式４８）に相当する演算を行うことで、演算Aが（X×Y）、演算Bが（OutputX＋OutputY）である場合にはSecret_In_X×Secret_In_Y=Secret_Out_X＋Secret_Out_Y  という関係が成り立っていることから、同様に（式５０）が得られる。
【００７８】
S1340で、機関P1の秘匿演算変換部１６１、機関P2の秘匿演算変換部１６１は、それぞれ、当該演算に使用した秘密データX、秘密データY、S1320あるいはS1330で計算した秘密出力OutputX、秘密出力OutpuYを、それぞれ、演算変換入力InputX、演算変換入力InputY、演算変換出力OutputX、演算変換出力OutputYとして自身の記憶部１３０に格納して、交渉秘密情報有演算変換処理を完了する。
【００７９】
以上の説明から判るように、交渉秘密情報有演算変換処理では、記憶部１３０に蓄えられている交渉秘密情報を用いることで、べき乗の演算を必要とする計算負荷の大きい分割加算乗算演算変換法、ElGamal加算乗算演算変換法、Paillier加算乗算演算変換法、分割乗算加算演算変換法、ElGamal乗算加算演算変換法、Paillier乗算加算演算変換法に比べて、計算負荷の小さい簡単な加減乗除演算によって、秘密データX、秘密データYに関する演算A（X×Y、X＋Y）の結果が得られる。
【００８０】
上記の説明より、交渉秘密情報有乗算加算変換処理あるいは交渉秘密情報有加算乗算変換処理に用いられる交渉秘密情報である第１交渉秘密情報Secret_In_X、第１交渉秘密情報 Secret_In_Y、第２交渉秘密情報Secret_Out_X、第２交渉秘密情報 Secret_Out_Yは演算の秘匿性を保つためのダミーデータとも言えるものであり、実際の演算結果には影響を及ぼさない。
したがって、交渉秘密情報有乗算加算変換処理あるいは交渉秘密情報有加算乗算変換処理で用いる交渉秘密情報である第１交渉秘密情報Secret_In_X、第１交渉秘密情報 Secret_In_Y、第２交渉秘密情報Secret_Out_X、第２交渉秘密情報 Secret_Out_Yの取得は、機関P1、機関P2が保有する実際の秘密データX、秘密データYを用いて実施される必要はなく、Secret_Out_X＋Secret_Out_Y＝Secret_In_X×Secret_In_Y、あるいはSecret_Out_X×Secret_Out_Y＝Secret_In_X＋Secret_In_Yを満たすように、分割加算乗算演算変換法、ElGamal加算乗算演算変換法、Paillier加算乗算演算変換法、分割乗算加算演算変換法、ElGamal乗算加算演算変換法、Paillier乗算加算演算変換法等によって、実際の演算に先だってダミーデータを用いて取得しておくことも可能である。
【００８１】
図１７はS1200で変数Negotiationが１でなかった場合の、S1400での交渉秘密情報無演算変換処理の詳細を示したものである。
機関P1、機関P2の秘匿演算変換部１６１は、それぞれの記憶部１３０に格納された演算変換型変数Typeの値が１であるなら、S1420に進み交渉秘密情報無乗算加算変換処理を相手機関と協力し実行する。Typeの値が１でなければ、双方の秘匿演算変換部１６１はS1430に進み交渉秘密情報無加算乗算変換処理に進む。
S1420あるいはS1430での演算処理の後、S1440に進む。
【００８２】
図１８はS1420での処理手順の概要を示したものであり、交渉秘密情報無乗算加算変換処理を実施する際にどのPTypeを用いるかを決定する手順を示したものである。S1421でPTypeの値を判定し、PType=1であれば分割乗算加算演算変換法を、PType=2であればElGamal乗算加算演算変換法を、、PType=3であればPaillier乗算加算演算変換法を用いる。
機関P1、機関P2は連携して、指定された演算変換法によって、（式５１）を満たす秘密出力OutputX、OutputYを求める。
OuputX＋OutputY＝X×Y              （５１）
【００８３】
図１９はS1430での処理手順の概要を示したものであり、交渉秘密情報無加算乗算変換処理を実施する際にどのPTypeを用いるかを決定する手順を示したものである。S1421でPTypeの値を判定し、PType=1であれば分割加算乗算演算変換法を、PType=2であればElGamal加算乗算演算変換法を、PType=3であればPaillier加算乗算演算変換法を用いる。
機関P1、機関P2は連携して、指定された演算変換法によって、（式５２）を満たす秘密出力OutputX、OutputYを求める。
OutputX×OutputY＝X＋Y              （５２）
【００８４】
S1440で、機関P1の秘匿演算変換部１６１、機関P2の秘匿演算変換部１６１は、S1420あるいはS1430での演算に用いた秘密データX、秘密データY、S1420あるいはS1430で計算したOutputX、OutoutYを、それぞれ、演算変換入力InputX、演算変換入力InputY、演算変換出力OutputX、演算変換出力OutputYとして自身の記憶部１３０に格納して、Negotiation値が≠１である、交渉秘密情報無演算変換処理を完了する。
【００８５】
ここで、交渉秘密情報有演算変換処理と交渉秘密情報無演算変換処理の２つの種類の処理を用意する理由を述べる。図１５、図１６に示す交渉秘密情報有演算変換プロトコルでは秘匿演算変換処理が加算、乗算、除算の計算コストの小さい演算のみを適用することで秘密出力OupyX、OutputYを計算することができている。交渉秘密情報有演算変換プロトコルの計算の機密性は交渉秘密情報の機密性に依存し、機密性の高い交渉秘密情報を用いることができれば、計算の機密性を保証することができる。
図６、図７、図９、図１０に示したElGamal加算乗算演算変換法、Paillier加算乗算演算変換法、ElGamal乗算加算演算変換法、Paillier乗算加算演算変換法等の交渉秘密情報無演算変換プロトコルでは秘匿演算変換処理を公開鍵により行い、かつ、秘密入力を用いたべき乗計算を必要としており、計算コストは大きいが、気密性の高い交渉秘密情報を取得することができる。
したがって、２つの種類の処理を組み合せることにより、すなわち、交渉秘密情報無演算変換により高い機密性をもつ交渉秘密情報を作成し、その情報を利用して交渉秘密情報有演算変換を行うことで、秘密入力を用いた演算変換を高速に、かつ、高機密に行うことが可能となる。
【００８６】
次に、図２０によって、交渉秘密情報取得部１６２での交渉秘密情報の取得と更新の手順であるS2000について詳細に説明する。
秘匿演算変換部１６１でのS1000の処理が完了すると、交渉秘密情報取得部１６２はS2000の交渉秘密情報取得処理を開始する。
S2100で、相手機関のデータ処理装置１００と連携し、S1000で作成した秘密出力の組（演算変換入力InputX、演算変換出力OutputX、Type）を後に索引により選別し秘密情報として利用するため、共通変数Idに索引を設定する。また、新しい交渉秘密情報を古い交渉秘密情報と組み合わせるか否かを決定し、変数Combineに設定する。
ここで、作成された秘密情報を他の交渉秘密情報と組み合わせる場合にはCombine=1、そうでない場合には、Combine=0とする。
【００８７】
次に、S2200で、S1000での秘匿演算変換処理の入力である演算変換入力InputX、出力である演算変換出力OutputX、演算変換の型Typeからなる情報を共通索引Idとして持つ交渉秘密情報SecretX[Id]を記憶部１３０に格納する。同様に機関P2では秘匿演算変換処理の入力である演算変換入力InputY、出力である演算変換出力OutputY、演算変換の型Typeからなる情報を共通索引Idとして持つ交渉秘密情報SecretY[Id]を記憶部１３０に格納する。
【００８８】
次に、S2300で、変数Combineが0か否かを判定し、0であれば交渉秘密情報取得処理を終了し、Combineが１であれば、S2400に進む。
【００８９】
次に、S2400で、機関P2と通信することで、他の情報と組み合わせる索引Id_Oldを決定する。
さらに、S2500で、機関P1の交渉秘密取得部１６２は索引Id_Oldをもつ古い交渉秘密情報SecretX[Id_Old]を記憶部１３０より読み出し、機関P2の交渉秘密取得部１６２は古い交渉秘密情報SecretY[Id_Old]を記憶部１３０より読み出す。
【００９０】
次に、S2600で、SecretX[Id]とSecretX[Id_Old]を入力として新しい交渉秘密情報を作成する。交渉秘密情報更新処理を実行し出力としてInputX、OutputX、Typeを受け取り、S2100へ戻る。
【００９１】
図２１はS2600の交渉秘密情報交換処理の詳細を示したものである。
S2600では、最初にS2610で秘密情報のTypeが乗算から加算への変換を示す１かどうか判定し、Typeが１であれば、S2620で、機関P1では、InputX、OutputXに、それぞれ、SecretX[Id].InputX、SecretX[Id].OutputXを設定する。そうでなければ、S2630で、InputX、OutputXに、それぞれ、SecretX「Id」.Output、SecretX[Id].InputXを設定する。機関P2の場合も同様にInputY、OutputYを設定する。
【００９２】
S2640、S2650、S2660では、S2610、S2620、S2630と同様に、既に存在する交渉秘密情報SecretX[Id_Old]、SecretY[Id_Old]から値を読み出し、O_InputX、O_OutputX、O_InputY、O_OutputYに値を設定する。
機関P2も同様に、O_InputX、O_OutputX、O_InputY、O_OutputYに値を設定する。
【００９３】
次に、機関P1の交渉秘密情報取得部１６２は、S2670で、InputXとO_InputXが等しいかを判定し、等しければCombineXに１を設定し、そうでなければ0を設定する。同様に、機関P2の交渉秘密情報取得部１６２はInputYとO_InputYが等しいかを判定し、等しければCombineに1を設定し、そうでなければ0を設定する。
【００９４】
二つの交渉秘密情報の乗算変換の入力InputXとO_InputXが等しい場合、InputX×InputY＝OutputX+OutputY、O_InputX×O_InputY＝O_OutputX＋O_OutputYの２つ条件が成り立つことより、（式５３）が成り立つ。
InputX×（InputY＋O_IputY）＝OutputX＋OutputY＋O_OutputX＋O_OutputY（５３）よって、機関P1ではInputX、OutputX＋O_OutputX、Type=1を新しい秘密情報として、機関P2ではInputY＋O_InpuY、OutputY＋O_OutputY、Type=1を新しい秘密情報として利用することができる。
【００９５】
上記のような新しい秘密情報の作成を、S2690のCombineXとCombineYの組合せにより場合分けした上でS2691かS2692のどちらかにより行う。上記の作成例はS2691に対応する。
【００９６】
交渉秘密情報更新処理を終えた、交渉秘密情報取得部１６２は新しい秘密情報を格納するため、交渉秘密情報取得処理のS2100に戻り、秘密情報の交渉秘密情報としての格納、および、さらなる更新処理を実行する。
【００９７】
本実施の形態によれば、２種類の演算変換処理を組み合せることにより、対象とする秘密データX、秘密データYについて、四則演算などの安価なコストの演算を適用することで、機密性の高い演算変換を行うことが可能になり、公平に意味のある秘密情報を作成することが可能となる。
【００９８】
さらに、乗算から加算、加算から乗算という基本的な演算の変換を行うことにより、得られた秘密情報を加算により組み合せることで、秘匿性に優れる新しい秘密情報を作成することが可能となり、秘密情報の機密性を向上させることも可能となる。
【００９９】
このように本実施の形態の方法は、従来の秘匿計算方法とは異なり、双方が合意した意味のある情報を交渉秘密情報として、公平に作成し、かつ、公開鍵暗号方式と同様の機密性を保ちながら、べき乗演算を用いることなく作成する効率的な方法となっている。
【０１００】
（本発明の実施形態３）
実施形態１での演算変換法では機関P1、P2での秘匿演算変換部１６１での演算処理において、演算負荷の大きな「べき乗計算」を行っていた。また、それらのべき乗計算は秘密データX，Yが決定しなければ、実行できないという問題があった。本発明の実施形態３では図５、図８の分割加算乗算演算変換法、分割乗算加算演算変換法において、秘密データX、Yが決定されてから実行する全ての演算を、計算負荷の小さい「加減乗除算」とする二段階交渉秘密情報無演算変換処理を実行する。
【０１０１】
分割加算乗算変換法における二段階交渉秘密情報無演算変換処理の概要を図２２に示す。二段階交渉秘密情報無演算変換処理では、各機関は秘密データX, Yが決定する前に交換できる情報を入力決定前処理として計算、交換し、秘密データX,Yに依存した計算、情報の交換は秘密データX、Y決定後に実施する。上記の二段階の方式を採用することにより、図５で説明した分割加算乗算演算変換法でのべき乗演算は全て入力前計算として実施でき、入力後計算は加減乗除算の演算のみとなる。入力前計算をオフライン処理とすることで、入力決定後に行うオンライン処理時間を大幅に削減することができる。
【０１０２】
二段階交渉秘密情報無加算乗算演算変換処理では入力前計算と入力後計算の二段階に分けて演算変換処理を行う。図２２において、機関P1は、秘密データXが決定する以前の前処理として、（式５３）、（式５４）で示されるCA1,CA2,CA3,DA3を計算し、機関P2へ送信する。ここで、図５で説明した分割加算乗算演算変換法とは異なり、この段階ではDA1,DA2の送信は行わない。
（CA1、CA2、CA3）＝（α1KA1、α3KA1、gγ1）          （５３）
DA3 ＝ gγ２                                          （５４）
ここに、α1、α3、γ1、γ2は機関P1のみが知る乱数、gは機関P1及び機関P2が知る原始元、xは機関P1のみが知る秘密鍵であり、KA1,KA2は公開鍵Z（＝gx）と乱数γ1、γ2とを用いて、KA1=Zγ1、KA2=Zγ2と表せる値であり、予め機関P1の記憶部１３０に格納されている。
CA1,CA2,CA3,DA3を受信した機関P2はCA3,DA3と自身が決定したランダムな2分割(N1,N2), 乱数パラメータβ1,・・・β(｜N1｜-1), θ1,・・・,θ(｜N2｜-1),λ1, ・・・,λnを用いて、（式５５）、（式５６）で示されるCB1,…,CB(n-2)とDB1,…,DBnを計算し、機関P1へ送信する。ここで、図５で説明した分割加算乗算演算変換法とは異なり、この段階ではCB(n-1), CBnの送信は行わない。
CBi = β＃１(i) Zλi （if  i∈N1-{n-1,n}）、  θ＃２(i) Zλi   （if  i∈N2） （５５）
DBi = ZλiCA3 （if  i∈N1）、  ZλiDA3 （if  i∈N2）                （５６）
ここで、＃１( i )は番号iが集合N1の要素を増加順に列挙したときに出現する順番を示し、＃２( i )についても集合N2に関して同様の定義を持つ順番とする。また、パラメータβ1,・・・β(｜N1｜-1), θ1,・・・,θ(｜N2｜-1)は完全に機関P2が独自に選択した乱数で良い。
機関P2より暗号文の列(CB1,…,CB(n-2))と(DB1,…,DBn)を受信した機関P1は、（式５７）、（式５８）、（式５９）で示される3つのパラメータEA1,FA1,FA2を計算する。
EA1=Σ1≦i≦n-2 CBi DBi-x              （５７）
FA1=DB(n-1)-x                        （５８）
FA2=DBn-x                          （５９）
上記の機関P1,P2で行われる計算、および、情報交換を入力前計算とする。
【０１０３】
秘密入力データXが機関P1において決定したら、機関P1はその秘密入力データより決定した乱数X1,X2（ここで、X1／X2＝X）、先の入力前計算で利用した乱数パラメータα1, α3を用いて、α2＝X1−α1、α4＝X2−α2として計算し、DA1＝α2KA2, DA2＝α4KA2として、暗号文DA1,DA2を計算し、DA1,DA2を機関P2へ送信する。
機関P1より暗号文DA1,DA2を受信し、自身の秘密入力データYが決定した機関P2はYより選択した乱数Y1,Y2（ここで、Y2／Y1＝Y）より、ΓB1＝CA1Y1+CA2Y2、ΓB2＝  DA1Y1+DA2Y2という内部計算を行い、パラメータΓB1, ΓB2の値を求める。さらに、ΓB1, ΓB2の値を用いて、β｜Ｎ１｜＝ΓB1−Σ1≦i≦|N1|-1βiによりパラメータβ｜Ｎ１｜の値を、θ｜Ｎ２｜＝ΓB2−Σ1≦i≦|N2|-1θiによりパラメータθ｜Ｎ２｜の値を計算する。パラメータβ|N1|、θ|N2|より暗号文CBn-1 をCBn-1＝β|N1|CB(n-1)’により、暗号文CBnをCBn＝θ|N2|CBn’として計算し、（CBn-1,CBn）を機関P2に送信する。
機関P2より（CBn-1,CBn）を受信した機関P1は入力前計算にて得ていた値EA1,FA1,FA2を用いて、秘密出力Φを（式６０）によって計算する。
Φ＝(EA1+CB(n-1)FA1+CB2FA2)／X2                              （６０）
機関P2では（式６１）で示される秘密出力Ψを計算しており、機関P1、P2が秘密出力Φと秘密出力Ψを交換することで、（式６２）から判るように、双方が演算結果（X+Y）を得ることができる。
Ψ＝１／Y1                                        （６１）
Φ×Ψ＝（X1Y1+X2Y2）／（X2Y1）
＝ X1/X2 + Y2/Y1
＝ X + Y                                    （６２）
【０１０４】
分割乗算加算変換法における二段階交渉秘密情報無演算変換処理の概要を図２３に示す。入力前計算は図２２の二段階交渉秘密情報無加算乗算変換処理と同じである。
以下では秘密入力データ決定後の処理について説明する。
【０１０５】
秘密入力データXが機関P1において決定したら、機関P1はその秘密入力データと先の入力前計算で利用した乱数パラメータα1, α3を用いて、α2＝X−α1、α4＝&#8722;１−α2として計算し、DA1＝α2KA2, DA2＝α4KA2として、暗号文DA1,DA2を計算し、DA1,DA2を機関P2へ送信する。
機関P1より暗号文DA1,DA2を受信し、自身の秘密入力データYが決定した機関P2は選択した乱数Ψより、ΓB1＝CA1Y+CA2Ψ、ΓB2＝  DA1Y+DA2Ψという内部計算を行い、パラメータΓB1, ΓB2の値を求める。さらに、ΓB1, ΓB2の値を用いて、β｜Ｎ１｜＝ΓB1−Σ1≦i≦|N1|-1βiによりパラメータβ｜Ｎ１｜の値を、θ｜Ｎ２｜＝ΓB2−Σ1≦i≦|N2|-1θiによりパラメータθ｜Ｎ２｜の値を計算する。パラメータβ|N1|、θ|N2|より暗号文CBn-1 をCBn-1＝β|N1|CB(n-1)’により、暗号文CBnをCBn＝θ|N2|CBn’として計算し、（CBn-1,CBn）を機関P2に送信する。
機関P2より（CBn-1,CBn）を受信した機関P1は入力前計算にて得ていた値EA1,FA1,FA2を用いて、秘密出力Φを（式６３）によって計算する。
Φ＝(EA1+CB(n-1)FA1+CB2FA2) （６３）
機関P2では秘密出力Ψを乱数として選択しており、機関P1、P2が秘密出力Φと秘密出力Ψを交換することで、（式６４）から判るように、双方が演算結果（X×Y）を得ることができる。
Φ＋Ψ＝（X×Y &#8212; 1×Ψ）＋ Ψ
＝ X×Y                               （６４）
【０１０６】
上記の、機関P1, P2によって秘密入力データX,Yが決定したのちに行う入力後計算は加減乗除算のみであり、べき乗計算を必要としないため、オンラインでの計算を高速に実行することができる。上記の二段階交渉秘密情報無演算変換処理により、べき乗計算を入力決定前に全て終えるという特徴は実施形態１での分割加算乗算演算変換法、分割乗算加算演算変換法以外のElGamal加算乗算演算変換法、Paillier加算乗算演算変換法、ElGamal乗算加算演算変換法、Paillier乗算加算演算変換法では活かすことができない。なぜなら、ElGamal暗号方式、Paillier暗号方式とも秘密入力X,Yを指数とするべき乗計算を必要とするからである。一方、分割による演算変換方法ではべき乗計算の指数部は乱数や秘密鍵など秘密入力に依存しない値であり、このような入力決定前の計算処理が可能となる。
【０１０７】
ここで、二段階交渉秘密情報無演算変換法の機密性について考える。機関P1の機密性は公開鍵暗号方式でCA3,DA3を公開していない場合、与えられたCA1,CA2,DA1,DA2の暗号文を得ることができるように、任意の秘密入力Xの値に対してKA1,KA2を選択することが可能である。よって、CA1,CA2,DA1,DA2だけであれば、機関P1の秘密入力Xの情報は何も洩れていないので、CA3,DA3によるKA1,KA2に関する情報が機関P2に明かされた機関P1の情報となる。CA3,DA3からKA1,KA2を推測する問題は、離散対数問題よりも簡単と推測されているDiffie-Hellman計算問題が解けないと仮定したときに、解けない。上記の仮定が成り立つなら、X1とX2の比である秘密入力データXの情報の機密性は守られる。
【０１０８】
一方、機関P2に関してはΓB1,ΓB2が判明すれば連立方程式の解を得ることで機関P1にY1,Y2の値を導出でき、Yも明らかとなってしまう。しかし、分割による方法ではΓB1、ΓB2は|N1|+|N2|個に分割され、かつ、乱数λiによって曖昧化されているので、それぞれの値を正確に推測するには各DBi（1≦i≦n）がCA3,DA3のどちらを用いて作成されたかという2n-1通りの異なる組合せの中から本物の組合せを選ばなければならない。よって、機関P1に機関P2のYの情報を正確に推測できる確率は2-(n+1)か剰余演算に利用している素数pの逆数p-1のどちらか大きな方の値となる。
【０１０９】
（本発明の実施形態４）
実施形態１，２，３では乗算から加算、加算から乗算に変化させる演算変換について説明した。実施形態４では、乗算から加算、加算から乗算に変化させる演算変換を組み合わせることで、底とべき指数の両方を機関P1,P2双方で変化させる秘密べき乗算演算変換法を実現する。本実施の形態では、機関P1の秘密入力は底に関する秘密入力Xとべき指数に関する秘密入力A、機関P2の秘密入力は底に関する秘密入力Yとべき指数に関する秘密入力Bとするとき、(X+Y)AB、（X+Y）（A＋B）、（X×Y）AB、（X×Y）（A+B）の形で表せるべき乗計算と等しい値を求めることができる秘密出力OutputX, OutputYをそれぞれの機関P1,P2の出力として交換することで、秘密べき乗演算変換を実現する。
【０１１０】
はじめに、（X+Y）ABの形で表せるべき乗演算を例に、秘密べき乗演算変換法の概要を図２３を用いて説明する。
まず、底を秘匿しながら計算するため、機関P1とP2が協力し、図５を用いて説明した交渉秘密情報無加算乗算演算変換法、あるいは図１６で説明した交渉秘密情報有加算乗算演算変換法によって加算乗算変換を行い、X+Y＝Φ×Ψとなるような中間の秘密出力Φ、Ψを機関P1,P2双方で得る。その後、機関P1、機関P2それぞれで、中間秘密出力Φ、Ψにそれぞれの秘密べき指数A, Bをべき乗し、FA=ΦA, FB=ΨBなる暗号文FA, FBをそれぞれ得る。次に、機関P1, P2は暗号文FA,FBを交換し、機関P1はFBに秘密べき指数Aを、機関P2はFAに秘密べき指数Bをべき乗して得られた値をそれぞれの秘密入力として、図８を用いて説明した交渉秘密情報無乗算加算演算変換法、あるいは図１６を用いて説明した交渉秘密情報有乗算加算変換法によって乗算加算変換を行うことで、秘密出力OutputX, OutputYをそれぞれ得る。
機関P1,P2が秘密出OutputX、OutputYを交換することで、（式６３）から、(X+Y)ABを求めることができる。
OutputX+OutputY=FBA×FAB=ΨBA×ΦAB＝(Ψ×Φ)AB=(X+Y)AB          （６３）
なお、図２３は交渉秘密情報有の場合の（即ち、交渉秘密情報を利用する場合の）プロトコルの概要を示したものである。
【０１１１】
ElGamal公開鍵暗号方式やPaillier公開鍵暗号方式を用いて秘匿計算を行う場合、平文への加減算は暗号文に関する乗算に、平文への乗算は暗号文に関するべき乗算に対応している。よって、平文のべき乗算は底を秘匿にしたままではべき乗算に変換できないため、暗号文に対する演算では実現できない。よって、秘匿演算中の底を一旦復号する必要がある。このとき、底の(X+Y)をどちらか一方の機関、例えば、公開鍵を提供している機関P1が知ることになれば、機関P1のみが機関P2の底に関する秘密入力データYの値を知ることとなり、機関P1とP2間の機密性を公平に保つことができない。
【０１１２】
図２３に示した例では上記の問題を解決するため、まず、機関P1,P2の秘密の底X、Yについて、分割加算乗算変換を行うことにより、公平な秘密情報Φ、Ψを得、ついで、秘密情報Φ、Ψを機関P1、P2の秘密べき指数A、Bでべき乗した値ΦA、ΨBを機関P1、P2で交換し、最後に、値ΦA、ΨBを機関P1,P2でB乗あるいはA乗した値ΦAB、ΨBAについて分割乗算加算変換を行っており、底とべき指数ともに秘匿したまま、機密性の高い秘密べき乗演算が可能となる。
【０１１３】
（X+Y）（A＋B）の形で表されるべき乗演算については、図２５に示すように第一段階で、（X+Y）について加算乗算演算変換によってΦ×Ψ＝X+Yの関係を満たす第一の中間出力Φ、Ψを得、第二段階で（A+B）についての加算乗算演算変換によってφ×ψ＝A+Bを満たす第二の中間中間出力φ、ψを得、機関P1,P2で第一および第二の中間出力からΦφ、Ψψを作成して交換し、交換したΦφ、Ψψを基に機関P1,P2で作成したΨψφ、ΦφΨから、乗算加算演算変換によって（式６４）の関係を満たすOutputX、OutputYを求めることで、（式６５）から（X+Y）（A＋B）を求めることができる。
OutputX＋OutputY ＝ Ψψφ×ΦφΨ                                                        （６４）
OutputX＋OutputY ＝ Ψψφ×ΦφΨ＝（Ψ×Φ）φψ＝（X+Y）（A+B）      （６５）
ただし、素数pを法とする剰余環上で演算を行う場合、第二段階で行う指数部の秘密入力の交渉情報有加算乗算変換ではp&#8722;１を法とする剰余環上で計算しなければならない（フェルマーの小定理よりap-1≡１(mod p)のため, ここでaはpの倍数でない整数）。よって、第二段階で用いる交渉秘密情報SecretX[ID2], SecretY[ID2]もp-1を法とする剰余環上で計算された情報でなければならない。このとき、p-1が素数でないため、除算を正確に計算できない場合が存在することに注意する必要がある。
【０１１４】
（X×Y）ABの形で表されるべき乗演算については、機関P1,P2でXA、YBを作成して交換し、交換したXA、YBを基に機関P1,P2でYBA、XABを作成し、YBA、XABから乗算加算演算変換によって（式６６）の関係を満たすOutputX、OutputYを求めることで、（式６７）から（X×Y）ABを求めることができる。
OutputX＋OutputY = YBA×XAB                                  （６６）
OutputX＋OutputY = YBA×XAB＝（X×Y）AB                     （６７）
【０１１５】
（X×Y）（A+B）の形で表されるべき乗演算については、第一段階で（A+B）についての加算乗算演算変換によってφ×ψ＝A+Bを満たす第二の中間中間出力φ、ψを得、機関P1,P2で自身の秘密入力と第一の中間出力からXφ、Yψを作成して交換し、交換したXφ、Yψを基に機関P1,P2で作成したYψφ、XφΨから乗算加算演算変換によって（式６８）の関係を満たすOutputX、OutputYを求めることで、（式６９）から（X×Y）（A+B）を求めることができる。
OutputX+OutputY = Xψφ×Yφψ                                                     （６８）
OutputX+OutputY = Yψφ×Xφψ＝（X×Y）ψφ＝（X×Y）（A+B）       （６９）
【０１１６】
上記ではべき乗算を加算に変換する処理について説明したが、OutputX, OutputYを得るための乗算加算変換処理の入力をそのままOutputX, OutputYとすることでべき乗算を乗算に変換できる。
【０１１７】
また、ここでは交渉秘密情報を用いる演算変換方法（すなわち、交渉秘密情報有の演算変換方式）について説明したが、図５から図１０で説明した、べき乗計算を用いて入力情報を秘匿しながら所望の値を得る方式である交渉秘密情報無の演算変換方式が適用可能であることは勿論である。
【産業上の利用可能性】
【０１１８】
本発明によれば、複数の機関がそれぞれ保持している秘密データを入力として演算Aを行ったときの結果と同じ結果を得ることができる別の演算Bに対する複数の入力を安価な計算コストで秘匿に計算し、各々の機関に秘密出力として返すことで、各々の機関の秘密データを秘匿した状態で、各々の機関が希望する演算結果を得ることができる。
【符号の説明】
【０１１９】
１  秘匿演算変換システム、１００  データ処理装置、１１０  制御部、１２０  通信部、
１３０  記憶部、１４０  操作部、１５０  インタフェース部、１６０  演算処理部、
１６１  秘匿演算変換処理部、１６２  交渉秘密情報取得処理部、２００  通信線
【図１】
2020016739.tif 000003
【図２】
2020016739.tif 000004
【図３】
2020016739.tif 000005
【図４】
2020016739.tif 000006
【図５】
2020016739.tif 000007
【図６】
2020016739.tif 000008
【図７】
2020016739.tif 000009
【図８】
2020016739.tif 000010
【図９】
2020016739.tif 000011
【図１０】
2020016739.tif 000012
【図１１】
2020016739.tif 000013
【図１２】
2020016739.tif 000014
【図１３】
2020016739.tif 000015
【図１４】
2020016739.tif 000016
【図１５】
2020016739.tif 000017
【図１６】
2020016739.tif 000018
【図１７】
2020016739.tif 000019
【図１８】
2020016739.tif 000020
【図１９】
2020016739.tif 000021
【図２０】
2020016739.tif 000022
【図２１】
2020016739.tif 000023
【図２２】
2020016739.tif 000024
【図２３】
2020016739.tif 000025
【図２４】
2020016739.tif 000026
【図２５】
2020016739.tif 000027
【図２６】
2020016739.tif 000028