(57)【特許請求の範囲】
【請求項１】
ユーザ機器から要求された検索データを用いてサーバ機器にある被検索データを検索する場合に両者が同一のデータを保有するかを検証する保持数検証システムであって、
前記サーバ機器は、
前記被検索データを検索するための公開パラメータを生成するサーバ生成部と、
生成された前記公開パラメータを前記ユーザ機器に送信するサーバ通信部と、を備え、
前記ユーザ機器は、
前記サーバ機器から受信した前記公開パラメータに基づいて、前記検索データについての前記公開パラメータに対応する秘密パラメータを生成するユーザ生成部と、
生成された前記秘密パラメータに基づいて前記検索データを暗号化するユーザ暗号化部と、
を備えることを特徴とする保持数検証システム。
【請求項２】
前記サーバ機器は、前記被検証データについての秘密鍵を生成する鍵生成部と、前記秘密鍵に基づいて、前記暗号化された検索データのそれぞれを再暗号化するサーバ暗号化部と、を備え、
前記ユーザ機器は、前記暗号化された検索データを前記サーバ機器に送信し、または再暗号化された検索データを前記サーバ機器から受信するユーザ通信部と、
を備えることを特徴とする請求項１に記載の保持数検証システム。
【請求項３】
前記サーバ機器は、前記鍵生成部が生成した秘密鍵に基づいて、前記公開パラメータを生成する、
ことを特徴とする請求項２に記載の保持数検証システム。
【請求項４】
前記ユーザ機器は、前記再暗号化された検索データと前記秘密パラメータとに基づいて、前記検索データの特徴値を抽出するユーザ処理部をさらに備える、
ことを特徴とする請求項３に記載の保持数検証システム。
【請求項５】
前記サーバ機器は、前記被検索データを圧縮し、その特徴値を抽出した特徴値郡群を前記ユーザ機器に送信するサーバ処理部と、を備え、
前記ユーザ機器は、前記ユーザ通信部が前記特徴値郡を受信し、前記ユーザ処理部は、受信された前記特徴値群と、前記検索データの特徴値とに基づいて、同一の値を有する前記被検索データと前記検索データとの数を判定する、
ことを特徴とする請求項４に記載の保持数検証システム。
【請求項６】
前記ユーザ機器は、前記ユーザ処理部が前記被検索データの検索用キーワードを分割し、分割されたデータを前記検索データに変換し、
前記サーバ機器は、前記サーバ処理部が前記被検索データを検索するための索引を分割し、分割されたデータを前記被検索データに変換する、
ことを特徴とする請求項５に記載の保持数検証システム。
【請求項７】
前記ユーザ機器は、前記ユーザ生成部が、前記検索データによって前記被検索データを検索する前に、前記公開パラメータから取り出したデータと、前記検証データの数と前記検証データの数によって生成された乱数とに基づいて、前記データと前記乱数とのべき乗剰余乗算により前記秘密パラメータを生成する、
ことを特徴とする請求項１に記載の保持数検証システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クライアントがサーバに情報を開示せずに、サーバが保持するクライアントと同一のデータの数を検証する、保持数検証システムに関する。
【背景技術】
【０００２】
クラウド型システムに代表されるように、情報システムが管理するデータ量は増加の一途を辿っている。これらのデータを活用する研究が進められる一方、同時に情報システムにおけるデータのプライバシを如何に保つか重要視されている。これを実現するため、データのプライバシを維持しながら、データを活用する研究が存在する。例えば、特許文献１や非特許文献１には、サーバ／クライアントモデルにおいて、クライアントが保有するデータと同じデータを、サーバが保有するかを確認する（同一のデータを検索する）暗号化方式が記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】公開番号PWO2012/077541, 吉野雅之, 佐藤尚宜, 長沼健。検索可能暗号処理システム。
【０００４】
【非特許文献１】Crytography ePring Archive  2011/141, Fast and Private Computation of Cardinality of Set Intersection and Union, Emiliano De Cristofaro, Paolo Gasti, and Gene Tsudik。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載された技術を用いる場合、サーバが同一のデータを保有するかをクライアントが確認するたび、サーバにもその結果(検索結果)が知られてしまう、というデータのプライバシに関する課題がある。一方、非特許文献１では、サーバにもその結果が知らせない方式が記載されているが、べき乗剰余乗算と呼ばれる処理の重い計算をクライアントが処理する必要がある。クライアントは携帯電話や小型ＰＣ等の計算能力の低い計算機でも処理できる必要があるため、計算効率の点で課題がある。以上を踏まえ、サーバにはクライアントが同一のデータを保有しているかを知らせずに、かつクライアントには過大な処理負荷を強いないことが、解決すべき課題である。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明にかかる保持数検証システムは、ユーザ機器から要求された検索データを用いてサーバ機器にある被検索データを検索する場合に両者が同一のデータを保有するかを検証する保持数検証システムであって、前記サーバ機器は、前記被検索データを検索するための公開パラメータを生成するサーバ生成部と、生成された前記公開パラメータを前記ユーザ機器に送信するサーバ通信部と、を備え、前記ユーザ機器は、前記サーバ機器から受信した前記公開パラメータに基づいて、前記検索データについての前記公開パラメータに対応する秘密パラメータを生成するユーザ生成部と、生成された前記秘密パラメータに基づいて前記検索データを暗号化するユーザ暗号化部と、を備えることを特徴とする。
【発明の効果】
【０００７】
本発明によれば、サーバには結果を知らせずに、サーバが保有する同一のデータの数を、クライアントが検証することが可能となる。
【図面の簡単な説明】
【０００８】
【図１】本実施形態に係る保持数検証システムの構成例を示す図である。
【図２】第一実施形態に係るユーザ機器の構成例を示す図である。
【図３】第一実施形態に係るサーバ機器の構成例を示す図である。
【図４】ユーザ機器とサーバ機器のハードウェア構成例を示す図である。
【図５】第一実施形態に係る公開パラメータの登録処理の手順を示すフローチャートである。
【図６Ａ】第一実施形態に係る秘密パラメータの生成処理の手順を示すフローチャートである。
【図６Ｂ】第一実施形態に係る秘密パラメータの構成を示す図である。
【図７】第一実施形態に係る同一データの保有数の証明処理の手順の前半部を示すフローチャートである。
【図８Ａ】第一実施形態に係る同一データの保有数の証明処理の手順の後半部を示すフローチャートである。
【図８Ｂ】第一実施形態に係る同一データの保有数の証明処理の手順の後半部を示すフローチャートである。
【図９Ａ】第一実施形態に係る通信データの構成を示す図である。
【図９Ｂ】第一実施形態に係る通信データの構成を示す図である。
【図１０Ａ】第一実施形態に係る検索キーワードから検索データの作成処理の手順を示す図である。
【図１０Ｂ】第一実施形態に係る索引から被検索データの作成処理の手順を示す図である。
【発明を実施するための形態】
【０００９】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。なお、実施形態において、同一の部材には原則として同一の符号を付け、繰り返しの説明は省略する。
【００１０】
《システム構成》
図１は、本実施形態に係る保持数検証システムＡの構成例を示す図である。図１の構成は、後記する第１実施形態に共通の構成である。保持数検証システムＡは、ユーザ機器200と、サーバ機器300とがネットワーク100を介して互いに接続された構成となっている。例えば、あるサービス提供形態では、ネットワーク100はインターネットを指し、サーバ機器300はクラウド事業者に設置され、ユーザ機器200は携帯電話やスマートフォンなどを指す。
《第一実施形態》
次に、図２から図１０を参照し、本発明に係る第一実施形態を説明する。
（ユーザ機器）
図２は、第一実施形態に係るユーザ機器200の構成例を示す機能概略図である。図示するように、ユーザ機器200は、データを処理する制御部210と、データを記憶する記憶部220と、情報を入力する入力部201と、情報を出力する出力部202と、外部装置とのデータの送受信を行う通信部203とを備える。
【００１１】
制御部210は、全体処理部211と、乱数生成部212と、基本演算部213と、圧縮関数部214を備える。
【００１２】
全体処理部211は、ユーザ機器200における各処理を統括制御したり、入力部201を介して、受け付けた情報を記憶部220に格納したり、サーバ機器300との情報の送受信を制御する。また、全体処理部211は、データを出力部202に表示する処理を行ったり、記憶部220に格納されているデータを読み込み、それぞれ、乱数生成部212に乱数データを生成させたり、基本演算部213にデータの演算処理を行わせたり、圧縮関数部214にデータを圧縮させたりし、通信データや、ユーザ機器200の検証データやデータ識別子を通信部203を介し、サーバ機器300（図１）へ送信する。
【００１３】
乱数生成部212は、秘密鍵などを用いて擬似乱数を生成する。このとき、秘密鍵のデータ値は、乱数生成部212によって、新しいデータ値に更新され、再び、全体処理部211により記憶部220に格納される。なお、乱数生成部212は、温度、時間、電力量などの物理現象や、乱数生成アルゴリズムを用いて乱数を生成・出力してもよい。また、乱数生成部212へビット長(512,1024,2048など)を入力することにより、任意のビット長の乱数が生成できる。
【００１４】
基本演算部213は、加算、減算、剰余乗算、比較演算などの基本的な算術演算に関する処理を行う。
【００１５】
圧縮関数部214は、任意のビット長のデータを、一定のビット長のデータに変換する処理を行う。標準的な暗号化ハッシュ関数の実装により圧縮関数部214を実現してもよい。
【００１６】
記憶部220には、検証データと、データ識別子と、秘密パラメータと、公開パラメータとが格納されている。検証データは、保持数の証明対象となるデータ（例えば、検索キーワード）である。データ識別子は、検証データを特定する情報（例えば、ＩＤ等の識別情報）を含むデータである。秘密パラメータは、検索データのそれぞれについて、ユーザ機器200が生成するデータである。公開パラメータは、サーバ機器300から送付された被検索データを検索するためのデータであり、秘密パラメータを生成するためのデータである。
【００１７】
（サーバ機器）
図３は、第一実施形態に係るサーバ機器300の構成例を示す機能概略図である。図示するように、サーバ機器300は、データを処理する制御部310と、データを記憶する記憶部320と、情報を入力する入力部301と、情報を出力する出力部302と、外部装置とのデータの送受信を行う通信部303とを備える。
【００１８】
制御部310は、全体処理部311と、乱数生成部312と、基本演算部313と、素数生成部314と、生成元生成部315と、チョップ関数部316を備える。
【００１９】
全体処理部311は、サーバ機器300における処理を統括制御したり、入力部301を介して、受け付けた情報を記憶部320に格納したり、ユーザ機器200との情報の送受信を制御する。また、全体処理部311は、データを出力部302に表示する処理を行ったり、記憶部320に格納されているデータを読み込み、通信部303を介して、ユーザ機器200へ送信する。
【００２０】
乱数生成部312は、秘密鍵などを用いて擬似乱数を生成する。このとき、秘密鍵のデータ値は、乱数生成部312によって、新しいデータ値に更新され、再び、全体処理部311により記憶部320に格納される。なお、乱数生成部312は、温度、時間、電力量などの物理現象や、乱数生成アルゴリズムを用いて乱数を生成・出力してもよい。また、乱数生成部212へビット長(512,1024,2048など)を入力することにより、任意のビット長の乱数が生成できる。
【００２１】
基本演算部313は、剰余乗算、加算、減算、比較演算などの基本的な算術演算に関する処理を行う。
【００２２】
素数生成部314には、乱数生成部312に擬似乱数の生成を依頼し、作成された擬似乱数が素数であるかを判定するテストを通し、素数を生成する。なお、素数生成部314は、標準的な素数生成アルゴリズムの実装により実現可能であり、素数生成部314にビット長(512,1024,2048など)を入力することにより、任意のビット長の素数を生成できる。
【００２３】
生成元生成部315は、群の生成元を生成する処理を行う。例えば、位数pの乗法群または加法群の生成元を生成する。
【００２４】
チョップ関数部316は、与えられたデータの特定のビット列を取り出す処理を行う。例えば、任意のデータから最下位ｔビットのデータが取りだせる。
【００２５】
記憶部320には、被検証データと、秘密鍵と、公開パラメータが格納されている。被検証データは、ユーザ機器200との保持数の証明対象となるデータ（例えば、検索キーワードによって検索対象となるデータ）である。秘密鍵は、サーバ機器300が生成したデータである。公開パラメータは、ユーザ機器200に送付するデータである。
【００２６】
図４は、ユーザ機器200とサーバ機器300であるコンピュータのハードウェア構成例を示す図である。コンピュータは、ＣＰＵ（Central Processing Unit）401と、メモリ402と、ＨＤＤ(Hard Disk Drive)等の外部記憶装置403と、ＣＤ（Compact Disk）等のデータを読み取るＣＤＤ（Compact Disk Drive）などの読書装置407と、キーボードやマウス等の入力装置406と、ディスプレイ等の出力装置405と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置404を有する一般的なＰＣ（Personal Computer）で実現される。
【００２７】
図２〜図３の各部210、211、212、213、214、310、311、312、313、314、315、316は、外部記憶装置403などに格納されているプログラムが、メモリに展開され、ＣＰＵによって実行されることにより具現化する。例えば、記憶部220、320は、ＣＰＵ401がメモリ402または外部記憶装置403を利用することにより実現可能であり、制御部210、310に含まれる各処理部は、外部記憶装置403に記憶されている所定のプログラムをメモリ402にロードしてＣＰＵ401で実行することで実現可能であり、入力部201、301は、ＣＰＵ401が入力装置406を利用することで実現可能であり、出力部202、302は、ＣＰＵ401が出力装置405を利用することで実現可能であり、通信部203、303は、ＣＰＵ401が通信装置404を利用することで実現可能である。
【００２８】
《フローチャート》
（公開パラメータの登録処理）
図５は、第一実施形態に係る秘密鍵と公開パラメータの生成処理の手順を示すフローチャートである。この処理は、同一データの保有数が証明できるよう、ユーザ機器200とサーバ機器300間で公開パラメータを共有する為に行われる。
【００２９】
まず、入力部301を介して、秘密鍵と公開パラメータを生成するための設定情報がサーバ機器300に入力される（S501）。そして、素数生成部314は、ランダムに素数ｐを生成し、公開パラメータとして記憶部320に格納する（S502）。次に、乱数生成部312は、0以上ｐ未満の整数ｋを一様ランダムに（即ち、乱数ｋを）生成し、秘密鍵として記憶部320に格納する(S502）。
【００３０】
次に、生成元生成部315は、素数ｐを位数とする乗法群Ｇｐの生成元ｇｐを生成し、秘密鍵として記憶部320に格納する（S503）。次に、基本演算部313は、ｇｐ-kを計算する（S504）。ここで、元ｇｐ―ｋとは法をｐとするｇｐの（−ｋ）乗のべき乗剰余乗算の値を持つ群Ｇｐの元を指す。そして、全体処理部211は、素数ｐ、生成元ｇｐ、元ｇｐ―ｋを通信データとして、ユーザ機器200へ通信部303を介して、送信する（S505）。
【００３１】
通信部203を介して、ユーザ機器200の全体処理部211は、通信データである素数ｐ、生成元ｇｐ、元ｇｐ―ｋを受信し（S506）、記憶部220へ公開パラメータとして格納する(S507)。また、全体処理部211は、無事に通信データを受信し記憶部220へ格納できたかを登録結果（例えば、その元を公開パラメータを記憶部220に格納できた旨、またはその元を公開パラメータを記憶部220に格納できなかった旨）としてまとめ、通信データとして、サーバ機器300へ通信部203を介して、送信する（S508）。
【００３２】
そして、通信部303を介して、サーバ機器300の全体処理部311は、通信データである登録結果を受信し（S509）、無事にユーザ機器200が通信データを登録できていれば終了し、登録できていなければS505へ戻り、再送信処理を行う。このように、図５に示した公開パラメータの登録処理を行うことによって、サーバ機器300が作成した公開パラメータがユーザ機器200に登録される。
【００３３】
（秘密パラメータの生成処理）
図６Ａ、６Ｂ中の図６Ａは、第一実施形態に係る、ユーザ機器200における秘密パラメータの生成処理の手順を示すフローチャートである。この処理は図７と図８Ａ、８Ｂで示す同一データの保有数の検証処理の前に実施する。一般に、この事前処理は実行時間に余裕があり、ユーザ機器200の計算能力が乏しくとも、処理の重いべき乗剰余乗算を(時間をかけてよいので)現実的に実行可能である。
【００３４】
まず、ユーザ機器200は、生成する秘密パラメータの数（すなわち、検証するデータの数（例えば、検索するキーワードの数）に対応する秘密パラメータの数）を指定する(S601)。以降は、生成する秘密パラメータの数はｎとする。乱数生成部212は、0以上ｐ未満のｎ個の整数（ｒ１、ｒ２、・・・ｒｉ、・・・ｒｎ）を一様ランダムに（即ち、乱数を）生成する（S602）。
【００３５】
基本演算部213は、ｇｐｒiとｇｐ-ｋｒiを計算する（S603）。ここで、ｇｐｒiとはｐを法とするｇｐのｒi乗のべき乗剰余乗算であり、ｇｐ-ｋｒiはｐを法とするｇｐ-ｋのｒi乗のべき乗剰余乗算である。
【００３６】
全体処理部211は、ｎ個の整数i（１、・・・ｎ）を識別子として作成し、ｇｐｒiとｇｐ-ｋｒiと共に、ｎ個の秘密パラメータ（i、ｇｐｒi、ｇｐ-ｋｒi）の組として保存する(S604)。図６Ｂは、秘密パラメータの構成を示している。
【００３７】
（同一データの保有数の証明処理の前半）
図７は、第一実施形態に係る同一データの保有数の証明処理の手順の前半を示すフローチャートである。図７と図８Ａ、８Ｂの手順を合わせた処理は、ユーザ機器200がサーバ機器300には結果を知らせずに、サーバ機器300が保有する同一のデータの数を、クライアントが検証する処理である。
【００３８】
まず、ユーザ機器200の入力部201を介し、検証データｄｉのデータ識別子iを作成する（S701）。以降は、ｍ個のデータ識別子ｉ（i=1、・・・ｍ）を選択したとする。ただし、ｍはｎ以下の正の整数とする。
【００３９】
全体処理部211は、秘密パラメータから、識別子iと元ｇｐｒiを読み込む。基本演算部213は、元ｇｐｒiｄｉを計算して暗号化する（S702）。ここで、元ｇｐｒiｄｉとは元ｇｐｒiと元ｄｉの剰余乗算による積の値を持つ群Ｇｐの元を指す。従って、S702の計算は（計算負荷の重いべき乗剰余乗算ではなく）計算負荷の軽い乗算ですむ。
【００４０】
全体処理部211は、識別子ｉと元ｇｐｒiｄｉを組（ｉ、ｇｐｒｉｄi）として、通信データに変換し、サーバ機器300へ通信部203を介して、送信する（S703）。図９Ａ、９Ｂ中の図９ＡにS703で送信される通信データの一部を示す。
【００４１】
通信部303を介して、サーバ機器300の全体処理部311は、通信データ（ｉ、ｇｐｒｉｄi）を受信し、記憶部320へ格納する（S704）。全体処理部311は、通信データから元ｇｐｒｉｄiを取り出す(S705）。基本演算部313は、元ｇｐｒｉｄiをｋ乗し、元（ｇｐｒｉｋｄiｋ）を得て再暗号化する（S706）。ここでｋ乗とは、ｐを法とする元ｇｐｒｉｄiのｋ乗のべき乗剰余乗算である。
【００４２】
そして、全体処理部311は、全ての組（ｉ、ｇｐｒｉｋｄiｋ）を通信データに変換し、ユーザ機器200へ通信部303を介して、送信する（S707）。図９ＢにS707で送信される通信データの一部を示す。そして、通信部203を介して、ユーザ機器200の全体処理部211は、通信データであるi=1、・・・ｍにおける（ｉ、ｇｐｒｉｋｄiｋ）を受信する（S708）。
【００４３】
全体処理部211は、通信データから識別子iと元ｇｐｒｉｋｄiｋを取り出し、秘密パラメータから、通信データと同一の識別子iと組である元ｇｐ-ｒiｋを取り出す(S709)。基本演算部213は、元ｇｐ-ｒiｋと元ｇｐｒｉｋｄiｋの積を計算し、元ｄiｋを得る(S710)。圧縮関数部214は、元ｄiｋの特徴値ｈ（ｄiｋ）を出力し、その旨をサーバ機器300に通知する(S711)。このように、図７に示した同一データの保有数の証明処理の手順の前半の処理では、サーバ機器300側では計算負荷の重いべき乗剰余乗算を行う一方、ユーザ機器200側ではそのようなべき乗剰余乗算を行わず、単なる剰余計算を行って検索キーワードのそれぞれについて特徴値を算出しているので、クライアントには過大な処理負荷を強いることがない。
【００４４】
図８Ａは、第一実施形態に係る同一データの保有数の証明処理の手順の後半を示すフローチャートである。サーバ機器300は、ユーザ機器200から特徴値ｈ（ｄiｋ）を出力した旨の通知を受けると、被検証データｃｉを選択する（S801）。以降は、Ｌ個の被検証データｃｉ（i=1、…  Ｌ）を選択したとする。
【００４５】
次に、基本演算部313は、元ｃｉkを計算する（S802）。ここで、元ｃｉkとは法をｐとする元ｃｉのｋ乗のべき乗剰余乗算の値を持つ群Ｇｐの元を指す。チョップ関数部316は、元ｃiｋの特徴値ｈ（ｃiｋ）を出力する(S803)。
【００４６】
チョップ関数部316は、特徴値ｈ（ｃiｋ）から最下位ｔビットｃｈ（ｈ（ｃiｋ））を抽出する(S804)。そして、全体処理部311は、ｃｈ（ｈ（ｃiｋ））を通信データに変換し、ユーザ機器200へ通信部303を介して、送信する（S805）。
【００４７】
通信部203を介して、ユーザ機器200の全体処理部211は、通信データであるｃｈ（ｈ（ｃiｋ））を受信する（S806）。圧縮関数部214は、特徴値ｈ（ｄiｋ）から最下位ｔビットｃｈ（ｈ（ｄiｋ））を抽出する(S807)。全体処理部211は、ｃｈ（ｈ（ｄiｋ））（i=1、…  ｍ）とｃｈ（ｈ（ｃiｋ））（i=1、…  Ｌ）を比較し、値が等しければ同一データとみなし、その数を同一データの保有数とみなす(S808)。このように、図８Ａに示した同一データの保有数の証明処理の手順の後半の処理が終了すると、検索対象となった被検証データのそれぞれについてべき乗剰余乗算を行って特徴値を算出し、算出した特徴値と図７で算出した検索キーワードのそれぞれについての特徴値とを比較して同一データの保有数を判定するので、サーバ機器300にはクライアントが同一のデータを保有しているかを知られることはない（保有している同一のデータを秘匿しつつ、その保有数のみが知られる）。また、検索時にユーザ側ではべき乗剰余乗算を行わないので、クライアントにおける計算処理を効率的に行うことができる。
【００４８】
S804とS809において、チョップ関数は最下位ｔビットを抽出したが、同一の箇所であれば、別の部分を抽出しても構わない。例えば、最上位ｔビットを抽出してもよく、またｔ箇所から１びっとずつランダムに抽出しても構わない。さらに、（通信量は増えてしまうが）S804とS809の処理を省き、特徴値ｈ（ｃiｋ）と特徴値ｈ（ｄiｋ）を比較するようにしても構わない。
【００４９】
図８Ａに示すフローチャートの方法では、検証データの数（Ｌ）に通信データが比例するため、Ｌが大きい場合には、通信データも同時に大きくなってしまう。そこで、図８Ａに示した方式に比べ、ユーザ機器200とサーバ機器300間の通信量を少なくする効果がある、別の手順を図８Ｂに示す。S801からS804まではその処理は図８Ａと同様であるため、説明を省く。
【００５０】
全体処理部311は、２ｔビットの特徴値群ｂを作成する。また、特徴値群ｂの各ビットを（ｂ１、・・・ｂ２ｔ）で表わし、全てのビットを０で初期化する(S805b)。全体処理部311は、ｃｈ（ｈ（ｃiｋ））番目の特徴値群ｂのビットを１に変換する(S806b)。
【００５１】
そして、全体処理部311は、特徴値群ｂを通信データに変換し、ユーザ機器200へ通信部303を介して、送信する（S807b）。通信部203を介して、ユーザ機器200の全体処理部211は、通信データである特徴値群ｂを受信する（S808b）。
【００５２】
全体処理部211は、特徴値ｈ（ｄiｋ）を読み込み、ｈ（ｄiｋ）番目の特徴値群ｂのビット値（０または１）を取り出す(S809b)。全体処理部211は、ｍ個の特徴値ｈ（ｄiｋ）に対し、S809の処理を繰り返し、そのビットの合計を、同一データの保有数とみなす(S810b)。なお、S804とS809同様、チョップ関数は同一の箇所であれば、別の部分を抽出してもよい。
【００５３】
このように、第一実施形態によれば、ユーザ機器200は、検証データと同一のデータを、サーバ機器300が何個持っているかを、確認できる。また、第一実施形態によれば、事前計算処理により、クライアントの計算処理を軽減し、効率的な検証を実現できる。
【００５４】
（第一実施形態の適用対象）
第一実施形態によれば、電子データを類似検索するサービスを提供する、サービス事業者に対し、ユーザが自身の情報を開示せずにサービスを利用できる。一般に、検索を高速化する為、予め検索対象の電子データに検索用の索引を付与しておく。この索引に対し、第一実施形態が適用可能である。例えば、図１０Ａ、１０Ｂ中の図１０Ａにユーザ側の処理フロー、図１０Ｂにサービス事業者側の処理フローの一部を抜粋する。サービス事業者は一般的な検索用の技術であるｎ−ｇｒａｍを用いて検索サービスを提供するものとする。図１０Ａは検索サービスを利用するにあたり、ユーザがユーザ機器に入力した検索用キーワードの一例（東京の文化）を示している。検索用キーワードはｎ文字（図１０Ａでは2文字）毎に分割され、検証データｄ１、ｄ２・・・に変換される。また、図１０Ｂは検索サービスを利用するにあたり、サーバ機器に用意された検索用の索引の一例（東京都の文化）を示している。検索用キーワード同様、索引もｎ文字（図１０(ｂ)では2文字）毎に分割され、被検証データｃ１、ｃ２・・・に変換される。以降、検証データと被検証データの同一数の検証は、第一実施形態の処理フローに従う。
【００５５】
ここでは、ｎ−ｇｒａｍを用いた検索サービスへの適用例を示したが、他の検索技術を用いた場合にも適用可能である。また、索引を用いずにデータを検索する場合も、データそのものを被検索対象データとみなすことにより、第一実施形態が適用可能である。
（第一実施形態の応用）
第一の実施形態では、乗法群Ｇｐを用いる例を示したが、乗算に代わり加算で代替できるため、乗法群Ｇｐの代わりに、加法群（楕円曲線上の加法群）を用いてもよい。また、他の数学的な性質を持つ環や体を用いてもよい。
【符号の説明】
【００５６】
１００：ネットワーク
２００：ユーザ機器
２０１：入力部
２０２：出力部
２０３：通信部
２１０：制御部
２１１：全体処理部
２１２：乱数生成部
２１３：基本演算部
２１４：圧縮関数部
２２０：記憶部
３００：サーバ機器
３０１：入力部
３０２：出力部
３０３：通信部
３１０：制御部
３１１：全体処理部
３１２：乱数生成部
３１３：基本演算部
３１４：素数生成部
３１５：生成元生成部
３１６：チョップ関数部
３２０：記憶部
４００：コンピュータ
４０１：ＣＰＵ(Central Processing Unit)
４０２：メモリ
４０３：外部記憶装置
４０４：通信装置
４０５：出力装置
４０６：入力装置
４０７：読書装置
４０８：記憶媒体
４０９：内部通信線
Ａ：保持数検証システム。
【図１】
0005976932.tif 000002
【図２】
0005976932.tif 000003
【図３】
0005976932.tif 000004
【図４】
0005976932.tif 000005
【図５】
0005976932.tif 000006
【図６Ａ】
0005976932.tif 000007
【図６Ｂ】
0005976932.tif 000008
【図７】
0005976932.tif 000009
【図８Ａ】
0005976932.tif 000010
【図８Ｂ】
0005976932.tif 000011
【図９Ａ】
0005976932.tif 000012
【図９Ｂ】
0005976932.tif 000013
【図１０Ａ】
0005976932.tif 000014
【図１０Ｂ】
0005976932.tif 000015