(57)【要約】  秘密データを引数とする所定の関数の値をマルチパーティ計算する秘密計算システムは複数のサーバ装置を備え、複数のサーバ装置は、前記秘密データを秘密分散して生成された有限体上の元であるシェアを保持する記憶部と、前記シェアを拡張して拡張シェアを生成するシェア拡張部と、前記拡張シェアを用いて前記所定の関数に含まれるOR演算を実行するOR計算部と、前記拡張シェアを用いて前記所定の関数に含まれるNOT演算を実行するNOT計算部と、を有する。マルチパーティ計算におけるラウンド数を削減する。
2016159357.tif 000002
【特許請求の範囲】
【請求項１】
秘密データを引数とする所定の関数の値をマルチパーティ計算する秘密計算システムであって、
複数のサーバ装置を備え、
前記複数のサーバ装置は、前記秘密データを秘密分散して生成された有限体上の元であるシェアを保持する記憶部と、
前記シェアを拡張して拡張シェアを生成するシェア拡張部と、
前記拡張シェアを用いて前記所定の関数に含まれるOR演算を実行するOR計算部と、
前記拡張シェアを用いて前記所定の関数に含まれるNOT演算を実行するNOT計算部と、を有する、
ことを特徴とする秘密計算システム。
【請求項２】
前記シェア拡張部は、前記シェアを秘密分散して生成された複数のシェアを成分とする配列を前記拡張シェアとして生成し、
前記OR計算部は、前記拡張シェアの各成分に対して、前記有限体上の乱数のシェアを乗じて足し合わせることで、前記OR演算を実行し、
前記NOT計算部は、前記拡張シェアの各成分がシェアする値を前記有限体の位数から1を引いた値でべき乗したものを1から差し引いた値の積をマルチパーティ計算することで、前記NOT演算を実行する、
請求項１に記載の秘密計算システム。
【請求項３】
前記シェアは、Shamirの秘密分散法に基づく前記秘密データの前記有限体上のシェアであり、
前記シェア拡張部は、前記シェアに対して、Shamirの秘密分散法による0の前記有限体上のシェアを加えることで前記拡張シェアを生成する、
請求項２に記載の秘密計算システム。
【請求項４】
前記シェア拡張部は、前記シェアを秘密分散して生成された複数のシェアを前記有限体の拡大体上の元として表したものを、前記拡張シェアとして生成し、
前記OR計算部は、OR演算の対象となる拡張シェアに対して、前記拡大体上の乱数のシェアを乗じて足し合わせることで前記OR演算を実行し、
前記NOT計算部は、NOT演算の対象となる拡張シェアを前記拡大体の基底で成分表示し、各成分に対応する基底を前記有限体の位数のべき乗でべき乗したものを各成分に乗じたものの和を求め、求めた和がシェアしている値の積を前記有限体の位数から1を引いた値でべき乗したものを1から減じた値をマルチパーティ計算することで、前記NOT演算を実行する、
請求項１に記載の秘密計算システム。
【請求項５】
前記シェアは、Shamirの秘密分散法に基づく前記秘密データの前記有限体上のシェアであり、
前記シェア拡張部は、前記シェアに対して、Shamirの秘密分散法による0の前記拡大体上のシェアを加えることで、前記拡張シェアを生成する、
請求項４に記載の秘密計算システム。
【請求項６】
前記複数のサーバ装置は、登録対象文字列の各ワードを秘密分散して生成されたシェアと、検索装置から受け付けた検索対象文字列の各ワードを秘密分散して生成されたシェアを前記記憶部に保持し、
前記シェア拡張部、前記OR計算部、および、前記NOT計算部を用いて、前記登録文字列の前記各ワードと前記検索文字列の前記各ワードの差のべき乗のシェアを、前記登録文字列の前記各ワードの前記シェアと前記検索文字列の前記各ワードの前記シェアとを用いてマルチパーティ計算し、前記べき乗のORのシェアを前記べき乗のシェアを用いてマルチパーティ計算し、前記ORされた値のNOTを前記ORされた値のシェアを用いてマルチパーティ計算し、前記NOTされた値のORを前記NOTされた値のシェアを用いてマルチパーティ計算し、
前記検索装置は、前記計算された前記NOTされた値のORに基づいて、検索対象文字列が登録対象文字列に部分一致したか否かを判定する、
請求項１ないし５のいずれか１項に記載の秘密計算システム。
【請求項７】
請求項１ないし６のいずれか１項に記載の秘密計算システムに含まれる前記複数のサーバ装置のうちの一のサーバ装置。
【請求項８】
秘密データを引数とする所定の関数の値を複数のサーバ装置を用いてマルチパーティ計算する秘密計算方法であって、
前記複数のサーバ装置のうちの一のサーバ装置が、前記秘密データを秘密分散して生成された有限体上の元であるシェアを受け付けるステップと、
前記シェアを拡張して拡張シェアを生成するステップと、
前記拡張シェアを用いて前記所定の関数に含まれるOR演算を実行するステップと、
前記拡張シェアを用いて前記所定の関数に含まれるNOT演算を実行するステップと、を含む、
ことを特徴とする秘密計算方法。
【請求項９】
前記一のサーバ装置は、前記シェアを秘密分散して生成された複数のシェアを成分とする配列を前記拡張シェアとして生成し、
前記拡張シェアの各成分に対して、前記有限体上の乱数のシェアを乗じて足し合わせることで、前記OR演算を実行し、
前記拡張シェアの各成分がシェアする値を前記有限体の位数から1を引いた値でべき乗したものを1から差し引いた値の積をマルチパーティ計算することで、前記NOT演算を実行する、
請求項８に記載の秘密計算方法。
【請求項１０】
秘密データを引数とする所定の関数の値を複数のコンピュータを用いてマルチパーティ計算するプログラムであって、
前記秘密データを秘密分散して生成された有限体上の元であるシェアを受け付ける処理と、
前記シェアを拡張して拡張シェアを生成する処理と、
前記拡張シェアを用いて前記所定の関数に含まれるOR演算を実行する処理と、
前記拡張シェアを用いて前記所定の関数に含まれるNOT演算を実行する処理と、を前記複数のコンピュータのうちの一のコンピュータに実行させる、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１５−０７７０６４号（２０１５年４月３日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、秘密計算システム、サーバ装置、秘密計算方法、および、プログラムに関し、特にマルチパーティ計算手法に基づく秘密計算システム、サーバ装置、秘密計算方法、および、プログラムに関する。
【背景技術】
【０００２】
まず、本発明の背景技術と、本発明を記述するために必要な用語について説明する。【０００３】
「秘密分散」
秘密分散方式(Share, Reconst)は、ユーザが保有している秘密aを複数のサーバ装置1, …, Nでシェアして持つためのプロトコルであり、秘密aからシェアを作るシェア生成関数Shareと、シェアから秘密aを復元する復元関数Reconstから成る。非特許文献１に記載された方式をはじめとして、秘密aおよびシェアは有限体の元であることが多い。本発明でも、秘密aおよびシェアが有限体の元である状況を考える。以下では、かかる状況における秘密分散法式について説明する。【０００４】
Fを有限体とするとき、秘密aとシェアが有限体Fの元である秘密分散を「Fにおける秘密分散」という。また、「Fおける秘密分散」で生成されたシェアを「秘密aのF上のシェア」または「秘密aのFでのシェア」という。【０００５】
ShareおよびReconstの関数の入出力は、次のとおりである。
・シェア生成関数Shareは、秘密aとサーバ装置の台数Nと有限体F（ないし、有限体Fに関する情報）を入力として受け取り、秘密aのシェアs[1], …, s[N]を出力する。
・復元関数Reconstは、シェアs[1], …, s[N]の一部または全部と有限体F（ないし、有限体Fに関する情報）を入力として受け付け、秘密aまたは「復元失敗」を意味するデータを出力する。【０００６】
秘密分散方式(Share, Reconst)は、以下の手順で用いられる。まず、ユーザUは、秘密aをサーバ装置1, ..., Nにシェアする場合、Share(a, N, F)を実行して出力s[1], …, s[N] ∈ Fを得る。次に、ユーザはシェアs[1], ..., s[N]を、それぞれサーバ装置1, ..., Nに送信する。後に、シェアから秘密を復元する必要が生じた場合、{i_1, …, i_v} ∈ Accessを満たすサーバ装置i_1, ..., i_vが自身のシェアs[i_1], … ,s[i_v]をユーザUに送信する。次に、ユーザUは、Reconst(s[i_1], …, s[i_v], F)を実行して秘密aを得る。【０００７】
ここでは、ユーザUがReconst(s[i_1], …, s[i_v], F)を実行するケースについて説明した。ただし、ユーザU以外のユーザ、または、サーバ装置がReconst(s[i_1], …, s[i_v], F)を実行してもよい。【０００８】
さらに、{1, …, N}の部分集合の集合Accessが以下を満たすとき、集合Accessを{1, …, N}上のアクセス構造という。
・S ∈ AccessかつS ⊂ Tであれば、T ∈ Access．【０００９】
また、{1, …, N}上のアクセス集合Accessに対して、(Share, Reconst)が以下の性質を満たすとき、(Share, Reconst)はAccess-安全であるという。
・s[1], …, s[N]をShare(a, N, F)の出力、S = {i_1, …, i_v}を{1, …, N}の部分集合とする。この場合、S ∈ Accessであるとき、Reconst(s[i_1], .., s[i_v], F)はaを出力する。一方、S ∈ Accessでないとき、s[i_1], .., s[i_v]からaのいかなる部分情報も知ることができない。【００１０】
「Shamirの秘密分散法」
次に、非特許文献１においてShamirによって提案された秘密分散法（以下、「Shamir秘密分散法」という。）について説明する。Shamir秘密分散法では、「しきい値」という自然数Kを事前に決めて固定する。なお、しきい値Kはサーバ装置の台数N以下とする必要がある。【００１１】
Shamir秘密分散法におけるアクセスAccessは
Access = {S ⊂ {1, …, N} | SはK個以上元を含む}
である。よって、Shamir秘密分散法では、サーバ装置1, ..., NのうちのK台以上が集まれば、秘密を復元することができる。一方、Shamir秘密分散法では、K台未満のサーバ装置が集まっても、秘密に関する情報を一切得ることができない。【００１２】
Shamir秘密分散法は、有限体上の秘密分散法である。Fを有限体とするとき、Shamir秘密分散法のシェア関数、および、復元関数を、それぞれShamirShare(a, K, N, F)およびShamirReconst(s[i_1], …, s[i_v], K, N, F)と表す。ここで、a ∈ Fは秘密であり、s[i_1], …, s[i_v] ∈ Fはシェアである。また、関数ShamirShareおよびShamirReconstは、以下のように定義される。【００１３】
・ShamirShare(a, K, N, F) : 乱数r[1], …, r[K - 1]をランダムに選び、i = 1, …, Nに対し、有限体F上の多項式f(X)を
f(X) = a + Σk = 1, …, K - 1r[k]Xk
により定義し、
s[i] = f(i)
を計算し、s[1], …, s[N]をそれぞれサーバ装置1, ..., Nのシェアとして返す。
・ShamirReconst(s[i_1], …, s[i_v], K, N, F) : vがK以上の場合、任意のu = 1, …, vに対して、f(i_u) = s[i_u]を満たす有限体F上のK - 1次多項式f(X)を求めてf(0)を出力する。一方、vがK未満の場合、秘密を復元できない旨のメッセージを返す。【００１４】
「マルチパーティ計算（ＭＰＣ：Multi Party Computation）プロトコル」
ＭＰＣプロトコルとは、何らかのアルゴリズムを複数のサーバ装置でセキュアに計算する手段のことである。本発明では、ＭＰＣプロトコルとして、「乗法剰余ＭＰＣプロトコル」および「乱数生成ＭＰＣプロトコル」を用いる。【００１５】
乗法剰余ＭＰＣプロトコルにおいて、s[1], …, s[N]は何らかの整数aの有限体F上のシェアとする。一方、t[1], …, t[N]は、何らかの整数bの有限体F上のシェアとする。【００１６】
乗法剰余ＭＰＣプロトコルとは、乗法剰余アルゴリズムをセキュアに実行するＭＰＣであり、サーバ装置1 , ..., M[N]が、それぞれ(s[1], t[1], F), ..., (s[N], t[N], F)を入力として実行され、サーバ装置1, ..., M[N]がそれぞれz[1], ..., z[n]を出力として受け取る。ここで、z[1], …, z[N]はF上の積abのF上のシェアである。【００１７】
一方、乱数生成ＭＰＣプロトコルとは、乱数生成アルゴリズムをセキュアに実行するＭＰＣであり、サーバ装置1, ..., Nがいずれも有限体Fを入力として実行され、サーバ装置1, ..., Nがそれぞれu[1], ..., u[N]を出力として受け取る。ここで、u[1], …, u[N]は有限体F上の一様乱数のFにおけるシェアである。【００１８】
これらのプロトコルの実現方法として、様々な方法（例えば、非特許文献２に記載された方法）を用いることが可能である。【００１９】
なお、特許文献１には、入力した秘密情報を部分秘密情報に分割し、分割した部分秘密情報と乱数または当該部分秘密情報との排他的論理和演算を実行して部分分散情報を生成し、生成された部分分散情報を連結して分散情報を生成して、生成された分散情報を所定の人数の管理者に送信する技術が記載されている。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２００９−０３７０９３号公報
【非特許文献】
【００２１】
【非特許文献１】A. Shamir, "How to Share a Secret," Communications of the ACM, November 1979, Volume 22, Number 11, pp. 612 - 613.
【非特許文献２】O. Goldreich, S. Micali, and A. Wigderson, "HOW TO PLAY ANY MENTAL GAME or A completeness Theorem for Protocols with Honest Majority," in Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing, ACM Press, 1987, pp. 218 - 229.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
上記特許文献１および非特許文献１、２の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。【００２３】
クラウド技術の普及により、ユーザがクラウド等に設けられたデータベースにデータを預け、その後、データベースに預けたデータの中からユーザが必要なデータを検索して利用するサービスが一般化しつつある。【００２４】
しかし、このようなサービスでは、データベースの管理者はユーザが預けたデータをすべて閲覧することができる。したがって、ユーザがデータをデータベースに預けると、ユーザのプライバシーがデータベース管理者に筒抜けになるおそれがある。【００２５】
このような危険を回避するために、データベースに預けるデータをユーザが暗号化することが考えられる。しかしながら、データを暗号化してしまうと、後でデータベースから必要なデータを検索しようと思っても、暗号化によりデータが読めなくなっているため、検索ができないという問題が生じる。【００２６】
このようなジレンマを解決する技術として、マルチパーティ計算（ＭＰＣ：Multi-Party Computation）プロトコルと呼ばれる技術が知られている。ＭＰＣプロトコルは、複数台のサーバ装置にデータa[1], …, a[m]を「シェア」して持った状態からスタートし、シェアされたデータから何らかのアルゴリズムφに従って必要な値φ(a[1], …, a[m])をセキュアに計算するプロトコルである。ここで、「シェア」は秘密分散方式で生成される。【００２７】
マルチパーティ計算に関する関連技術においては、論理演算子AND、OR、NOTのマルチパーティ計算方法を提案するとともに、一般の関数φに対してはφをAND、OR、NOT等の論理演算子で表した上で、論理演算子AND、OR、NOTのマルチパーティ計算方法を組み合わせることでφのマルチパーティ計算を実現している。【００２８】
関連技術に係るマルチパーティ計算では、ANDの計算を行うために、サーバ装置群は定数ラウンド分の通信を行う必要がある。したがって、J個のビットa[1], …, a[J]をANDしたa[1] AND … AND a[J]を計算するためには、最低でもO(log J)ラウンドを要する。【００２９】
例えば、１回のANDの計算にXラウンド要する状況下で8個（J = 8）のデータをANDしたa[1] AND … AND a[8]を計算するためには、以下の計算が必要となる。
・1〜Xラウンド目でb[1] = a[1] AND a[2], b[2] = a[3] AND a[4], b[3] = a[5] AND a[6], b[4] = a[7] AND a[8]をマルチパーティ計算し、
・X+1〜2Xラウンド目でc[1] = b[1] AND b[2], c[2] = b[3] AND b[4]をマルチパーティ計算し、
・2X+1〜3Xラウンド目でc[1] AND c[2]をマルチパーティ計算する。
したがって、AND計算において、合計3X = (log2 8)・Xラウンドを要する。【００３０】
このように、関連技術に係るマルチパーティ計算では、多数のデータをANDする際、多数のラウンド数を要するという問題がある。【００３１】
特に、マルチパーティ計算を検索に応用した場合、上述の問題が顕著となる。例えば、クエリb = b[1] … b[m]を部分ビット列として含むビット列a = a[1] … a[n]を検索したい場合、φとして
φ(a, b) = 1（bがaの部分ビット列である場合）、
φ(a, b) = 0（それ以外の場合）
を満たすものを採用すればよい。【００３２】
ここで、bがaの部分ビット列であることは、論理式
∃ j  (b[j + 1] = a[j + 1]) AND … AND (b[j + n] = a[j + n])
を満たすことと同値である。したがって、部分ビット列であるか否かを判定するには、n個のデータのANDをマルチパーティ計算する必要があり、多数のラウンド数を要する。【００３３】
なお、特許文献１に記載された技術によっても、上述の問題は解消されない。【００３４】
そこで、マルチパーティ計算におけるラウンド数を削減することが課題となる。本発明の目的は、かかる課題解決に寄与する秘密計算システム、サーバ装置、秘密計算方法、および、プログラムを提供することにある。
【課題を解決するための手段】
【００３５】
本発明の第１の態様に係る秘密計算システムは、秘密データを引数とする所定の関数の値をマルチパーティ計算する秘密計算システムであって、複数のサーバ装置を備え、前記複数のサーバ装置は、前記秘密データを秘密分散して生成された有限体上の元であるシェアを保持する記憶部と、前記シェアを拡張して拡張シェアを生成するシェア拡張部と、前記拡張シェアを用いて前記所定の関数に含まれるOR演算を実行するOR計算部と、前記拡張シェアを用いて前記所定の関数に含まれるNOT演算を実行するNOT計算部と、を有する。【００３６】
本発明の第２の態様に係るサーバ装置は、第１の態様に係る秘密計算システムに含まれる前記複数のサーバ装置のうちの一のサーバ装置である。【００３７】
本発明の第３の態様に係る秘密計算方法は、秘密データを引数とする所定の関数の値を複数のサーバ装置を用いてマルチパーティ計算する秘密計算方法であって、前記複数のサーバ装置のうちの一のサーバ装置が、前記秘密データを秘密分散して生成された有限体上の元であるシェアを受け付けるステップと、前記シェアを拡張して拡張シェアを生成するステップと、前記拡張シェアを用いて前記所定の関数に含まれるOR演算を実行するステップと、前記拡張シェアを用いて前記所定の関数に含まれるNOT演算を実行するステップと、を含む。【００３８】
本発明の第４の態様に係るプログラムは、秘密データを引数とする所定の関数の値を複数のコンピュータを用いてマルチパーティ計算するプログラムであって、前記秘密データを秘密分散して生成された有限体上の元であるシェアを受け付ける処理と、前記シェアを拡張して拡張シェアを生成する処理と、前記拡張シェアを用いて前記所定の関数に含まれるOR演算を実行する処理と、前記拡張シェアを用いて前記所定の関数に含まれるNOT演算を実行する処理と、を前記複数のコンピュータのうちの一のコンピュータに実行させる。なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することもできる。
【発明の効果】
【００３９】
本発明に係る秘密計算システム、サーバ装置、秘密計算方法、および、プログラムによると、マルチパーティ計算におけるラウンド数を削減することが可能となる。
【図面の簡単な説明】
【００４０】
【図１】一実施形態に係る秘密計算システムの構成を例示するブロック図である。
【図２】第１および第２の実施形態に係る秘密計算システムの構成を例示するブロック図である。
【図３】第３および第４の実施形態に係る秘密計算システムの構成を例示するブロック図である。
【発明を実施するための形態】
【００４１】
＜発明の概要＞
はじめに、本発明の概要（基本的なアイデア）について説明する。
【００４２】
関連技術に係るマルチパーティ計算は、以下のようにして構築されている。
・足し算を計算するマルチパーティ計算と掛け算を計算するマルチパーティ計算を作る。
・ANDを計算するマルチパーティ計算、NOTを計算するマルチパーティ計算、および、ORを計算するマルチパーティ計算を、上述の足し算と掛け算のマルチパーティ計算を組み合わせて作る。
・任意の関数はAND演算子とNOT演算子とOR演算子を用いて表現できるので、上述のAND, OR, NOTのマルチパーティ計算を組み合わせて実現する。
【００４３】
上記において、足し算のマルチパーティ計算は、0ラウンドで（すなわち、サーバ装置間の通信を行うことなく）実現できることが知られている。一方、掛け算のマルチパーティ計算は定数ラウンドを要することが知られている。
【００４４】
AND、OR、NOTのマルチパーティ計算は、掛け算のマルチパーティ計算をベースとして実現されている。したがって、これらの論理演算子のマルチパーティ計算も定数ラウンドを要する。特に、複数個のデータのORや複数データのANDをマルチパーティ計算するには、上述のように多数のラウンド数を要する。
【００４５】
そこで、本発明では、NOTのマルチパーティ計算と複数データのORのマルチパーティ計算を、可能な限り少ない掛け算で実現する。これにより、マルチパーティ計算のラウンド効率の改善を図る。なお、AND演算子はORとNOTを組み合わせて表現することができるので、ANDのマルチパーティ計算はORとNOTのマルチパーティ計算によって実現することができる。
【００４６】
本発明において、NOT演算子のマルチパーティ計算と複数データのOR演算子のマルチパーティ計算は、それぞれ、以下のアイデアに基づいて実行される。
【００４７】
まず、有限体Fを固定し、有限体Fの元0を真理値「FALSE」、0以外の元を真理値「TRUE」に対応させる。マルチパーティ計算で用いられる各ビットは真理値であるため、各ビットがFALSEであるかTRUEであるかに応じて、0または0以外の有限体Fの元のいずれかを割り振る。
【００４８】
NOT aをマルチパーティ計算するには、aのシェアを用いて
1 - aq - 1
のシェアをマルチパーティ計算すればよい。ここで、qは有限体Fの位数である。
【００４９】
Fermatの小定理より、1 - aq - 1はaが0の場合1となり、aが0以外の場合0となる。よって、上記の計算によりNOTが計算されることになる。
【００５０】
一方、a[1], …, a[J]のORをマルチパーティ計算するには、i = 1, …, Jに対するa[i]の有限体F上のシェアs[j, 1], …, s[j, N]をそれぞれサーバ装置1, ..., Nが持っている状態からスタートし、n = 1, …, Nに対し各サーバ装置nが
Σj = 1, …, J s[j, n]u[j, n] ∈F
を計算する。ここで、(u[j, n])n = 1, …, Nは有限体F上の何らかの乱数r[j]のシェアである。
【００５１】
定義より(Σj = 1, …, J s[j, n]u[j, n])n = 1, …, NはV = Σj = 1, …, J a[j]r[j]のシェアになっている。a[1] = … = a[J] = 0である場合、Vは0になり、これはa[1] OR …. OR a[J] = 0と一致する。一方a[1], …, a[J]の中に0でないものがある場合、r[j]は乱数であるため、V = Σj = 1, …, J a[j]r[j]は確率1 - (1/q)で0以外の値になる。すなわち、qを十分大きい値にとることで、高い確率でVはa[1] OR … OR a[J] = 1と一致する。
【００５２】
以上の議論により、有限体Fの位数qを十分大きくとることにより、NOT演算子とOR演算子のマルチパーティ計算を高い確率で正しく実行することができる。
【００５３】
そこで、位数qを大きな値に設定することが考えられる。しかしながら、NOT演算子は1 - aqのマルチパーティ計算により実現されているので、qを大きくするに従ってNOT演算子の計算のラウンド効率が悪化するというジレンマが生じる。
【００５４】
本発明では、かかるジレンマを２通りの方法で解決する。なお、以下の解決方法１、２は、それぞれ、後述する第１、第２の実施形態において採用される。
【００５５】
［解決方法１］
第１の解決方法は、次のとおりである。すなわち、上述のジレンマを解決するため、有限体Fの位数qを小さな値としたまま、代わりに、１つの値aをλ回秘密分散することでλ個のシェアの組(s[n, 1])n = 1, … N、…, (s[n, λ])n = 1, … Nを生成し、サーバ装置nは(s[n, 1], …, s[n, λ])を保持する。ここで、λはセキュリティ・パラメータである。また、(s[n, 1], …, s[n, λ])のことをaの「拡張シェア」という。
【００５６】
拡張シェア(s[n, 1], …, s[n, λ]) n = 1, … Nに対し、(s[n, 1])n = 1,…, N, …, (s[n, λ])n = 1, …, Nがシェアしている値をそれぞれu[1], …, u[λ]とする。この場合、u[1] = … = u[λ] = 0のとき、拡張シェアはFALSEをシェアしているものとみなし、それ以外のとき、拡張シェアはTRUEをシェアしているものとみなす。
【００５７】
｛解決方法１におけるOR計算｝
OR計算では、拡張シェアの各成分s[n, 1], …, s[n, λ]に対し、前述のように乱数との積の和を取る。これにより「乱数との積の和」という計算がλ回繰り返されることになるので、OR計算を間違える確率は1/qλとなり、間違い確率はλに対して指数関数的に小さくなる。よって、λを大きくすることで、q自身を小さく保ったまま間違い確率を小さくすることができる。これにより、上述のジレンマを解消することができる。
【００５８】
｛解決方法１におけるNOT計算｝
一方、NOT計算の際には、s[n, 1], …, s[n, λ]がシェアしている値をu[1], …, u[λ]とするとき、v = (1 - u[1]q - 1) … (1 - u[λ]q - 1)のシェアをマルチパーティ計算し、vのシェアの拡張シェアを作る。Fermatの小定理より、u[1], …, u[λ]がすべて0の場合vは1になり、それ以外の場合vは0になる。したがって、以上の計算はNOT演算子に対応する。
【００５９】
［解決方法２］
解決方法１では、通常のシェアを拡張シェアに変換する手続きを導入した。一方、第２の解決方法では、変換手続きとして、通常のシェアに0のF上のシェアを足し合わせる方法が用いられる。第２の解決方法では、上述のジレンマを解決するため、有限体Fの位数qを小さな値としつつ、有限体Fの拡大体Lの位数を大きくする。さらに、必要に応じて有限体F上のシェアを拡大体L上のシェアに変換する。変換後のシェアを「拡張シェア」と呼ぶ。第２の解決方法においても、通常のシェアを拡張シェアに変換する変換手続が導入される。ただし、第２の解決方法では、変換手法として、通常のシェアに0の拡大体L上のシェアを足し合わせる方法が用いられる。
【００６０】
｛解決方法２におけるOR計算｝
OR計算において、
Σj = 1, …, J T[j, n]u[j, n] ∈ L
を計算する。ここでT[j, n]はa[j]の拡張シェアであり、u[j, n]は拡大体L上の何らかの乱数のシェアである。有限体Fの位数q自身は小さい場合であっても、拡大体Lの位数Qを大きく取ることで、OR計算の間違い確率は小さくなる。すなわち、上述のジレンマは解消される。
【００６１】
｛解決方法２におけるNOT計算｝
NOT aをマルチパーティ計算するには、aの拡張シェアを用いて
1 - aQ - 1
のシェアをマルチパーティ計算する。ここで、Qは拡大体Lの位数である。しかし、前述の理由でQは大きい値にする必要があるため、単純に1 - aQ-1のシェアをマルチパーティ計算しようとすると、NOT計算の効率が悪くなるという問題がある。そこで、次のようにしてaQの計算を効率化する。
【００６２】
Lは有限体Fの拡大体であるため、拡大体Lは有限体F上線形空間とみなせる。そこで、E[1], …, E[λ]を拡大体LのF上線形空間の基底とすると、拡大体Lの任意の元aを
Σl = 1, …, λa[l]E[l]
と表すことができる。また、定義より明らかにQ = qλである。
【００６３】
したがって、
aQ-1 = (Σl = 1, …, λa[l]E[l])^{qλ - 1} = Σl = 1, …, λa[l]E[l]^{(1 + q + … + qλ - 1)(q - 1)}
= (Πi = 0, …, λ - 1Σl = 1, …, λa[l]E[l]^{q^i})q - 1
である。
【００６４】
左辺をマルチパーティ計算する代わりに、右辺をマルチパーティ計算することで、効率的にNOTを計算することができる。
【００６５】
＜一実施形態＞
次に、本発明の一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００６６】
図１は、一実施形態に係る秘密計算システム１０の構成を例示するブロック図である。図１を参照すると、秘密計算システム１０は、秘密データを引数とする所定の関数の値をマルチパーティ計算する秘密計算システムであって、複数のサーバ装置２−１〜２−Ｎを備えている。
【００６７】
サーバ装置２−１〜２−Ｎは、秘密データを秘密分散して生成された有限体（F）上の元であるシェアを保持する記憶部２２−１〜２２−Ｎと、前記シェアを拡張して拡張シェアを生成するシェア拡張部２３１−１〜２３１−Ｎと、前記拡張シェアを用いて前記所定の関数に含まれるOR演算を実行するOR計算部２３２−１〜２３２−Ｎと、前記拡張シェアを用いて前記所定の関数に含まれるNOT演算を実行するNOT計算部２３３−１〜２３３−Ｎと、を有する。
【００６８】
ここで、シェア拡張部２３１−１〜２３１−Ｎは、前記シェアを秘密分散して生成された複数のシェアを成分とする配列を拡張シェアとして生成してもよい。このとき、OR計算部２３２−１〜２３２−Ｎは、拡張シェアの各成分に対して、有限体（F）上の乱数のシェアを乗じて足し合わせることでOR演算を実行する。また、NOT計算部２３３−１〜２３３−Ｎは、前記拡張シェアの各成分がシェアする値を前記有限体の位数（q）から1を引いた値（q - 1）でべき乗したものを1から差し引いた値の積をマルチパーティ計算することで、NOT演算を実行する。
【００６９】
一方、シェア拡張部２３１−１〜２３１−Ｎは、前記シェアを秘密分散して生成された複数のシェアを有限体（F）の拡大体（L）上の元として表したものを、前記拡張シェアとして生成するようにしてもよい。このとき、OR計算部２３２−１〜２３２−Ｎは、OR演算の対象となる拡張シェアに対して、拡大体（L）上の乱数のシェアを乗じて足し合わせることで、OR演算を実行する。また、NOT計算部２３３−１〜２３３−Ｎは、NOT演算の対象となる拡張シェアを拡大体（L）の基底で成分表示し、各成分に対応する基底を有限体（F）の位数（q）のべき乗でべき乗したものを各成分に乗じたものの和を求め、求めた和がシェアしている値の積を有限体（F）の位数（q）から1を引いた値（q - 1）でべき乗したものを1から減じた値をマルチパーティ計算することで、NOT演算を実行する。
【００７０】
かかる秘密計算システム１０によると、マルチパーティ計算におけるラウンド数を削減することが可能となる。なぜなら、秘密計算システム１０によれば、有限体Fの位数qを大きくすることなく、OR演算子およびNOT演算子を高い確率で正しく計算することができるからである。
【００７１】
＜実施形態１＞
次に、第１の実施形態に係る秘密計算システムについて、図面を参照して説明する。はじめに、本実施形態と、後述する第２の実施形態との間で共通する構成および動作について説明する。
【００７２】
以下では、λをセキュリティ・パラメータとする。また、Nをサーバ装置の台数とし、有限体Fの位数qをN以上とする。さらに、{0, 1}を自然に有限体Fの部分集合とみなす。
【００７３】
［構成］
図２は、本実施形態に係る秘密計算システム１０の構成を例示するブロック図である。なお、後述する第２の実施形態に係る秘密計算システム１０も図２と同様の構成を有する。
【００７４】
図２を参照すると、秘密計算システム１０は、登録装置１とサーバ装置２−１〜２−Ｎを備えている。なお、サーバ装置２−１〜２−Ｎのうちのいずれかが登録装置１の機能を兼ねていてもよい。
【００７５】
登録装置１は、通信部１１、記憶部１２、および、計算部１３を備えている。また、計算部１３は、シェア生成部１３１と復元部１３２を備えている。
【００７６】
サーバ装置２−ｎ（n = 1, …, N）は、通信部２１−ｎ、記憶部２２−ｎ、および、計算部２３−ｎを備えている。また、計算部２３−ｎは、シェア拡張部２３１−ｎ、OR計算部２３２−ｎ、および、NOT計算部２３３−ｎを備えている。
【００７７】
［動作］
本実施形態では、Shamirの秘密分散法を用いる。そこで、事前にしきい値Kを固定（fix）しておく。さらに、有限体Fの相異なる元m[1], …, m[N]を固定する。
【００７８】
a[1], …, a[U] ∈ {0, 1} ⊂ Fを秘密データとし、φを関数とする。本実施形態では、φ(a[1], …, a[U])をマルチパーティ計算したい場合を考える。
【００７９】
この場合、以下の動作が行われる。
・登録装置１は、秘密データa[1], ..., a[U]を受け付けると、受け付けた秘密データa[1], ..., a[U]を記憶部１２に保持する。また、登録装置１のシェア生成部１３１は、u = 1, …, Uに対し、後述する「シェア生成」を行い、a[u]のシェアs[u, 1], …, s[u, N]を求める。次に、登録装置１の通信部１１は、生成されたシェアs[u, 1], …, s[u, N]を、それぞれサーバ装置２−１〜２−Ｎに送る。
・サーバ装置２−１〜２−Ｎの通信部２１−１〜２１−Ｎは、それぞれ、登録装置１からシェアs[u, 1], …, s[u, N]を受け取ると、記憶部２２−１〜２２−Ｎに格納する。シェア拡張部２３１−１〜２３１−Ｎは、それぞれ、マルチパーティ計算を開始するまでに「シェア拡張」を行ってs[u, 1], …, s[u, N]の拡張シェアを求め、求めた拡張シェアを記憶部２２−１〜２２−Ｎに保持する。
・サーバ装置２−１〜２−Ｎの計算部２３−１〜２３−Ｎは、関数φをORゲートとNOTゲートの組み合わせで表記し、u = 1, …, Uに対するa[u]の拡張シェアを入力として、ORゲートとNOTゲートを順にマルチパーティ計算していく。ORゲートに対するマルチパーティ計算は後述する「OR計算」の部分、NOTゲートに対するマルチパーティ計算は後述する「NOT計算」の部分で説明する。サーバ装置２−１〜２−Ｎは、最終的にφ(a[1], …, a[U])のシェアを得る。
・φ(a[1], …, a[U])の各ビットのシェアの計算が終了すると、サーバ装置２−１〜２−Ｎの通信部２１−１〜２１−Ｎは、計算したシェアを登録装置１に送出する。登録装置１の復元部１３２は、サーバ装置２−１〜２−Ｎから送出されたシェアに基づいて、後述する「復元計算」を行うことでφ(a[1], …, a[U])を復元する。
【００８０】
上記では、サーバ装置２−１〜２−Ｎに設けられたシェア拡張部２３１−１〜２３１−Ｎがシェア拡張を行う場合について説明した。ただし、登録装置１の側でシェア拡張を行ってもよい。この場合、登録装置１の通信部１１は、シェアs[u, 1], …, s[u, N]自身ではなく、これらのシェアをシェア拡張して得られた拡張シェアをサーバ装置２−１〜２−Ｎに送出する。
【００８１】
次に、シェア生成動作の詳細について説明する。本実施形態と後述する第２の実施形態との間で、シェア生成動作は共通である。
【００８２】
｛シェア生成｝
実施形態１、２では、秘密aは{0, 1}の元である場合を想定する。ただし、以下のシェア生成動作は秘密aがFの元であれば{0, 1}の元でなくとも正しく動作する。なお、後述する第３、第４の実施形態では、秘密aが{0, 1}の元とは限らない場合に対しても以下のシェア生成動作を用いる。
【００８３】
・登録装置１は、秘密a ∈ Fを入力として受け取る。
・シェア生成部１３１は乱数r[1], …, r[K - 1] ∈ Fをランダムに選び、i = 1, …, Nに対し、有限体F上の多項式f(X)を
f(X) = a + Σk = 1, …, K - 1r[k]Xk
により定義し、n = 1, …, Nに対し
s[n] = f(m[n])
を計算する。通信部１１は、計算されたシェアs[1], …, s[N]を、それぞれサーバ装置2-1, ..., 2-Nのシェアとして送信する。
・サーバ装置２−１〜２−Ｎは、それぞれ、受信したシェアs[1], …, s[N]を記憶部２２−１〜２２−Ｎに保持する。
【００８４】
本実施形態と後述する第２の実施形態との間では、「シェア拡張」、「OR計算」、「NOT計算」および「復元計算」の動作が相違する。以下では、本実施形態における「シェア拡張」、「OR計算」、「NOT計算」および「復元計算」の動作について説明する。
【００８５】
｛シェア拡張｝
・サーバ装置２−１〜２−Ｎのシェア拡張部２３１−１〜２３１−Ｎは、それぞれ、シェアs[1], …, s[N]を記憶部２２−１〜２２−Ｎから読み込む。
・l =1, …, λ、d = 1, …, Dに対し、シェア拡張部２３１−１〜２３１−Ｎは乱数生成ＭＰＣプロトコルを実行することで、有限体F上の一様乱数r[l, d]のシェアを生成する。実行結果として、シェア拡張部２３１−１〜２３１−Ｎはそれぞれr[l, d]のシェアρ[l, d, 1], …., ρ[l, d, N]を得る。
・n = 1, …, N, l = 1, …, λに対し、シェア拡張部２３１−ｎは
t[n, l] = s[n] + Σd = 1, …, Dρ[l, d, n]m[n]d
を計算する。
・n = 1, …, N に対し、シェア拡張部２３１−ｎは(t[n, 1], …, t[n, λ])を拡張シェアとして出力する。
【００８６】
｛OR計算｝
j = 1, …, Jに対し、サーバ装置２−１〜２−Ｎがa[j]の拡張シェア(t[j, 1, 1], …, t[j, 1, λ]) ∈ Fλ, …, (t[j, N, 1],…,t[j, N, λ]) ∈ Fλをそれぞれ記憶部２２−１〜２２−Ｎに保管しているとき、サーバ装置２−１〜２−ＮのOR計算部２３２−１〜２３２−Ｎは、次のようにしてb = a[1] OR … OR a[J]のシェアを計算する。
・j = 1, …, Jに対し、OR計算部２３２−１〜２３２−Ｎは、それぞれ、拡張シェア(t[j, 1, 1], …, t[j, 1, λ]) ∈ Fλ, …, (t[j, N, 1], …, t[j, N, λ]) ∈Fλを記憶部２２−１〜２２−Ｎから読み込む。
・OR計算部２３２−１〜２３２−Ｎは、それぞれ、乱数生成ＭＰＣをJλ回実行する。その結果として、j = 1, …, J, l = 1, …, λに対して、OR計算部２３２−１〜２３２−Ｎは、それぞれ、有限体F上の乱数R[j, l]のシェアu[j, 1, l], …, u[j, N, l]を得る。
・n = 1, …, N, l = 1, …, λに対し、OR計算部２３２−ｎはv[n, l] = Σj = 1,…,Jt[j, n, l]u[j, n, l]∈Fを計算し、(v[n, 1], …, v[n, λ])をbの拡張シェアとして記憶部２２−ｎに保管する。
【００８７】
｛NOT計算｝
サーバ装置２−１〜２−Ｎが、それぞれ、aの拡張シェア(t[1, 1], …, t[1, λ]) ∈ Fλ, …,  (t[N, 1], …, t[N, λ]) ∈ Fλを記憶部２２−１〜２２−Ｎに保管しているとき、サーバ装置２−１〜２−ＮのNOT計算部２３３−１〜２３３−Ｎは、次のようにしてb = NOT aのシェアを計算する。
・NOT計算部２３３−１〜２３３−Ｎは、それぞれ、秘密aの拡張シェア(t[1, 1], …, t[1, λ]) ∈ Fλ, …,  (t[N, 1], …, t[N, λ]) ∈ Fλを記憶部２２−１〜２２−Ｎから読み込む。拡張シェアの定義より、(t[n, l]) n = 1, …, Nは何らかの元c[n] ∈ Fの秘密分散になっている。
・n = 1, …, N, l = 1, …, λに対し、NOT計算部２３３−ｎがt[n, l] ∈ Fを入力として用いて
d[l] = 1 - c[l]q - 1
のシェアを得るマルチパーティ計算を実行する。NOT計算部２３３−ｎは、かかるマルチパーティ計算を、有限体F上の和のマルチパーティ計算と積のマルチパーティ計算を組み合わせることで実行することができる。ここで、qは有限体Fの位数である。実行結果として、NOT計算部２３３−１〜２３３−Ｎは、それぞれd[l]のシェアδ[1, l], …, δ[N, l]を得る。
・n = 1, …, Nに対し、NOT計算部２３３−ｎがδ[n, 1], …, δ[n, λ] ∈ Fを入力として用いて、
e = d[1] … d[λ]
のシェアを得るマルチパーティ計算を実行する。NOT計算部２３３−１〜２３３−Ｎは、実行結果として、それぞれeのシェアε[1], …, ε[N]を得る。
・n = 1, …, Nに対し、シェア拡張部２３１−ｎはε[n]を入力としてシェア拡張を実行する。実行結果として得られた拡張シェアを記憶部２２−ｎに書き込む。
【００８８】
｛復元計算｝
・登録装置１の復元部１３２は、v個（v ≧ K）の拡張シェア(t[i_1, 1], …, t[i_1, λ]) ∈ Fλ, …, (t[i_v, 1],…,t[i_v, λ]) ∈ Fλを入力として受け取る。
・復元部１３２は、l = 1, …, λに対して、ShamirReconst(t[i_1, l], …, t[i_v, l], K, N, F)を実行し、出力a[l]を得る。
・復元部１３２は、a[1] = …. = a[λ] = 0である場合0を出力し、それ以外の場合1を出力する。
【００８９】
本実施形態の秘密計算システム１０によると、有限体Fの位数q自身を小さく保ったままOR計算を間違える確率を小さくすることができる。したがって、本実施形態によると、ラウンド効率を悪化させることなく、マルチパーティ計算を高い確率で正しく実行することができる。
【００９０】
＜実施形態２＞
次に、第２の実施形態に係る秘密計算システムについて、図面を参照して説明する。
【００９１】
［構成］
図２は、本実施形態の秘密計算システム１０の構成を例示するブロック図である。本実施形態の秘密計算システム１０の構成は、第１の実施形態の秘密計算システムの構成と同様であるため、説明を省略する。
【００９２】
本実施形態では、有限体Fとして位数qがサーバ装置の台数N以上のものを用いる。また、有限体Fの相異なる元m[1], …, m[N]を固定する。
【００９３】
さらに、本実施形態では、Lを有限体Fの拡大体であって、拡大次数がセキュリティ・パラメータλ以上であるものとする。拡大体Lの定義より、拡大体LをF上λ次元ベクトル空間とみなすことができる。そこで、F上λ次元ベクトル空間としての拡大体Lの基底E[1], …, E[λ] ∈ Lを固定する。
【００９４】
［動作］
次に、本実施形態の秘密計算システムの動作について説明する。なお、本実施形態におけるシェア生成動作は、第１の実施形態におけるシェア生成動作と同様であるため、説明を省略する。以下では、本実施形態における「シェア拡張」、「OR計算」、「NOT計算」および「復元計算」の動作について説明する。
【００９５】
｛シェア拡張｝
・n = 1, …, N, l = 1, …, λに対し、第１の実施形態と同様に、サーバ装置２−ｎのシェア拡張部２３１−１は
t[n, l] = s[n] + Σd = 1, …, Dρ[l, d, n]m[n]d
を計算する。
・本実施形態では、シェア拡張部２３１−ｎ（n = 1, …, N）は、
T[n] = Σl = 1, …, λt[n, l]E[l]
を計算し、計算したT[n]を拡張シェアとして出力する。
【００９６】
｛OR計算｝
j = 1, …, Jに対し、サーバ装置２−１〜２−Ｎが、それぞれa[j]の拡張シェアT[j, 1] ∈ L, …,  T[j, N] ∈ Lを記憶部２２−１〜２２−Ｎに保管しているとき、サーバ装置２−１〜２−ＮのOR計算部２３２−１〜２３２−Ｎは、次のようにしてb = a[1] OR … OR a[J]のシェアを計算する。
・j = 1, …, Jに対し、OR計算部２３２−１〜２３２−Ｎは、それぞれ、拡張シェアT[j, 1] ∈ L, …, T[j, N] ∈ Lを記憶部２２−１〜２２−Ｎから読み込む。
・OR計算部２３２−１〜２３２−Ｎは、それぞれ、乱数生成ＭＰＣをJ回実行する。その結果として、j = 1, …, Jに対して、OR計算部２３２−１〜２３２−Ｎは、それぞれ、拡大体L上の乱数R[j]のシェアu[j, 1], …, u[j, N] ∈ Lを得る。
・n = 1, …, Nに対し、OR計算部２３２−ｎはv[n] = Σj = 1, …, JT[j, n]u[j, n] ∈ Lを計算し、v[n]をbの拡張シェアとして記憶部２２−ｎに保管する。
【００９７】
｛NOT計算｝
サーバ装置２−１〜２−Ｎが、それぞれaの拡張シェアT[1] ∈ L, …, T[N] ∈ Lを記憶部２２−１〜２２−Ｎに保管しているとき、サーバ装置２−１〜２−ＮのNOT計算部２３３−１〜２３３−Ｎは、次のようにしてb = NOT aのシェアを計算する。
・NOT計算部２３３−１〜２３３−Ｎは、それぞれ、秘密aの拡張シェアT[1] ∈ L, …, T[N] ∈ Lを記憶部２２−１〜２２−Ｎから読み込む。拡張シェアの定義より、T[1], …, T[N]はaを秘密分散したシェアである。
・n = 1, …, Nに対し、NOT計算部２３３−ｎはT[n]を
T[n] = Σl = 1, …, λt[n, l]E[l]      (t[n, l]∈F)
と成分表示し、y = 1, …, λに対し、
δ[n, y] = Σl = 1, …, λt[n, l]E[l]^{qu}
を計算する。ここで、qは有限体Fの位数である。拡張シェアの定義より、δ[n, y]は何らかの元d[y]を秘密分散したシェアである。
・n=1, …, Nに対し、NOT計算部２３３−ｎがδ[n, 1], …, δ[n, λ] ∈ Lを入力として用いて、
e = 1 - (d[1] … d[λ])q - 1
のシェアを得るマルチパーティ計算を実行する。NOT計算部２３３−１〜２３３−Ｎは、実行結果として、それぞれeのシェアε[1], …, ε[N]を得る。
【００９８】
｛復元計算｝
・登録装置１の復元部１３２は、v個（v ≧ K）の拡張シェアT[i_1], …, T[i_v]を入力として受け取る。
・復元部１３２は、u = 1, …, vに対して、T[i_u]をT[i_u] = Σl = 1, …, λt[i_u, l]E[l]と成分表示する。
・復元部１３２は、l = 1, …, λに対して、ShamirReconst(t[i_1, l], …, t[i_v, l], K, N, F)を実行して出力a[l]を得る。
・復元部１３２は、a[1] = …. = a[λ] = 0である場合0を出力し、それ以外の場合1を出力する。
【００９９】
本実施形態の秘密計算システム１０によると、有限体Fの位数qを小さく保ったままOR計算を間違える確率を小さくすることができる。したがって、本実施形態によると、ラウンド効率を悪化させることなく、マルチパーティ計算を高い確率で正しく実行することができる。また、この計算の際に、NOT計算の効率の低下を防ぐことも可能となる。
【０１００】
＜実施形態３＞
次に、第３の実施形態に係る秘密計算システムについて、図面を参照して説明する。本実施形態の秘密計算システムは、第１の実施形態に係る秘密計算システムを文字列検索（例えば、文字列の部分一致検索）に適用したものである。
【０１０１】
以下では、Nをサーバ装置の台数とする。また、本実施形態において、文字列とは「ワード」と呼ばれるデータを有限個並べたものを指し、各ワードは0以上W未満の整数を指すものとする。さらに、第１の実施形態における有限体Fとして、位数qがW以上のものをとる。
【０１０２】
［構成］
図３は、本実施形態に係る秘密計算システム２０の構成を例示するブロック図である。図３を参照すると、秘密計算システム２０は、登録装置３、検索装置４、および、サーバ装置２−１〜２−Ｎを備えている。登録装置１と検索装置３は、別個の装置であっても同一の装置であってもよい。同様に、登録装置１および検索装置３の機能を、サーバ装置２−１〜２−Ｎのいずれかが備えていてもよい。
【０１０３】
本実施形態では、サーバ装置２−１〜２−Ｎに対して登録装置３が文字列を登録する。文字列を登録する登録装置３は、文字列毎に異なってもよいし同一でもよい。図３では、一例として、すべての文字列を同一の装置が登録する状況を想定し、t番目の文字列atを登録する状況を示す。
【０１０４】
また、本実施形態では、サーバ装置２−１〜２−Ｎに保管された文字列を検索装置４が検索する。検索装置４は、検索文字列b毎に異なってもよいし同一でもよい。図３では、一例として、１台の検索装置４がすべての検索を行う状況を想定する。
【０１０５】
登録装置３は、通信部３１、記憶部３２、および、計算部３３を備えている。また、計算部３３は、登録文字列のシェアを生成するシェア生成部３３１を備えている。
【０１０６】
検索装置４は、通信部４１、記憶部４２、および、計算部４３を備えている。また、計算部４３は、検索文字列のシェアを生成するシェア生成部４３１と、復元部４３２を備えている。
【０１０７】
サーバ装置２−ｎ（n = 1, …, N）は、通信部２１−ｎ、記憶部２２−ｎ、および、計算部２３−ｎを備えている。また、計算部２３−ｎは、シェア拡張部２３１−ｎ、OR計算部２３２−ｎ、および、NOT計算部２３３−ｎを備えている。
【０１０８】
［動作］
次に、本実施形態の秘密検索システム２０の動作について説明する。
【０１０９】
｛登録手順｝
ここで、a = a[1] … a[U]を登録したい文字列とする。登録装置３のシェア生成部３３１は、各u = 1, …, Uに対して、a[u]のシェアs[u, 1], …, s[u, N]を第１の実施形態のシェア生成と同様の手順で計算する。登録装置３の通信部３１は、生成されたシェアs[u, 1], …, s[u, N]を、それぞれサーバ装置２−１〜２−Ｎに送る。サーバ装置２−１〜２−Ｎは、それぞれ、受信したシェアs[u, 1], …, s[u, N]を記憶部２２−１〜２２−Ｎに保管する。サーバ装置２−ｎのシェア拡張部２３１−ｎ（n = 1, …, N）は、任意のタイミングでシェアs[u, n]に対する拡大シェアを計算しておく。
【０１１０】
｛検索手順｝
ここでは、b = b[1] … b[V]を検索装置４がクエリする文字列とする。本実施形態では、サーバ装置２−１〜２−Ｎにシェアが登録されている文字列a = a[1] … a[U]のうちの、bがaの部分文字列となっているものを見つけることを目標とする。
・検索装置４のシェア生成部４３１は、v = 1, …, Vに対して、b[v]のシェアを計算する。検索装置４の通信部４１は、計算されたb[v]のシェアをサーバ装置２−１、…、サーバ装置２−Ｎに送る。サーバ装置２−ｎのシェア拡張部２３１−ｎ（n = 1, …, N）は、b[v]のシェアに対する拡大シェアを計算する。
・サーバ装置２−１〜２−Ｎの計算部２３−１〜２３−Ｎは、シェアが登録されている各文字列a = a[1] ... a[U]に対し、u = 1, …, U - Vに対するa[u]の拡大シェアとv = 1, …, Vに対するb[v]の拡大シェアを入力として減法と乗法のマルチパーティ計算を行うことで
c[u, v] = (a[u] - b[u + v])q
の拡大シェアを計算する。ここで、qは有限体Fの位数である。
・サーバ装置２−１〜２−ＮのNOT計算部２３３−１〜２３３−Ｎは、u = 1, …, U - V, v = 1, …, Vに対して、第１の実施形態のNOT計算を用いることで、c[u, v]の拡大シェアから
d[u, v] = NOT c[u, v]
の拡大シェアを計算する。
・サーバ装置２−１〜２−ＮのOR計算部２３２−１〜２３２−Ｎは、u = 1, …, U - Vに対して、第１の実施形態のOR計算を用いることで、d[u, v]の拡大シェアから
e[u] = d[u, 1] OR … OR d[u, V]
の拡大シェアを計算する。
・サーバ装置２−１〜２−ＮのNOT計算部２３３−１〜２３３−Ｎは、u = 1, …, U - V,に対して、第１の実施形態のNOT計算を用いることで、e[u]の拡大シェアから
f[u] = NOT e[u]
の拡大シェアを計算する。
・サーバ装置２−１〜２−ＮのOR計算部２３２−１〜２３２−Ｎは、第１の実施形態のOR計算を用いることで、f[u]の拡大シェアから
g = f[1] OR … OR f[V]
の拡大シェアを計算する。
・検索装置４の復元部４３２は、第１の実施形態の復元計算を用いることで、gのシェアからgを復元する。
・復元部４３２は、g = 1である場合、a = a[1] ... a[U]が検索にヒットしたものとみなして、a[1]のシェア、…、a[U]のシェアを検索装置に送信する。
・復元部４３２は、第１の実施形態の復元計算を用いることで、a[1]のシェア、…、a[U]のシェアからそれぞれa[1], …, a[U]を復元し、a = a[1] … a[U]とする。
【０１１１】
本実施形態の秘密計算システム２０によると、文字列検索をマルチパーティ計算に基づいて行う場合において、ラウンド数を削減することが可能となり、高速な文字列検索が実現される。
【０１１２】
＜実施形態４＞
次に、第４の実施形態に係る秘密計算システムについて、説明する。本実施形態の秘密計算システムの構成は、第３の実施形態に係る秘密計算システムの構成（図３）と同様である。
【０１１３】
ただし、本実施形態では、第３の実施形態において第１の実施形態１に係る「OR計算」、「NOT計算」および「復元計算」を用いる代わりに、第２の実施形態に係る「OR計算」、「NOT計算」および「復元計算」を用いる点で、第３の実施形態と相違する。
【０１１４】
本実施形態の秘密計算システム２０によると、第３の実施形態に係る秘密計算システムと同様の効果がもたらされる。すなわち、本実施形態によると、文字列検索をマルチパーティ計算に基づいて行う場合において、ラウンド数を削減することが可能となり、高速な文字列検索が実現される。
【０１１５】
なお、本発明において、下記の形態が可能である。
［形態１］
上記第１の態様に係る秘密計算システムのとおりである。
［形態２］
前記シェア拡張部は、前記シェアを秘密分散して生成された複数のシェアを成分とする配列を前記拡張シェアとして生成し、
前記OR計算部は、前記拡張シェアの各成分に対して、前記有限体上の乱数のシェアを乗じて足し合わせることで、前記OR演算を実行し、
前記NOT計算部は、前記拡張シェアの各成分がシェアする値を前記有限体の位数から1を引いた値でべき乗したものを1から差し引いた値の積をマルチパーティ計算することで、前記NOT演算を実行する、
形態１に記載の秘密計算システム。
［形態３］
前記シェアは、Shamirの秘密分散法に基づく前記秘密データの前記有限体上のシェアであり、
前記シェア拡張部は、前記シェアに対して、Shamirの秘密分散法による0の前記有限体上のシェアを加えることで、前記拡張シェアを生成する、
形態２に記載の秘密計算システム。
［形態４］
前記シェア拡張部は、前記シェアを秘密分散して生成された複数のシェアを前記有限体の拡大体上の元として表したものを、前記拡張シェアとして生成し、
前記OR計算部は、OR演算の対象となる拡張シェアに対して、前記拡大体上の乱数のシェアを乗じて足し合わせることで、前記OR演算を実行し、
前記NOT計算部は、NOT演算の対象となる拡張シェアを前記拡大体の基底で成分表示し、各成分に対応する基底を前記有限体の位数のべき乗でべき乗したものを各成分に乗じたものの和を求め、求めた和がシェアしている値の積を前記有限体の位数から1を引いた値でべき乗したものを1から減じた値をマルチパーティ計算することで、前記NOT演算を実行する、
形態１に記載の秘密計算システム。
［形態５］
前記シェアは、Shamirの秘密分散法に基づく前記秘密データの前記有限体上のシェアであり、
前記シェア拡張部は、前記シェアに対して、Shamirの秘密分散法による0の前記拡大体上のシェアを加えることで、前記拡張シェアを生成する、
形態４に記載の秘密計算システム。
［形態６］
前記複数のサーバ装置は、登録対象文字列の各ワードを秘密分散して生成されたシェアと、検索装置から受け付けた検索対象文字列の各ワードを秘密分散して生成されたシェアを前記記憶部に保持し、
前記シェア拡張部、前記OR計算部、および、前記NOT計算部を用いて、前記登録文字列の前記各ワードと前記検索文字列の前記各ワードの差のべき乗のシェアを、前記登録文字列の前記各ワードの前記シェアと前記検索文字列の前記各ワードの前記シェアとを用いてマルチパーティ計算し、前記べき乗のORのシェアを前記べき乗のシェアを用いてマルチパーティ計算し、前記ORされた値のNOTを前記ORされた値のシェアを用いてマルチパーティ計算し、前記NOTされた値のORを前記NOTされた値のシェアを用いてマルチパーティ計算し、
前記検索装置は、前記計算された前記NOTされた値のORに基づいて、検索対象文字列が登録対象文字列に部分一致したか否かを判定する、
形態１ないし５のいずれか一に記載の秘密計算システム。
［形態７］
形態１ないし６のいずれか一に記載の秘密計算システムに含まれる前記複数のサーバ装置のうちの一のサーバ装置。
［形態８］
上記第３の態様に係る秘密計算方法のとおりである。
［形態９］
前記一のサーバ装置は、前記シェアを秘密分散して生成された複数のシェアを成分とする配列を前記拡張シェアとして生成し、
前記拡張シェアの各成分に対して、前記有限体上の乱数のシェアを乗じて足し合わせることで、前記OR演算を実行し、
前記拡張シェアの各成分がシェアする値を前記有限体の位数から1を引いた値でべき乗したものを1から差し引いた値の積をマルチパーティ計算することで、前記NOT演算を実行する、
形態８に記載の秘密計算方法。
［形態１０］
前記シェアは、Shamirの秘密分散法に基づく前記秘密データの前記有限体上のシェアであり、
前記一のサーバ装置は、前記シェアに対して、Shamirの秘密分散法による0の前記有限体上のシェアを加えることで前記拡張シェアを生成する、
形態９に記載の秘密計算方法。
［形態１１］
前記一のサーバ装置は、前記シェアを秘密分散して生成された複数のシェアを前記有限体の拡大体上の元として表したものを、前記拡張シェアとして生成し、
OR演算の対象となる拡張シェアに対して、前記拡大体上の乱数のシェアを乗じて足し合わせることで、前記OR演算を実行し、
NOT演算の対象となる拡張シェアを前記拡大体の基底で成分表示し、各成分に対応する基底を前記有限体の位数のべき乗でべき乗したものを各成分に乗じたものの和を求め、求めた和がシェアしている値の積を前記有限体の位数から1を引いた値でべき乗したものを1から減じた値をマルチパーティ計算することで、前記NOT演算を実行する、
形態８に記載の秘密計算方法。
［形態１２］
前記シェアは、Shamirの秘密分散法に基づく前記秘密データの前記有限体上のシェアであり、
前記一のサーバ装置は、前記シェアに対して、Shamirの秘密分散法による0の前記拡大体上のシェアを加えることで、前記拡張シェアを生成する、
形態１１に記載の秘密計算方法。
［形態１３］
上記第４の態様に係るプログラムのとおりである。
［形態１４］
前記シェアを秘密分散して生成された複数のシェアを成分とする配列を前記拡張シェアとして生成する処理と、
前記拡張シェアの各成分に対して、前記有限体上の乱数のシェアを乗じて足し合わせることで、前記OR演算を実行する処理と、
前記拡張シェアの各成分がシェアする値を前記有限体の位数から1を引いた値でべき乗したものを1から差し引いた値の積をマルチパーティ計算することで、前記NOT演算を実行する処理と、を前記一のコンピュータに実行させる、
形態１３に記載のプログラム。
［形態１５］
前記シェアは、Shamirの秘密分散法に基づく前記秘密データの前記有限体上のシェアであり、
前記シェアに対して、Shamirの秘密分散法による0の前記有限体上のシェアを加えることで、前記拡張シェアを生成する処理を、前記一のコンピュータに実行させる、
形態１４に記載のプログラム。
［形態１６］
前記シェアを秘密分散して生成された複数のシェアを前記有限体の拡大体上の元として表したものを、前記拡張シェアとして生成する処理と、
OR演算の対象となる拡張シェアに対して、前記拡大体上の乱数のシェアを乗じて足し合わせることで、前記OR演算を実行する処理と、
NOT演算の対象となる拡張シェアを前記拡大体の基底で成分表示し、各成分に対応する基底を前記有限体の位数のべき乗でべき乗したものを各成分に乗じたものの和を求め、求めた和がシェアしている値の積を前記有限体の位数から1を引いた値でべき乗したものを1から減じた値をマルチパーティ計算することで、前記NOT演算を実行する処理と、を前記一のコンピュータに実行させる、
形態１３に記載のプログラム。
［形態１７］
前記シェアは、Shamirの秘密分散法に基づく前記秘密データの前記有限体上のシェアであり、
前記シェアに対して、Shamirの秘密分散法による0の前記拡大体上のシェアを加えることで、前記拡張シェアを生成する処理を、前記一のコンピュータに実行させる、
形態１６に記載のプログラム。
【０１１６】
なお、上記特許文献および非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０１１７】
１、３    登録装置
２−１〜２−Ｎ    サーバ装置
４    検索装置
１０、２０    秘密計算システム
１１、２１−１〜２１−Ｎ、３１、４１    通信部
１２、２２−１〜２２−Ｎ、３２、４２    記憶部
１３、２３−１〜２３−Ｎ、３３、４３    計算部
１３１、３３１、４３１    シェア生成部
１３２、４３２    復元部
２３１−１〜２３１−Ｎ    シェア拡張部
２３２−１〜２３２−Ｎ    OR計算部
２３３−１〜２３３−Ｎ    NOT計算部
【図１】
2016159357.tif 000003
【図２】
2016159357.tif 000004
【図３】
2016159357.tif 000005
【国際調査報告】
2016159357.tif 000006
2016159357.tif 000007
2016159357.tif 000008
2016159357.tif 000009