(57)【要約】  本発明は、MPCプロトコルに関して効率的な検索を実現するシステム、装置を提供する。登録装置は、文字列を複数の法のもと秘密分散したシェアを生成し複数のサーバ装置に送信して保管し、検索装置は、検索文字列を前記複数の法のもと秘密分散したシェアを前記複数のサーバ装置に送信し、複数のサーバ装置では、前記記憶部に保管されている各登録文字列のシェア及び前記複数の法毎にサブルーチンを実行し実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定し、検索装置は、前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から中国人剰余定理により、前記検索文字列がヒットした検索結果を得る。
2016148281.tif 000002
【特許請求の範囲】
【請求項１】
登録装置と、
検索装置と、
複数のサーバ装置と、
を備え、
前記登録装置は、登録文字列を複数の法のもと秘密分散したシェアを生成する登録文字列シェア生成部を備え、
前記登録文字列シェア生成部で生成したシェアを、それぞれ前記複数のサーバ装置に送信し、
前記複数のサーバ装置では、受信したシェアを記憶部に保管し、
前記検索装置は、検索文字列を前記複数の法のもと秘密分散したシェアを生成する検索文字列シェア生成部を備え、
前記検索文字列シェア生成部で生成したシェアを、それぞれ前記複数のサーバ装置に送信し、
前記複数のサーバ装置は、それぞれの前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し、前記演算処理の実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算部を備え、
前記検索装置は、前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から、中国人剰余定理により、検索結果を復元する復元部を備えた、ことを特徴とする秘匿文字列計算システム。
【請求項２】
前記登録文字列をa=a[1]||…||a[n]、前記検索文字列をb=b[1]||…||b[m]とし（ただし、||は連接演算子、mとnは、m＜nの正整数）、
前記サーバ装置の前記検索応答計算部は、前記予め定められた演算処理として、
各j(j=1,…,n-m)および各k(k=1,…,m)に対し、前記登録文字列のj+kワード目のシェアと前記検索文字列のkワード目が一致するか否かによって1又は0になる値のシェアを計算する第一マルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルにより計算されたシェアを前記k毎に、前記法のもと、足し合わせ、
前記足し合わされたシェアが0になるか否かによって、0又は1になる値のシェアを計算する第二マルチパーティ計算プロトコルを実行し、
前記登録文字列のワード数から、前記検索文字列のワード数と、前記第二マルチパーティ計算プロトコルにより計算された前記シェアの総和とを、前記法のもと減算し、
前記減算した値に、乱数生成マルチパーティ計算プロトコルにより得られたシェアを、前記法のもと乗じたものを出力する、ことを特徴とする請求項１記載の秘匿文字列計算システム。
【請求項３】
前記検索応答計算部において、前記第一マルチパーティ計算プロトコルは、前記登録文字列のj+kワード目のシェアから前記検索文字列のkワード目を前記法のもと減じたものを、前記法のカーマイケル関数値で、べき乗剰余するマルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルは、前記足し合わされたシェアを、前記法のカーマイケル関数値でべき乗剰余するマルチパーティ計算プロトコルを実行する、ことを特徴とする請求項２記載の秘匿文字列計算システム。
【請求項４】
コンピュータシステムによる秘匿文字列計算方法であって、
登録文字列を複数の法のもと秘密分散したシェアを生成し、それぞれ複数のサーバ装置に送信して、前記複数のサーバ装置に保管し、
検索文字列を前記複数の法のもと秘密分散したシェアを、前記複数のサーバ装置に送信し、
前記複数のサーバ装置では、前記保管されている各登録文字列のシェア及び前記複数の法毎に、サブルーチンを呼び出して演算処理を実行し、前記演算処理の実行結果を復元して、前記保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定し、
前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から中国人剰余定理により、検索結果を復元する、ことを特徴とする秘匿文字列計算方法。
【請求項５】
前記登録文字列をa=a[1]||…||a[n]、前記検索文字列をb=b[1]||…||b[m]とし（ただし、||は連接演算子、mとnは、m＜nの正整数）、
各j(j=1,…,n-m)および各k(k=1,…,m)に対し、前記サーバ装置で呼び出される前記サブルーチンは、
各jおよび各kに対し、前記登録文字列のj+kワード目のシェアと前記検索文字列のkワード目が一致するか否かによって1又は0になる値のシェアを計算する第一マルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルにより計算されたシェアを前記k毎に、前記法のもと、足し合わせ、
前記足し合わされたシェアが0になるか否かによって、0又は1になる値のシェアを計算する第二マルチパーティ計算プロトコルを実行し、
前記登録文字列のワード数から、前記検索文字列のワード数と、前記第二マルチパーティ計算プロトコルにより計算された前記シェアの総和を、前記法のもと減算し、
前記減算した値に、乱数生成マルチパーティ計算プロトコルにより得られたシェアを前記法のもと乗じたものを出力する、ことを特徴とする請求項４記載の秘匿文字列計算方法。
【請求項６】
前記サブルーチンにおいて、前記第一マルチパーティ計算プロトコルは、前記登録文字列のj+kワード目のシェアから前記検索文字列のkワード目を前記法のもと減じたものを、前記法のカーマイケル関数値で、べき乗剰余するマルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルは、前記足し合わされたシェアを前記法のカーマイケル関数値でべき乗剰余するマルチパーティ計算プロトコルを実行する、ことを特徴とする請求項５記載の秘匿文字列計算方法。
【請求項７】
登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から複数のサーバ装置に送信されるシェアを受信する通信部と、
前記受信した登録文字列のシェアを保管する記憶部と、
検索文字列を前記複数の法のもと秘密分散したシェアを前記複数のサーバ装置に送信する検索装置から送信されたシェアを前記通信部で受信すると、前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算部と、
を備え、
前記検索結果のシェアを前記通信部を介して前記検索装置に送信し、
前記検索装置をして、各サーバ装置から返答されたシェアの復元結果から中国人剰余定理により、検索結果を復元可能としてなる、ことを特徴とするサーバ装置。
【請求項８】
前記登録文字列をa=a[1]||…||a[n]、前記検索文字列をb=b[1]||…||b[m]とし（ただし、||は連接演算子、mとnは、m＜nの正整数）、
前記検索応答計算部は、前記予め定められた演算処理として、
各j(j=1,…,n-m)および各k(k=1,…,m)に対し、前記登録文字列のj+kワード目のシェアと検索文字列のkワード目が一致するか否かによって1又は0になる値のシェアを計算する第一マルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルにより計算されたシェアを前記k毎に、前記法のもと、足し合わせ、
前記足し合わされたシェアが0になるか否かによって、0又は1になる値のシェアを計算する第二マルチパーティ計算プロトコルを実行し、
前記登録文字列のワード数から、前記検索文字列のワード数と前記第二マルチパーティ計算プロトコルにより計算された前記シェアの総和を、前記法のもと減算し、
前記減算した値に、乱数生成マルチパーティ計算プロトコルにより得られたシェアを前記法のもと乗じたものを出力する、ことを特徴とする請求項７記載のサーバ装置。
【請求項９】
前記検索応答計算部において、前記第一マルチパーティ計算プロトコルは、前記登録文字列のj+kワード目のシェアから前記検索文字列のkワード目を前記法のもと減じたものを、前記法のカーマイケル関数値で、べき乗剰余するマルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルは、前記足し合わされたシェアを前記法のカーマイケル関数値でべき乗剰余するマルチパーティ計算プロトコルを実行する、ことを特徴とする請求項８記載のサーバ装置。
【請求項１０】
登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から複数のサーバ装置に送信されるシェアを受信して記憶部に保管する処理と、
検索文字列を前記複数の法のもと秘密分散したシェアを前記複数のサーバ装置に送信する検索装置から送信されたシェアを受信する処理と、
前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算処理と、
前記検索結果のシェアを前記検索装置へ送信する処理、
を前記サーバ装置を構成するコンピュータに実行させるプログラム。
【請求項１１】
登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から前記シェアを受け取り保管する複数のサーバ装置に通信接続する通信部と、
検索文字列を前記複数の法のもと秘密分散したシェアを生成する検索文字列シェア生成部と、
を備え、
前記検索文字列シェア生成部で生成したシェアを、前記通信部を介して、それぞれ前記複数のサーバ装置に送信し、前記複数のサーバ装置では、それぞれの前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し、前記演算処理の実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定し、
前記複数のサーバ装置から返答され前記通信部を介して受信したシェアを復元し、前記復元結果から、中国人剰余定理により、検索結果を復元する復元部を備えた、ことを特徴とする検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１５−０５６３６７号（２０１５年３月１９日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は秘匿文字列計算システム及び方法と装置並びにプログラムに関する。
【背景技術】
【０００２】
秘密分散の代表的な方式として（k,n)しきい値秘密分散法では、秘密情報Sをｎ個の分散情報Ｗiに符号化し、そのうち任意のk個の分散情報を集めれば、元の秘密情報Sを完全に復元できるが、k-1個の分散情報では、秘密情報Sは求められない（非特許文献１参照）。マルチパーティ計算は、各計算主体i(i=1,…,N)がそれぞれ値aiを入力として他の計算主体に値aiを明かすことなく、特定の関数値Fi(a1,…,aN)を得る技術である。【０００３】
＜剰余算＞  
整数a、pに対し、aをpで割った余りを(a mod p)と表記する。さらに整数a、b、pに対し、(a mod p)と(b mod p)が等しいことを、「a=b mod p」と表記する。整数環をZで表し、Z/pZは、{0,…,p-1}でmod pの演算を考えた環を表す。「mod p」での演算を考えるとき，pを「法」もしくは「モジュラス」と呼ぶ。【０００４】
＜中国人剰余定理（Chinese remainder theorem）＞
どの２つも互い素のn個の整数p[1],…,p[n]に対して、任意に与えられた整数a[i]∈Zp［ｉ］{i=1,2,…,n}に対して、
a = (a[1] mod p[1]), 
a = (a[2] mod p[2]),
…, 
a = (a[n] mod p[n])
を満たす整数ａが、p[1]…p[n]を法として（0≦ａ＜p[1]…p[n]）、一意に定まる。【０００５】
中国人剰余定理により、x= (a mod p[1]…p[n])は、a[1],…,a[n]の関数となる。この関数を、
x= ChineseRemainder(a[1],…,a[n])
・・・(1)
と表記する。なお、関数ChineseRemainder(a[1],…,a[n])は効率的に計算可能であることが知られている。【０００６】
＜カーマイケル関数数(Carmichael function)＞
カーマイケル関数は、与えられた整数pに対し、an = 1 mod p が任意のpと互いに素なaについて成立する最小のnを返す関数λである。
aλ（ｐ）=1 mod p
・・・(2)【０００７】
カーマイケル関数λは、以下のように帰納的に定義される。
・ｐがｑｋ（ｑ：奇素数）の場合、
λ(qｋ) = qｋ−１(q - 1)
・ｐが2ｋの場合、kが３以上のとき、λ(2ｋ) = 2ｋ−2
k＝1のとき、λ(2ｋ) =１
k＝2のとき、λ(2ｋ) =2
・・・(3)【０００８】
なお、p=q1k1 q2k2 ・・・qmkm（q1，q2，…，qmが互いに素のとき）、
λ(q1k1 q2k2，…qmkm) = lcm(λ(q1k1), λ(q2k2),…，λ(qmkm))
(lcm:最小公倍数)
・・・(4)【０００９】
＜秘密分散＞
秘密分散方式(Share, Reconst)は、秘密ｓの保有者であるユーザは、ｓからN個のシェア（分散情報）を呼ばれる値s1,…,sNを生成し、s1,…,sNをシェア保有者であるN個のサーバM[1],…,M[N]に秘密裏に渡す。その後、任意のk個のサーバからk個のシェアを集め、所定の演算により、秘密sを復元できる。複数サーバM[1],…,M[N]でシェアして持つ為のプロトコルとして、秘密sからシェアを作るシェア生成関数Shareと、シェアから秘密sを復元する復元関数Reconstの２つがある。なお、非特許文献１の方式をはじめ、シェアはZ/pZの元である事が多い。【００１０】
本明細書でも、シェアはZ/pZの元である状況を考えているので、そのような状況下での秘密分散法式について説明する。ここで、pは何らかの整数である。このような状況下での秘密分散を、「法pにおける秘密分散」といい、「法pにおける秘密分散」で生成されたシェアを「秘密sのmod pのシェア」もしくは「秘密sの法pでのシェア」と呼ぶ。【００１１】
ShareおよびReconstの関数の入出力は以下のとおりである：【００１２】
＜シェア生成関数Share＞
シェア生成関数Shareは、秘密sと、サーバの台数Nと、整数pを入力として受け取り、sのmod pのシェア（分散情報）x[1],…,x[N]を出力する。【００１３】
＜復元関数Reconst＞
復元関数Reconstは、mod pのシェアx[1],…,x[N]の全てもしくは一部と、pとを入力として受け取り、秘密aを出力するか、もしくは「復元失敗」を意味するデータを出力する。【００１４】
秘密分散方式(Share,Reconst)は、以下の手順で用いられる。【００１５】
まず、ユーザUが秘密sをサーバM[1],…,M[N]にシェアさせる場合、Share(s,N,p)を実行し、出力（シェア）x[1],…,x[N]を得る。  【００１６】
そして、ユーザＵは、シェアx[1]をサーバM[1]に送信し、・・・、シェアx[N]をサーバM[N]に送信する。【００１７】
その後、ユーザUにおいて、シェアから秘密を復元する必要が生じたら、{i_1,…,i_t}∈Accessを満たすサーバM[i_1],…,M[i_t]が自身のシェアx[i_1],…,x[i_t]をユーザUに送信する。【００１８】
ユーザUは、Reconst(x[i_1],…,x[i_t])を実行し、秘密sを得る。【００１９】
なお、ここでは、ユーザUがReconst(x[i_1],…,x[i_t])を実行するケースを想定して説明したが、それ以外のユーザ、あるいはサーバがReconst(x[i_1],…,x[i_t])を実行してもよい。【００２０】
＜アクセス構造＞
{1,…,N}の部分集合の集合Accessが以下を満たすとき、集合Accessを{1,…,N}上のアクセス構造という：
S∈Access、かつ、S⊂Tであれば、T∈Access
・・・(5)【００２１】
＜Access-安全＞
{1,…,N}上のアクセス集合Accessに対し、(Share,Reconst)が以下をみたすとき、(Share,Reconst)は、Access-安全であると言う。【００２２】
x[1],…,x[N]をShare(s,N,p)の出力、S={i_1,…,i_t}を{1,…,N}の部分集合とする。【００２３】
このとき、
S∈Accessであれば、Reconst(x[i_1],..,x[i_t], p)はsを出力する。【００２４】
S∈Accessでなければ、シェアx[i_1],..,x[i_t]からsのいかなる部分情報も知る事ができない。【００２５】
＜MPC (Multi Party Computation)プロトコル＞
マルチパーティ計算(MPC)プロトコルは、何らかのアルゴリズムを複数のサーバでセキュアに計算する手法をいう。後述の実施形態では、「乗法剰余MPCプロトコル」、「べき乗剰余MPCプロトコル」、「乱数生成MPCプロトコル」の３種類のMPCプロトコルを用いる。 【００２６】
pを整数とし、x[1],…,x[N]は何らかの整数aのmod pでのシェアとし、y[1],…,y[N]は何らかの整数bのmod pでのシェアとする。【００２７】
＜乗法剰余MPCプロトコル＞
乗法剰余MPCプロトコルは、乗法剰余アルゴリズムをセキュアに実行するMPCである。サーバ装置M[1]が(x[1],y[1],p)，…，サーバ装置M[N]が(x[N],y[N],p)を入力として実行される。サーバ装置M[1]がz[1],…, サーバ装置M[N]がz[n]を出力として受け取る。【００２８】
ここで、
z[1],…,z[N]は、(ab mod p)のmod pにおけるシェアである。【００２９】
＜べき乗剰余MPCプロトコル＞
べき乗剰余MPCプロトコルは、べき乗剰余アルゴリズムをセキュアに実行するMPCである。サーバ装置M[1]が(x[1],n,p)，…，サーバ装置M[N]が(x[N],n,p)を入力として実行され、サーバ装置M[1]がw[1],…, サーバ装置M[N]がw[N]を出力として受け取る。【００３０】
ここで、nは整数であり、
w[1],…,w[N]は、(an mod p)のmod pにおけるシェアである。【００３１】
＜乱数生成MPCプロトコル＞
乱数生成MPCプロトコルは、乱数生成アルゴリズムをセキュアに実行するMPCである。サーバ装置M[1],…M[N]がいずれもpを入力として実行され、サーバ装置M[1]がu[1],…M[N]がu[N]を出力として受け取る。【００３２】
ここで、u[1],…,u[N]は、Z/pZ上の一様乱数のmod pにおけるシェアである。【００３３】
これらのプロトコルの実現方法として様々な手法が知られているが、例えば非特許文献２記載の方法を用いる事ができる。
【先行技術文献】
【非特許文献】
【００３４】
【非特許文献１】Shamir, Adi, "How to share a secret", Communications of the ACM, Volume 22 (11): pages 612-613, 1979
【非特許文献２】O. Goldreich, S. Micali, and A. Wigderson. "How to play ANY mental game", In Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 218-229. ACM Press, 1987.
【発明の概要】
【発明が解決しようとする課題】
【００３５】
以下に関連技術の分析を与える。【００３６】
近時、クラウド技術の普及により、ユーザがクラウド等にあるデータベースにデータを預け、後日、データベースに預けたデータの中からユーザが必要な物を検索して利用するサービスが一般化しつつある。【００３７】
しかし、このようなサービスでは、データベースの管理者は、ユーザが預けたデータを全て閲覧することができる。このため、例えば、ユーザがデータをデータベースに預けると、ユーザのプライバシーがデータベース管理者に筒抜けになる可能性がある。【００３８】
データベースに預けるデータをユーザ側で予め暗号化し、暗号化したデータをデータベースに登録することで、上記可能性を回避できる。しかしながら、データを暗号化してデータベースに登録してしまうと、後日、当該データベースから必要なデータを検索する場合、平文等による検索を行うことができない。【００３９】
このような問題に対して、例えば上記したMPCプロトコルが用いられる。MPCプロトコルは、複数のサーバに、データx[1],…,x[n]をシェア（share）して持った状態からスタートし、シェアされたデータから何らかのアルゴリズムFにしたがって必要な値F(x[1],…,x[n])をセキュアに計算するプロトコルである。「シェア（分散情報）」は秘密分散方式で作られる。【００４０】
検索アルゴリズムを上記Fとし、「検索にヒットするか否か」を上記「必要な値」とし、MPCプロトコルを用いることで、原理的には、セキュアな検索を実現することができる。MPCプロトコルには様々なものが提案されているが、後述するように、いずれも、効率が悪い。【００４１】
したがって、本発明は上記課題に鑑みて創案されたものであって、その目的は、MPCプロトコルに関して効率的な検索を実現する秘匿文字列計算システム及び方法と装置並びにプログラムを提供することにある。
【課題を解決するための手段】
【００４２】
本発明の１つの側面によれば、登録装置と、検索装置と、複数のサーバ装置と、を備え、前記登録装置は、登録文字列を複数の法のもと秘密分散したシェアを生成する登録文字列シェア生成部を備え、
前記登録文字列シェア生成部で生成されたシェアは、それぞれ前記複数のサーバ装置に送信され前記複数のサーバ装置の記憶部に保管され、
前記検索装置は、検索文字列を前記複数の法のもと秘密分散したシェアを前記複数のサーバ装置に送信する検索文字列シェア生成部を備え、
前記複数のサーバ装置では、前記記憶部に保管されている各登録文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算部を備え、
前記検索装置は、前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から、中国人剰余定理により、検索結果を復元する復元部を備えた秘匿文字列計算システムが提供される。【００４３】
本発明の他の側面によれば、登録文字列を複数の法のもと秘密分散したシェアを生成し、それぞれ複数のサーバ装置に送信して保管し、
検索文字列を前記複数の法のもと秘密分散したシェアを、前記複数のサーバ装置に送信し、
前記複数のサーバ装置では、前記記憶部に保管されている各登録文字列のシェア及び前記複数の法毎に、サブルーチンを呼び出して演算処理を実行し、実行結果を復元して、前記登録文字列のシェアを検索結果として返答するか否かを決定し、
前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から中国人剰余定理により、検索結果を復元する、秘匿文字列計算方法が提供される。【００４４】
本発明の他の側面によれば、登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から複数のサーバ装置に送信されるシェアを受信する通信部と、
前記受信した登録文字列のシェアを保管する記憶部と、
検索文字列を前記複数の法のもと秘密分散したシェアを前記複数のサーバ装置に送信する検索装置から送信されたシェアを前記通信部で受信すると、前記記憶部に保管されている各登録文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算部と、
を備え、
前記検索結果のシェアを前記通信部を介して前記検索装置に送信し、前記検索装置をして、各サーバ装置から返答されたシェアの復元結果から中国人剰余定理により、検索結果を復元可能としてなるサーバ装置が提供される。【００４５】
本発明のさらに他の側面によれば、登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から複数のサーバ装置に送信されるシェアを受信して記憶部に保管する処理と、
検索文字列を前記複数の法のもと秘密分散したシェアを前記複数のサーバ装置に送信する検索装置から送信されたシェアを受信する処理と、
前記記憶部に保管されている各登録文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算処理と、
前記検索結果のシェアを前記検索装置へ送信する処理、
を前記サーバ装置を構成するコンピュータに実行させるプログラムが提供される。本発明によれば、上記プログラムを記録したコンピュータ読み出し可能な記録媒体（半導体ストレージあるいは磁気／光記録媒体等）が提供される。【００４６】
本発明のさらに他の側面によれば、検索文字列を前記複数の法のもと秘密分散したシェアを、登録文字列を複数の法のもと秘密分散したシェアを保管する複数のサーバ装置に送信する検索文字列シェア生成部と、
各登録文字列のシェア及び前記複数の法毎に、サブルーチンを呼び出して演算処理を実行し、実行結果を復元して、前記登録文字列のシェアを検索結果として返答するか否かを決定する前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から中国人剰余定理により、検索結果を復元する復元部と、を備えた検索装置が提供される。
【発明の効果】
【００４７】
本発明によれば、MPCプロトコルに関して効率的な検索を実現可能としている。
【図面の簡単な説明】
【００４８】
【図１】本発明の実施形態の構成例を説明する図である。
【図２】本発明の実施形態の動作手順を説明する図である。
【図３】本発明の実施形態の動作手順を説明する図である。
【発明を実施するための形態】
【００４９】
本発明の実施形態を説明する。上述のように、一般のアルゴリズムに対するMPCプロトコルは非常に効率が悪い。本実施形態によれば、検索アルゴリズムFを適切に設計することで、効率的な検索を実現する。
【００５０】
MPCプロトコルの効率が悪くなる原因は掛け算にあることが知られている。すなわち、検索アルゴリズムFが掛け算を含んでいればいるほど、必要な値F(x[1],…,x[n])を計算する為のMPCプロトコルの効率が悪くなる。
【００５１】
そこで、本実施形態では、MPCプロトコルの効率を上げる為、可能な限り、掛け算を使わずに、検索を可能とするアルゴリズムを実現している。
【００５２】
特に制限されるものではないが、実施形態で扱う文字列は、「ワード」と呼ばれる単位を複数個並べたものである。「ワード」はWビット（Wは例えば8、16、32等、所定の正整数）のビット列であるものとする。
【００５３】
データベースに保存されている文字列a=a[1]||…||a[n]が、検索文字列b=b[1]||…||b[m]を部分文字列として含むことを、「aは検索条件bにヒットした」とみなす。ただし、「||」は文字列の連結（concatenation）を表す。a[1]〜a[n]、b[1]〜b[m]はワードである。
【００５４】
aが検索条件bにヒットする必要十分条件は、以下で与えられる。 
【００５５】
あるj∈{1,…n-m}が存在し、
a[j+1]=b[1] 、且つ、 …且つ、a[j+m]=b[m]
・・・(6)
【００５６】
検索を行う方法を提示する為、まず、
「aは検索条件bにヒットした」という条件を別の条件に書き換えていく。
【００５７】
関数Gを以下で定義する。
G(x)=0  if x=0
G(x)=1  if x≠0
・・・(7)
（すなわち、x=0なら、G(x)=0、x=0でないなら、G(x)=1)。
【００５８】
すると、上の条件(式(6))は、以下と同値である：
【００５９】
c[j,k]=G(a[j+k]-b[k])，
u[j]= c[j,1]+…+c[j,m]
とすると、
あるj∈{1,…n-m}が存在し、 
u[j]=0 mod X
・・・(8)
【００６０】
ここで、Xは整数である（具体的な値は後述する）。
【００６１】
MPCプロトコルでは、「mod X」の計算を用いているので、上記（8）では、u[j]=0 mod Xと表記している（mod X」をつけている）。
【００６２】
Xとして、2＾W（＾は冪乗演算子：２Wと等価）よりも、２を底とする対数log2 nよりも大きな値をとれば、
u[j]=0となる必要十分条件は、
u[j]=0 mod X
・・・(9)
となることが簡単に確かめられる。
【００６３】
上記した関数Gを用いることで、
「u[j]=0となるj∈{1,…n-m}が存在する」
という条件は、以下と同値であることが分かる。
【００６４】
d[j]=G(u[j])とすると、
(n-m-d[1]-d[2]-…-d[n-m]) ≠ 0 mod X
・・・（10)
【００６５】
「mod X」を取っている理由は、上記と同様である。
【００６６】
以下のアルゴリズムをFX (a,b)とすると、
aが検索条件bにヒットしたか否かを、
FX(a,b)=「ヒットした」となるか否かで判定できることがわかる(FXの添字はアルゴリズム中で「mod X」していることを明示したもの)。
【００６７】
ステップ１：
j=1,…n-m，k=1,…,mに対し、
c[j,k]=G(a[j+k]-b[k]) mod X
・・・(11)
を計算する。
【００６８】
ステップ２：
j=1,…n-mに対し、
u[j]=c[j,1]+…+c[j,m] mod X
・・・(12)
を計算する。
【００６９】
ステップ３：
j=1,…n-mに対し、
d[j]=G(u[j])
・・・(13)
を計算する。
【００７０】
ステップ４：
e=(n-m-d[1]-…-d[n-m])×(乱数) mod X
・・・(14)
を計算する。
【００７１】
ステップ５：
e=0 mod Xなら、「ヒットしない」、
e≠0 mod Xなら、「ヒットした」
・・・(15)
を出力する。
【００７２】
ステップ4で乱数を乗じているのは、後でFXを計算するMPCプロトコルを作る時に、eの値から、攻撃者に情報が漏れるのを防ぐためである。
【００７３】
前述のように、関数FXが掛け算を使えば使うほど、FXを計算するMPCプロトコルの速度は遅くなる。
【００７４】
上述のアルゴリズムFX(a,b)では、掛け算は用いられていない。このため、効率がよい。そこで、サブルーチン（subroutine）の関数Gを、可能な限り少ない回数の掛け算で実現すれば良い。
【００７５】
λ(x)をカーマイケル関数とし、H(x,X)を以下で定義する。
H(x,X)= x＾λ(X)  mod X
・・・(16)
【００７６】
カーマイケル関数λ(x)の定義より、H(x,X)は以下の値をとる。
【００７７】
x=0なら、 H(x,X)= 0 mod X,
x≠0なら、H(x,X)= 1 mod X
・・・(17)
【００７８】
そこで、FX(a,b)のサブルーチンG(x)として H(x,X)を用いることができる。
【００７９】
前述したように、Xはワードのビット長Wより大きくなければならない。このため、G(x)としてH(x,X)を用いると、Wが大きな値の時に、効率が悪くなる。例えばC言語のint型32ビットを１ワードとすると(W=32)、２＾W= ２＾32 = 4,294,967,296と大きな値になる為、効率が悪い。
【００８０】
そこで、FX(a,b)にさらなる改良を施すことで、この問題を回避する。
【００８１】
改良のため、Xを、
X=Πp∈S p
・・・(18)
を満たすように選ぶ。ここで、集合Sは、任意のp, q∈Sに対し、pとqは互いに素を満たす整数の集合である。したがって、Ｘは集合Sに含まれる互いに素の整数p， q，…の積である。
【００８２】
そして、以下のアルゴリズムIX(a,b)を考える：
【００８３】
＜アルゴリズムIX(a,b)＞
各p∈Sに対し、Fp(a,b)を実行する（サブルーチンG(x)としてH(x,p)を用いる）。
【００８４】
Fp(a,b)の出力をe[p]とする。
全てのp∈Sに対し、
e[p]=0 mod pであるなら、「ヒットしない」、
e[p]≠0 mod pであるなら、「ヒットした」
を出力する。
【００８５】
X=Πp∈S p
であることから、
任意のp∈Sに対し、カーマイケル関数λ(p)は、λ(X)の約数である。すなわち、Xはpを約数として含み、カーマイケル関数の定義(式(2))から、λ(p)はλ(X)の約数であることが分かる。
【００８６】
x^λ(p)が1もしくは0であることから、以下が成り立つ。
【００８７】
H(x,X) = x＾λ(X) = x＾λ(p) =H(x,p) mod p
・・・(19)
【００８８】
よって中国人剰余定理から、IX(a,b)の出力は、FX(a,b)の出力と等しい。
しかも、実施形態のアルゴリズムIX(a,b)では、FX(a,b)のH(x,X)の代わりに、
H(x,p)= x＾λ(p)  mod p
・・・(20)
を計算する。
【００８９】
λ(p)の方がλ(X)よりも小さいことから、
H(x,p)=x＾λ(p) mod p
の計算の方が、
H(x,X)=x＾λ(X) mod X
の計算よりも効率的である。
【００９０】
よって、上記アルゴリズムIX(a,b)は、前述した課題（FX(a,b)の効率が悪い）を解決している。
【００９１】
そこで、本実施形態では、アルゴリズムIX(a,b)を実行するMPCプロトコルを作る。以下、実施形態について説明する。
【００９２】
＜装置構成＞
図１は、本発明の実施形態のシステムの構成例を説明する図である。図１を参照すると、実施形態のシステムは、登録装置1、検索装置2、N台のサーバ装置3-1, …,サーバ装置3-Nを備えている。登録装置1は、検索装置2と別の装置であっても同一の装置であってもよい。また、登録装置1や検索装置2は、サーバ装置3，… ,サーバ装置3-Nのいずれかと一致していても良い。
【００９３】
登録装置1は、登録文字列シェア生成部11と、通信部12を備えている。登録装置1は、サーバ装置3-1,…,サーバ装置3-Nに文字列a[1], a[2],…を登録する。
【００９４】
文字列a[1], a[2],…を登録する登録装置1は、文字列毎に異なっても良いし、同一でも良い。図１では、a[1], a[2],…を全て同一の登録装置１が登録し、t番目の文字列を登録するものとする。なお、登録装置１の各部の一部又は全ての処理、制御は、プログラム制御で実現するようにしてもよいことは勿論である。
【００９５】
検索装置2は、検索文字列シェア生成部21と、通信部22と、復元部23を備えている。検索装置2は、サーバ装置3-1,…,サーバ装置3-Nに保管された文字列を検索する。図１では、１台の検索装置2が全ての検索を行う。ただし、検索文字列b毎に検索装置2が異なっても良い。なお、検索装置２の各部の一部又は全ての処理、制御は、プログラム制御で実現するようにしてもよいことは勿論である。
【００９６】
サーバ装置3-α（α=1,…,N）は、通信部31-αと、データ記憶部32-αと、検索応答計算部33-αを備えている。なお、サーバ装置3-αの各部の一部又は全ての処理、制御は、プログラム制御で実現するようにしてもよいことは勿論である。
【００９７】
以下、本実施形態における登録装置1、検索装置2、サーバ装置3-1,…,3-Nの動作の概略を説明する。
【００９８】
登録装置1は、登録文字列シェア生成部11を用いて、a[t]のシェアを計算し、通信部12を用いて、当該シェアを、サーバ装置3-1,…,サーバ装置3-Nに送信する。
【００９９】
サーバ装置3-1,…,サーバ装置3-Nは、それぞれ、サーバ装置の通信部31-1,…,サーバ装置の通信部31-Nを用いて、シェアを受け取り、受け取ったシェアを、それぞれデータ記憶部32-1,…,データ記憶部32-Nに記憶する。
【０１００】
なお、以上の手続きの詳細は、後述する＜登録方法＞で説明する。
【０１０１】
検索装置2は、サーバ装置3-1,…,サーバ装置3-Nに登録されたデータを検索する場合、検索文字列シェア生成部21を用いて、検索文字列のシェアを計算し、通信部22を用いて、該検索文字列のシェアをそれぞれサーバ装置3-1,…,サーバ装置3-Nに送信する。
【０１０２】
サーバ装置3-1,…,サーバ装置3-Nは、それぞれ、検索応答計算部33-1,…,33-Nを用いて、互いに通信しながら、返答すべきデータを決定する。サーバ装置3-1,…,サーバ装置3-Nは、それぞれ、検索応答のシェアを通信部33-1,…,通信部33-Nを用いて、検索装置2に送信する。
【０１０３】
検索装置2は、通信部22を用いてシェアを受信し、復元部23を用いて、シェアから検索結果を復元する。
【０１０４】
以上の手続きの詳細は後述する＜検索方法＞で説明する。
【０１０５】
本実施形態は、文字列の検索に関するものであるが、以下、登録装置がサーバ装置に登録する文字列は、いずれもn個のワードからなっているものとする。各ワードはWビットのビット列であるものとする。
【０１０６】
さらに、λをセキュリティ・パラメータとする。λが大きければ大きいほど、セキュアになるが、その分、効率が悪くなる。このため、適切なλを選択する必要がある。特に制限されないが、例えばλは160に設定することが推奨されている。
【０１０７】
Sを以下の２つの性質を満たす整数の集合とする：
【０１０８】
・任意のp, q∈Sに対し、pとqは互いに素。
・・・(21)
【０１０９】
・2＾W, log2 n ≦ Πp∈S p
・・・(22)
【０１１０】
上の条件(21)、(22)を満たせば、Sはどのような集合でも良い。例えば集合Sとして、2, 3, 5, …と、小さい素数を、上の条件（不等式(22))を満たすまで集めたものとしてもよい。
【０１１１】
Accessを集合{1,…N}上のアクセス構造とし、(Share,Reconst)をAccess-安全な秘密分散方式とする。
【０１１２】
＜登録方法＞
a[t]を文字列とし、a[t]のi番目のワードをa[t,i]と表記する。記号「||」で文字列の連結を表す。定義より、
a[t]=a[t,1]||…||a[t,n]
・・・(23)
と表記することができる。
【０１１３】
登録装置1がサーバ装置3-1，…，サーバ装置3-Nに文字列a[t]を登録する方法を説明する。
【０１１４】
ステップ1：
各i=1,…,n,  各p∈Sに対し、登録装置1の登録文字列シェア生成部11は、
Share(a[t,i],N,p)
・・・(24)
を実行し、その出力（シェア）:
x[t,i,1,p],…,x[t,i,N,p]
・・・(25)
を得る。
【０１１５】
ステップ2：
各i=1,…,n, 各α=1,…,N,  各p∈Sに対し、登録装置1はシェアx[t,i,α,p]を通信部１２を介してサーバ装置3-jに送る。
【０１１６】
ステップ3：
各α=1,…,N,  各p∈Sに対し、サーバ装置3-αは、
x[t,1,α,p]||…|| x[t,n,α,p]
・・・(26)
を保管する（||は連結（concatenation）演算子）。
【０１１７】
＜検索方法＞
a=a[1]||…||a[n]，b=b[1]||…||b[m]
・・・(27)
を文字列とするとき、aがbを部分文字列として含むとは、前述したように、
あるi∈{0,…,n-m}が存在し、
a[i+1]=b[1],…,a[i+m]=b[m]
・・・(28)
が全て成り立つことをいう。
【０１１８】
図２は、実施形態の手順を説明する図である。検索装置2がサーバ装置3-1,…,サーバ装置3-Nに登録された文字列群の中から、
b=b[1]||…||b[m]
を部分文字列として含むものを検索する手順について図２を参照して説明する。
【０１１９】
ステップ1: 
検索装置2の検索文字列シェア生成部11は、検索文字列bのシェアを生成し、サーバ装置3-1,…,サーバ装置3-Nに送信する(図２の201)。以下のステップからなる。
【０１２０】
ステップ1.1：
各p∈S，各k=1,…,mに対し、検索装置2の検索文字列シェア生成部21は、
Share(b[k], N, p)
・・・(29)
を実行し、その出力（検索文字列のシェア）：
y[k,1],…,y[k,N]
・・・(30)
を得る。
【０１２１】
ステップ1.2：
各α=1,…,N, 各k=1,…,mに対し、検索装置2は、検索文字列のシェアy[k,α]をサーバ装置3-αに送る。
【０１２２】
ステップ2：
サーバ装置3-1,…,サーバ装置3-Nはサブルーチン（subroutine）の実行による返答を決定する(図２の202)。ステップ2は以下の４ステップ2.1〜2.4からなる（ただし、図２では省略されている）。
【０１２３】
ステップ2.1：
各t=1,2,…，各p∈Sに対し以下を実行する。
【０１２４】
ステップ2.１.1：
各α=1,…,Nに対しサーバ装置3-αは登録文字列のシェア
x[t,j,α,p]
を読み込む。
【０１２５】
ステップ2.１.2：
サーバ装置3-1は、
x[t,1,1,p]||…||x[t,n,1,p]，
サーバ装置3-2は、
x[t,1,2,p]||…||x[t,n,2,p]，
…，
サーバ装置3-Nは、
x[t,1,N,p]||…||x[t,n,N,p]
をそれぞれ入力として、それぞれ、検索文字列のシェアy[k,α]（k=1,…,m, α=1,…,N）を用いて、後述するサブルーチン（subroutine）を呼び出す（subroutine  call）。
【０１２６】
サーバ装置3-1,…, サーバ装置3-Nはそれぞれサブルーチンの出力として、
e[t,1,p],…,e[t,N,p]
・・・(31)
を得る。
【０１２７】
ステップ2.2：
各t=1,2,…，各p∈Sに対し、サーバ装置3-1,…,サーバ装置3-Nは、それぞれ、e[t,1,p],…,e[t,N,p]を開示する。
【０１２８】
ただし、例えばサーバ装置3-αが不正なサーバ装置である場合、サーバ装置3-αはe[t,α,p]を開示するとは限らない。このため、開示されたデータの数は、サーバ装置の台数Nより少ないかも知れない。
【０１２９】
ステップ2.3：
各t=1,2,…，各p∈Sに対し、
E[t]={α|サーバ装置3-αはe[t,α,p]を開示した}
・・・(32)
とし、
E[t]∈Access
・・・(33)
の場合（E[t]が集合Accessに含まれる場合）、
サーバ装置3-1,…, サーバ装置3-Nは、各自、
Reconst(e[t,1,p],…, e[t,N,p])
・・・(34)
を実行し、その出力として，f[t,p]を得る。
【０１３０】
一方、E[t]∈Access
でなければ、検索手順は失敗であり，ここで検索手順を終了する。
【０１３１】
ステップ2.4：
各t=1,2,…，各α=1,…,Nに対し、以下のステップ2.4.1を実行する。
【０１３２】
ステップ2.4.1：
f[t,p]≠0 mod p
・・・(35)
となるp∈Sが存在すれば、サーバ装置3-αは、
x[t,1,α,p]||…|| x[t,n,α,p]
・・・(36)
を検索装置2に送信する。
【０１３３】
ただし、不正なサーバ装置は、
x[t,1,α,p]||…|| x[t,n,α,p]
を検索装置2に送信するとは限らない為、検索装置2が受け取るデータ数は、サーバ装置の台数Nより少ないかもしれない。
【０１３４】
ステップ3：検索装置2は、以下のように、中国人剰余定理により、検索結果の復元を行う(図２の203)。
【０１３５】
ステップ3.1：
各t=1,2,…、p∈Sに対し、
X[t]={α|サーバ装置3-αはx[t,1,α,p]||…|| x[t,n,α,p]を検索装置2に送った}
・・・(37)
とする。
【０１３６】
ステップ3.2：
X[t]∈Access
・・・(38)
の場合、以下を行う。
【０１３７】
ステップ3.2.1：
各p∈Sに対し、検索装置2は、各j=1,…nに対し、
Reconst((x[t,j,α,p])α∈X[t])
・・・(39)
を実行し、その出力として、g[t,j,p]を得る。
【０１３８】
ステップ3.2.2：
ChineseRemainder((g[t,j,p])p∈S)
・・・(40)
を実行し、その出力として、a[t,j]を得る。
【０１３９】
ステップ3.2.3：
a[t]=a[t,1]||…||a[t,n]
・・・(41)
とし、t番目のデータa[t]は、検索されたものとみなして出力する。
【０１４０】
なお、ステップ3では、各t=1,2,…、各p∈Sに対してサブルーチン（subroutine）を実行するので、(tの個数)×(pの個数)回だけ、サブルーチン（subroutine）が実行されることになる。これらのサブルーチン（subroutine）は並行して(in parallel 又はconcurrently)行ってもよいし、１つずつ、逐次的に（sequentially）行っても良い。 
【０１４１】
＜サブルーチン（subroutine）＞
図３は、サブルーチンの手順を示す図３である。図３を参照して、サブルーチンの処理（演算処理）について説明する。
【０１４２】
サーバ装置3-1において、サブルーチンは、ｘ[t,1,1,p]||…|| x[t,n,1,p]、y[k,1,p](k=1,..,m)を入力とし、…、サーバ装置3-Nにおいて、サブルーチンは、x[t,1,N,p]||…|| x[t,n,N,p], y[k,N,p](k=1,..,m)を入力として、以下のステップ1〜３を行う。なお、y[k,α,p]は各p∈S，各k=1,…,mに対して生成された検索文字列でのシェアである。
【０１４３】
ステップ1：
a[t, j+k]のシェアと検索文字列のb[k]が一致するかに関するシェアc[t,j,k,1,p],…, c[t,j,k,N,p]を計算する（図３の301）。
【０１４４】
サブルーチンのステップ１（図３の301）は、ステップ1.1と1.2からなる(図３には、図示されない)。
【０１４５】
ステップ1.1：
各α=1,…,N、各j=1,…,n-m、各k=1,…,mに対し、サーバ装置3-αは、
z[t,j,k,α,p]= x[t,j+k,α,p]- y[j,α,p] mod p
・・・(42)
を計算する。
【０１４６】
ステップ1.2：
各j=1,…,n-m、各k=1,…,mに対し、サーバ装置3-1,…,サーバ装置3-Nは、それぞれ、
(z[t,j,k,1,p],λ(p)), …, (z[t,j,k,N,p],λ(p))
・・・(43)
を入力として、べき乗剰余MPCプロトコルを実行する。なお、λ(p)はカーマイケル関数である(pと互いに素なaについてa＾λ（p）=1 mod p)。
【０１４７】
サーバ装置3-1,…,サーバ装置3-Nは、べき乗剰余MPCプロトコルの実行結果として、それぞれ、
c[t,j,k,1,p],…, c[t,j,k,N,p]
・・・(44)
を得る。
【０１４８】
ステップ2：
サーバ装置3-1,…, サーバ装置3-Nは、c[t,j,k,1,p],…c[t,j,k,N,pのk=1〜ｍの和が０か否かのシェアd[t,j,1,p],…, d[t,j,N,p]を計算する(図３の302)。ステップ2はステップ2.1と2.2からなる（図３では不図示）。
【０１４９】
ステップ2.1：
各α=1,…,N、各j=1,…,n-mに対し、サーバ装置3-αは、
u[t,j,α,p]=Σk=1,…,mc[t,j,k,α,p]
・・・(45)
を計算する。
【０１５０】
ステップ2.2：
各j=1,…,n-mに対し、サーバ装置3-1,…, サーバ装置3-Nは、それぞれ、
(u[t,j,1,p],λ(p),p), …, (u[t,j,N,p],λ(p) ,p)
・・・(46)
を入力として、べき乗剰余MPCプロトコルを実行する。
【０１５１】
サーバ装置3-1,…, サーバ装置3-Nは、べき乗剰余MPCプロトコルの実行結果としてそれぞれ、
d[t,j,1,p],…, d[t,j,N,p]
・・・(47)
を得る。
【０１５２】
ステップ３：
n-mとの差をランダム化したもののシェアを生成する(図３の303)。以下のステップ3.1、3.2、3.3からなる。
【０１５３】
ステップ3.1：
各α=1,…,Nに対し、サーバ装置3-αは、
v[t,α,p]= n-m-Σj=1,…,n-md[t,j,α,p]
・・・(48)
を計算する。
【０１５４】
ステップ3.2：
サーバ装置3-1,…, サーバ装置3-Nは、いずれもpを入力として、乱数生成MPCプロトコルを行い、その出力として、それぞれ、
r[t,1,p],…, r[t,N,p]
・・・(49)
を得る。
【０１５５】
ステップ3.3：
サーバ装置3-1,…, サーバ装置3-Nは、それぞれ、
(v[t,1,p], r[t,1,p]),…, (v[t,N,p], r[t,N,p])
・・・(50)
を入力として、乗法剰余MPCプロトコルを実行し、その出力として、それぞれ、
e[t,1,p],…,e[t,N,p]
・・・(51)
を得る。
【０１５６】
なお、ステップ1.2では、各j=1,…,n-m、各k=1,…,mに対して、べき乗剰余MPCプロトコルを行うので、(n-m)m回だけ、べき乗剰余MPCが行われることになるが、これらのべき乗剰余MPCは、並行して行ってもよいし、１つずつ逐次的に行っても良い。 
【０１５７】
同様に、ステップ2.2でも、計n-m回だけべき乗剰余MPCが行われるが、これらのべき乗剰余MPCは並行して行ってもよいし、１つずつ逐次的に行っても良い。
【０１５８】
さらにステップ3.2の乱数生成MPCは、ステップ1.1、1.2、2.1、2.2、3.1と独立に実行できるので、ステップ1.1、1.2、2.1、2.2、3.1を実行している際に、同時並行的に実行しても構わないし、先にステップ3.2を実行してからステップ1.1、1.2、2.1、2.2、3.1を行ってもよい。
【０１５９】
またステップ1.2、ステップ2.2では、カーマイケル関数値λ(p)を用いてべき乗剰余MPCを行っているが、λ(p)の代わりに、λ(p)の倍数を用いても正しく動作する。例えば、オイラー関数値φ(p)をλ(p)の代わりに用いても正しく動作する。
【０１６０】
なお、上記非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【０１６１】
上記した実施形態は、以下のように付記される（ただし、以下に制限されない）。
【０１６２】
(付記１）
登録装置と、検索装置と、複数のサーバ装置と、を備え、前記登録装置は、登録文字列を複数の法のもと秘密分散したシェアを生成する登録文字列シェア生成部を備え、
前記登録文字列シェア生成部で生成したシェアを、それぞれ前記複数のサーバ装置に送信し、
前記複数のサーバ装置では、受信したシェアを記憶部に保管し、
前記検索装置は、検索文字列を前記複数の法のもと秘密分散したシェアを生成する検索文字列シェア生成部を備え、
前記検索文字列シェア生成部で生成したシェアを、それぞれ前記複数のサーバ装置に送信し、
前記複数のサーバ装置は、それぞれの前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し、前記演算処理の実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算部を備え、
前記検索装置は、前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から、中国人剰余定理により、検索結果を復元する復元部を備えた、ことを特徴とする秘匿文字列計算システム。
【０１６３】
(付記２）
前記登録文字列をa=a[1]||…||a[n]、前記検索文字列をb=b[1]||…||b[m]とし（ただし、||は連接演算子、mとnは、m＜nの正整数）、
前記サーバ装置の前記検索応答計算部は、前記予め定められた演算処理として、
各j(j=1,…,n-m)および各k(k=1,…,m)に対し、前記登録文字列のj+kワード目のシェアと前記検索文字列のkワード目が一致するか否かによって1又は0になる値のシェアを計算する第一マルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルにより計算されたシェアを前記k毎に、前記法のもと、足し合わせ、
前記足し合わされたシェアが0になるか否かによって、0又は1になる値のシェアを計算する第二マルチパーティ計算プロトコルを実行し、
前記登録文字列のワード数から、前記検索文字列のワード数と、前記第二マルチパーティ計算プロトコルにより計算された前記シェアの総和とを、前記法のもと減算し、
前記減算した値に、乱数生成マルチパーティ計算プロトコルにより得られたシェアを、前記法のもと乗じたものを出力する、ことを特徴とする付記１記載の秘匿文字列計算システム。
【０１６４】
(付記３）
前記検索応答計算部において、前記第一マルチパーティ計算プロトコルは、前記登録文字列のj+kワード目のシェアから前記検索文字列のkワード目を前記法のもと減じたものを、前記法のカーマイケル関数値で、べき乗剰余するマルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルは、前記足し合わされたシェアを、前記法のカーマイケル関数値でべき乗剰余するマルチパーティ計算プロトコルを実行する、ことを特徴とする付記２記載の秘匿文字列計算システム。
【０１６５】
(付記４）
コンピュータシステムによる秘匿文字列計算方法であって、
登録文字列を複数の法のもと秘密分散したシェアを生成し、それぞれ複数のサーバ装置に送信して、前記複数のサーバ装置に保管し、
検索文字列を前記複数の法のもと秘密分散したシェアを、前記複数のサーバ装置に送信し、
前記複数のサーバ装置では、前記保管されている各文字列のシェア及び前記複数の法毎に、サブルーチンを呼び出して演算処理を実行し、前記演算処理の実行結果を復元して、前記保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定し、
前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から中国人剰余定理により、検索結果を復元する、ことを特徴とする秘匿文字列計算方法。
【０１６６】
(付記５）
前記登録文字列をa=a[1]||…||a[n]、前記検索文字列をb=b[1]||…||b[m]とし（ただし、||は連接演算子、mとnは、m＜nの正整数）、
各j(j=1,…,n-m)および各k(k=1,…,m)に対し、前記サーバ装置で呼び出される前記サブルーチンは、
各jおよび各kに対し、前記登録文字列のj+kワード目のシェアと検索文字列のkワード目が一致するか否かによって1又は0になる値のシェアを計算する第一マルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルにより計算されたシェアを前記k毎に、前記法のもと、足し合わせ、
前記足し合わされたシェアが0になるか否かによって、0又は1になる値のシェアを計算する第二マルチパーティ計算プロトコルを実行し、
前記登録文字列のワード数から、前記検索文字列のワード数と前記第二マルチパーティ計算プロトコルにより計算された前記シェアの総和を、前記法のもと減算し、
前記減算した値に、乱数生成マルチパーティ計算プロトコルにより得られたシェアを前記法のもと乗じたものを出力する、ことを特徴とする付記４記載の秘匿文字列計算方法。
【０１６７】
(付記６）
前記サブルーチンにおいて、前記第一マルチパーティ計算プロトコルは、前記登録文字列のj+kワード目のシェアから前記検索文字列のkワード目を前記法のもと減じたものを、前記法のカーマイケル関数値で、べき乗剰余するマルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルは、前記足し合わされたシェアを前記法のカーマイケル関数値でべき乗剰余するマルチパーティ計算プロトコルを実行する、ことを特徴とする付記５記載の秘匿文字列計算方法。
【０１６８】
(付記７）
登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から複数のサーバ装置に送信されるシェアを受信する通信部と、
前記受信した登録文字列のシェアを保管する記憶部と、
検索文字列を前記複数の法のもと秘密分散したシェアを前記複数のサーバ装置に送信する検索装置から送信されたシェアを前記通信部で受信すると、前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算部と、
を備え、
前記検索結果のシェアを前記通信部を介して前記検索装置に送信し、
前記検索装置をして、各サーバ装置から返答されたシェアの復元結果から中国人剰余定理により、検索結果を復元可能としてなる、ことを特徴とするサーバ装置。
【０１６９】
(付記８）
前記登録文字列をa=a[1]||…||a[n]、前記検索文字列をb=b[1]||…||b[m]とし（ただし、||は連接演算子、mとnは、m＜nの正整数）、
前記検索応答計算部は、前記予め定められた演算処理として、
各j(j=1,…,n-m)および各k(k=1,…,m)に対し、前記登録文字列のj+kワード目のシェアと検索文字列のkワード目が一致するか否かによって1又は0になる値のシェアを計算する第一マルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルにより計算されたシェアを前記k毎に、前記法のもと、足し合わせ、
前記足し合わされたシェアが0になるか否かによって、0又は1になる値のシェアを計算する第二マルチパーティ計算プロトコルを実行し、
前記登録文字列のワード数から、前記検索文字列のワード数と前記第二マルチパーティ計算プロトコルにより計算された前記シェアの総和を、前記法のもと減算し、
前記減算した値に、乱数生成マルチパーティ計算プロトコルにより得られたシェアを前記法のもと乗じたものを出力する、ことを特徴とする付記７記載のサーバ装置。
【０１７０】
(付記９）
前記検索応答計算部において、前記第一マルチパーティ計算プロトコルは、前記登録文字列のj+kワード目のシェアから前記検索文字列のkワード目を前記法のもと減じたものを、前記法のカーマイケル関数値で、べき乗剰余するマルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルは、前記足し合わされたシェアを前記法のカーマイケル関数値でべき乗剰余するマルチパーティ計算プロトコルを実行する、ことを特徴とする付記８記載のサーバ装置。
【０１７１】
(付記１０）
登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から複数のサーバ装置に送信されるシェアを受信して記憶部に保管する処理と、
検索文字列を前記複数の法のもと秘密分散したシェアを前記複数のサーバ装置に送信する検索装置から送信されたシェアを受信する処理と、
前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定する検索応答計算処理と、
前記検索結果のシェアを前記検索装置へ送信する処理、
を前記サーバ装置を構成するコンピュータに実行させるプログラム。
【０１７２】
(付記１１）
前記登録文字列をa=a[1]||…||a[n]、前記検索文字列をb=b[1]||…||b[m]とし（ただし、||は連接演算子、mとnは、m＜nの正整数）、
前記検索応答計算処理では、前記予め定められた演算処理として、
各j(j=1,…,n-m)および各k(k=1,…,m)に対し、前記登録文字列のj+kワード目のシェアと前記検索文字列のkワード目が一致するか否かによって1又は0になる値のシェアを計算する第一マルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルにより計算されたシェアを前記k毎に、前記法のもと、足し合わせ、
前記足し合わされたシェアが0になるか否かによって、0又は1になる値のシェアを計算する第二マルチパーティ計算プロトコルを実行し、
前記登録文字列のワード数から、前記検索文字列のワード数と、前記第二マルチパーティ計算プロトコルにより計算された前記シェアの総和とを、前記法のもと減算し、
前記減算した値に、乱数生成マルチパーティ計算プロトコルにより得られたシェアを、前記法のもと乗じたものを出力する、ことを特徴とする付記１０記載のプログラム。
【０１７３】
(付記１２）
前記検索応答計算処理において、前記第一マルチパーティ計算プロトコルは、前記登録文字列のj+kワード目のシェアから前記検索文字列のkワード目を前記法のもと減じたものを、前記法のカーマイケル関数値で、べき乗剰余するマルチパーティ計算プロトコルを実行し、
前記第一マルチパーティ計算プロトコルは、前記足し合わされたシェアを、前記法のカーマイケル関数値でべき乗剰余するマルチパーティ計算プロトコルを実行する、ことを特徴とする付記１１記載のプログラム。
【０１７４】
(付記１３）
登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から前記シェアを受け取り保管する複数のサーバ装置に接続する通信部と、
検索文字列を前記複数の法のもと秘密分散したシェアを生成する検索文字列シェア生成部と、
を備え、
前記検索文字列シェア生成部で生成したシェアを、前記通信部を介して、それぞれ前記複数のサーバ装置に送信し、前記複数のサーバ装置では、それぞれの前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し、前記演算処理の実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定し、
前記複数のサーバ装置から返答され前記通信部を介して受信したシェアを復元し、前記復元結果から、中国人剰余定理により、検索結果を復元する復元部を備えた、ことを特徴とする検索装置。
【０１７５】
(付記１４）
登録文字列を複数の法のもと秘密分散したシェアを生成する登録装置から前記シェアを受け取り保管する複数のサーバ装置に接続する検索装置を構成するコンピュータに、
検索文字列を前記複数の法のもと秘密分散したシェアを生成し、前記生成したシェアをそれぞれ前記複数のサーバ装置に送信する第１の処理を実行させ、
前記複数のサーバ装置では、それぞれの前記記憶部に保管されている各文字列のシェア及び前記複数の法毎に、予め定められた演算処理を実行し、前記演算処理の実行結果を復元して、前記記憶部に保管されている前記登録文字列のシェアを検索結果として返答するか否かを決定し、
前記複数のサーバ装置から返答されたシェアを復元し、前記復元結果から、中国人剰余定理により、検索結果を復元する第２の処理を前記コンピュータにさらに実行させるプログラム。
【符号の説明】
【０１７６】
１  登録装置
２  検索装置
３−１〜３−N  サーバ装置
１１  登録文字列シェア生成部
１２  通信部
２１  検索文字列シェア生成部
２２  通信部
２３  復元部
３１−１〜３１−N  通信部
３２−１〜３２−N  データ記憶部
３３−１〜３３−N  検索応答計算部
【図１】
2016148281.tif 000003
【図２】
2016148281.tif 000004
【図３】
2016148281.tif 000005
【国際調査報告】
2016148281.tif 000006
2016148281.tif 000007