(57)【特許請求の範囲】
【請求項１】
複数のサービス提供装置と、
データ登録装置と、
データベースと、
複数のプロキシ装置と、
統合データ生成装置と、
統合データ記憶装置とを備え、
前記サービス提供装置は、
データを暗号化するためのサービスの公開鍵および該公開鍵に対応した秘密鍵を生成する鍵生成手段と、
前記サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成するプロキシ鍵生成手段とを含み、
前記データ登録装置は、前記サービスの公開鍵および所定のデータを入力として、暗号データを生成する暗号データ生成手段を含み、
前記データベースは、前記暗号データを記憶し、
前記プロキシ装置は、前記データベースに記憶された暗号データに対して、前記プロキシ鍵生成手段によって生成されたプロキシ鍵を入力として、暗号化部分統計データを生成する暗号化部分統計データ生成手段を含み、
前記統合データ生成装置は、前記暗号化部分統計データを各プロキシ装置から入力し、暗号化統計データを生成する暗号化統計データ生成手段を含み、
前記統合データ記憶装置は、前記暗号化統計データを記憶する
ことを特徴とする暗号化統計処理システム。
【請求項２】
プロキシ鍵生成手段は、各サービス提供装置がそれぞれの秘密鍵を入力とし、前記各サービス提供装置と互いに通信を行うことによって、前記各サービス提供装置の秘密鍵に対応するプロキシ鍵を生成する
請求項１記載の暗号化統計処理システム。
【請求項３】
サービス提供装置は、統合データ記憶装置に記憶された暗号化統計データと、各サービス提供装置の秘密鍵とを入力として、前記各サービス提供装置と互いに通信を行うことによって、前記暗号化統計データの復号を行い、統計情報を生成する統計情報生成手段を含む
請求項２記載の暗号化統計処理システム。
【請求項４】
プロキシ鍵生成手段は、
素数位数qを持つ群G，G_T、
e()をGの元2つを入力としてG_Tの群への写像であるペアリング関数、
gを群Gの生成元、
q,e,gおよびZ=e(g,g)をシステムパラメータとし、
暗号データを記憶するデータベースの数を１以上の整数N、a_iをサービスiの秘密鍵、y_i=g^{a_i}を公開鍵としたとき、前記サービスiに対応するプロキシ鍵rk_iとして、g^{a_1a_2…a_N/a_i}を含むプロキシ鍵を生成する
請求項１記載の暗号化統計処理システム。
【請求項５】
暗号データ生成手段は、メッセージをM、1以上q未満の乱数をrとしたとき、サービスiに対応する暗号データとして、(y_i^r,M・Z^r)を含む暗号データを生成し、
暗号化統計データ生成手段は、統計情報を計算する対象となる暗号データを生成するために使用された乱数の総和をRとし、gpk=g^{a_1a_2…a_N}、統計情報をSとしたとき、(e(gpk,g)^R,S・Z^R)を含む暗号化統計データを生成する
請求項４記載の暗号化統計処理システム。
【請求項６】
データを暗号化するためのサービスの公開鍵および該公開鍵に対応した秘密鍵を生成する鍵生成手段と、
前記サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成するプロキシ鍵生成手段と、
前記サービスの公開鍵および所定のデータを入力として、暗号データを生成する暗号データ生成手段と、
前記暗号データに対して、前記プロキシ鍵生成手段によって生成されたプロキシ鍵を入力として、暗号化部分統計データを生成する暗号化部分統計データ生成手段と、
前記暗号化部分統計データに基づいて、暗号化統計データを生成する暗号化統計データ生成手段とを備えた
ことを特徴とする暗号化統計処理装置。
【請求項７】
鍵生成プログラムに従って処理を実行するプロセッサが、データを暗号化するためのサービスの公開鍵および該公開鍵に対応した秘密鍵を生成し、
プロキシ鍵生成プログラムに従って処理を実行するプロセッサが、前記サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成し、
暗号化部分統計データ生成プログラムに従って処理を実行するプロセッサが、前記サービスの公開鍵および所定のデータを入力として生成されデータベースに記憶された暗号データを該データベースから読み出し、読み出した暗号データに対して、前記プロキシ鍵を入力として、暗号化部分統計データを生成し、
暗号化統計データ生成プログラムに従って処理を実行するプロセッサが、前記暗号化部分統計データに基づいて、暗号化統計データを生成し、統合データ記憶装置に記憶させる
ことを特徴とする暗号化統計処理方法。
【請求項８】
コンピュータに、
データを暗号化するためのサービスの公開鍵および該公開鍵に対応した秘密鍵を生成する鍵生成処理と、
前記サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成するプロキシ鍵生成処理と、
前記サービスの公開鍵および所定のデータを入力として、暗号データを生成し、データベースに記憶させる暗号データ生成処理と、
前記データベースに記憶された暗号データを読み出し、読み出した暗号データに対して、前記プロキシ鍵生成処理によって生成されたプロキシ鍵を入力として、暗号化部分統計データを生成する暗号化部分統計データ生成処理と、
前記暗号化部分統計データに基づいて、暗号化統計データを生成し、統合データ記憶装置に記憶させる暗号化統計データ生成処理とを
実行させるための暗号化統計処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化統計処理システム、暗号化統計処理装置、暗号化統計処理方法及び暗号化統計処理プログラムに関する。
【背景技術】
【０００２】
近年、クラウドサービスにおけるセキュリティの重要性が広く認識されている。例えば、クラウドネットワーク（以下、単にクラウドという）上のデータベースに準同型暗号を用いて暗号化されたデータを保存し、データベースに記憶された暗号データに対して暗号化したまま統計処理を行うことで処理結果の暗号データを生成し、必要な時に処理結果の暗号データを取り出し、復号するサービスが提案されている。【０００３】
これに関連する技術として、例えば非特許文献１には、準同型暗号方式が記載されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】一色寿幸、尾花賢、森岡澄夫、佐古和恵、「準同型性を有する暗号方式のFPGA実装について」、2011年暗号と情報セキュリティシンポジウム（SCIS2011）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
クラウドにおけるサービスにおいて、ユーザから提供された情報をクラウド上のデータベースに収集し、収集した情報から統計データを求め、統計データに基づくサービスを行うものがある。例えば、ユーザにお勧めの商品に関する情報を提供するリコメンデーションサービスなどが、これにあたる。【０００６】
このとき、ユーザから提供される情報には、ユーザの購買情報や属性（年齢、性別、職業、居住地域など）など、ユーザの個人情報を含むことが多い。【０００７】
一方、クラウド上のデータベースは、誰が、どこで、どのように管理しているか明確でないことが多く、ユーザがセキュリティに対する不安を抱いていると言われている。すなわち、ユーザはクラウド上のデータベースの管理者を信頼できないため、データベースで多用されているデータへのアクセス権限を利用した情報漏えい対策が意味をなさない。【０００８】
そこで、クラウド上のデータベースの管理者にもユーザの情報が分からないように、ユーザから提供される情報をサービス提供者のみが復号できるように暗号化し、その暗号データをクラウド上のデータベースに保管することが考えられる。しかし、一般的に暗号化してしまうと、復号せずに提供情報から統計データを求めることが困難であることが知られている。【０００９】
非特許文献１に記載の準同型暗号方式は、ある公開鍵を用いて暗号化された複数の暗号データに対して、秘密鍵を用いずに暗号化したまま平文に対して統計処理を行うことを可能とする暗号方式である。ところが、統計処理が可能となる暗号データは、すべて同じ公開鍵で暗号化されていなくてはならない。すなわち、統計処理を行いたい対象の暗号データが、異なる公開鍵で暗号化されている場合、暗号化したまま統計処理を行うことができない。【００１０】
統計処理を行いたい対象の暗号データが異なる公開鍵で暗号化されている場合、例えば統計処理を行いたい対象であるすべての暗号データを取り出し、復号し、統計処理を行うことが考えられる。しかしこの方法では、すべての暗号データをサービス提供者側にダウンロードしなくてはならず、利便性や通信コストの観点で望ましくない。また、クラウド環境では、サービス提供者側の計算資源が少ないことが想定されるため、統計処理に要する計算をなるべくクラウド側で行うことが望まれている。さらに、暗号化されている対象のデータを一度復号してしまうため、サービス提供者が利用する計算機からのデータの漏洩を防がなくてはならず、対応にコストがかかってしまう。【００１１】
そこで、本発明は、異なる公開鍵を用いて暗号化された暗号データに対して、暗号化したまま統計処理を行う暗号化統計処理システム、暗号化統計処理装置、暗号化統計処理方法および暗号化統計処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明による暗号化統計処理システムは、複数のサービス提供装置と、データ登録装置と、データベースと、複数のプロキシ装置と、統合データ生成装置と、統合データ記憶装置とを備え、サービス提供装置は、データを暗号化するためのサービスの公開鍵および公開鍵に対応した秘密鍵を生成する鍵生成手段と、サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成するプロキシ鍵生成手段とを含み、データ登録装置は、サービスの公開鍵および所定のデータを入力として、暗号データを生成する暗号データ生成手段を含み、データベースは、暗号データを記憶し、プロキシ装置は、データベースに記憶された暗号データに対して、プロキシ鍵生成手段によって生成されたプロキシ鍵を入力として、暗号化部分統計データを生成する暗号化部分統計データ生成手段を含み、統合データ生成装置は、暗号化部分統計データを各プロキシ装置から入力し、暗号化統計データを生成する暗号化統計データ生成手段を含み、統合データ記憶装置は、暗号化統計データを記憶することを特徴とする。【００１３】
本発明による暗号化統計処理装置は、データを暗号化するためのサービスの公開鍵および公開鍵に対応した秘密鍵を生成する鍵生成手段と、サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成するプロキシ鍵生成手段と、サービスの公開鍵および所定のデータを入力として、暗号データを生成する暗号データ生成手段と、暗号データに対して、プロキシ鍵生成手段によって生成されたプロキシ鍵を入力として、暗号化部分統計データを生成する暗号化部分統計データ生成手段と、暗号化部分統計データに基づいて、暗号化統計データを生成する暗号化統計データ生成手段とを備えたことを特徴とする。【００１４】
本発明による暗号化統計処理方法は、鍵生成プログラムに従って処理を実行するプロセッサが、データを暗号化するためのサービスの公開鍵および公開鍵に対応した秘密鍵を生成し、プロキシ鍵生成プログラムに従って処理を実行するプロセッサが、サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成し、暗号化部分統計データ生成プログラムに従って処理を実行するプロセッサが、サービスの公開鍵および所定のデータを入力として生成されデータベースに記憶された暗号データを該データベースから読み出し、読み出した暗号データに対して、プロキシ鍵を入力として、暗号化部分統計データを生成し、暗号化統計データ生成プログラムに従って処理を実行するプロセッサが、暗号化部分統計データに基づいて、暗号化統計データを生成し、統合データ記憶装置に記憶させることを特徴とする。
【００１５】
本発明による暗号化統計処理プログラムは、コンピュータに、データを暗号化するためのサービスの公開鍵および公開鍵に対応した秘密鍵を生成する鍵生成処理と、サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成するプロキシ鍵生成処理と、サービスの公開鍵および所定のデータを入力として、暗号データを生成し、データベースに記憶させる暗号データ生成処理と、前記データベースに記憶された暗号データを読み出し、読み出した暗号データに対して、プロキシ鍵生成処理によって生成されたプロキシ鍵を入力として、暗号化部分統計データを生成する暗号化部分統計データ生成処理と、暗号化部分統計データに基づいて、暗号化統計データを生成し、統合データ記憶装置に記憶させる暗号化統計データ生成処理とを実行させることを特徴とする。
【発明の効果】
【００１６】
本発明によれば、異なる公開鍵を用いて暗号化された暗号データに対して、暗号化したまま統計処理を行うことができる。
【図面の簡単な説明】
【００１７】
【図１】本発明による暗号化統計処理システムの構成の一例を示すブロック図である。
【図２】データ登録装置の構成例を示すブロック図である。
【図３】サービス提供装置の構成例を示すブロック図である。
【図４】プロキシ装置の構成例を示すブロック図である。
【図５】統合データ生成装置の構成例を示すブロック図である。
【図６】サービス提供者鍵生成処理の一例を示す流れ図である。
【図７】データ登録処理の一例を示す流れ図である。
【図８】プロキシ鍵生成処理の一例を示す流れ図である。
【図９】統計情報計算処理の一例を示す流れ図である。
【図１０】復号処理の一例を示す流れ図である。
【図１１】サービス提供者鍵生成処理の一例を示す流れ図である。
【図１２】データ登録処理の一例を示す流れ図である。
【図１３】プロキシ鍵生成処理の一例を示す流れ図である。
【図１４】統計情報計算処理の一例を示す流れ図である。
【図１５】復号処理の一例を示す流れ図である。
【図１６】暗号化統計処理システムの最小の構成例を示すブロック図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態について図面を参照して説明する。図１は、本発明による暗号化統計処理システムの構成の一例を示すブロック図である。図１に示すように、暗号化統計処理システムは、暗号データを登録するデータ登録装置10と、暗号データを記憶する１つ以上のデータベース20-1，20-2，…，20-Nと、１つ以上のサービス提供装置60-iと、１つ以上のプロキシ装置30-iと、統合データ生成装置40と、統合データ記憶装置50とを含む。また、各装置は、ＬＡＮやインターネット等の通信ネットワークを介して相互に接続されている。
【００１９】
データベース20-1，20-2，…，20-Nは、光ディスク装置や磁気ディスク装置等の記憶装置（図示せず）に記憶されている。なお、データベースごとに異なる記憶装置に記憶させるようにしてもよいし、複数のデータベースを１つの記憶装置に記憶させるようにしてもよい。以下、データがデータベースに記憶されているとの表現を用いるが、具体的には、記憶装置が記憶しているデータベースに含まれていることを意味する。
【００２０】
サービス提供装置60-iは、暗号データを生成するための公開鍵pk_iと、公開鍵pk_iに対応する秘密鍵sk_iとを生成する。また、サービス提供装置60-iは、データベース20-iに記憶されている暗号データから暗号化部分統計データを生成するためのプロキシ鍵を生成する。また、サービス提供装置60-iは、暗号化統計データを復号し、統計データを生成する。
【００２１】
ここで、プロキシ鍵とは、所定の公開鍵を用いて暗号化された暗号データを、その公開鍵とは異なる公開鍵に対応する秘密鍵を用いて復号できる暗号データに変換するための鍵である。
【００２２】
また、暗号化部分統計データとは、所定の公開鍵を用いて生成された暗号データの集合に対して、対応する平文の集合より導かれる統計データを、所定の公開鍵を用いて暗号化したデータである。
【００２３】
本実施形態では、複数のデータベースが存在していることを想定している。また、簡略化のために、データベースごとにそれぞれ異なる公開鍵を１つだけ用いて、データの暗号化を行っているものとしている。すなわち、データベース１には公開鍵１、データベース２には公開鍵２を用いて暗号化されたデータを記憶させている。
【００２４】
後述する例では、データベース１には、E(pk_1,M_1)からE(pk_1,M_n)が記憶されている。また、データベース２には、E(pk_2,M'_1)からE(pk_2,M'_n')が記憶されている。ここで、MをM_1,…，M_nから求められる統計データとする。例えば、M=(M_1+…+M_n)とすれば、MはM_1,…,M_nの総和である。そして、本実施形態で利用している準同型暗号をEとして用いると、暗号化したまま、E(pk_1,M)を計算することができる。本実施形態では、このE(pk_1,M)をデータベース１の暗号化部分統計データと呼ぶ。
【００２５】
プロキシ装置30-iは、データベース20-iに記憶されている暗号データとプロキシ鍵とを入力として、暗号化部分統計データを生成する。
【００２６】
統合データ生成装置40は、１つ以上の暗号化部分統計データを入力として、暗号化統計データを生成する。統合データ記憶装置50は、暗号化統計データを記憶する。暗号化統計データとは、暗号化部分統計データに基づいて統計処理を行った結果の暗号データである。
【００２７】
データ登録装置10は、具体的には、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。図２は、データ登録装置の構成例を示すブロック図である。図２に示すように、データ登録装置10は、暗号データ生成部10-1と、暗号データ登録要求部10-2とを含む。
【００２８】
暗号データ生成部10-1は、サービス提供装置60-iによって生成された公開鍵pk_iおよび登録したいデータMを入力とし、公開鍵pk_iを用いてMの暗号データを生成する機能を備えている。暗号データ生成部10-1は、具体的には、プログラムに従って処理を実行する情報処理装置のＣＰＵによって実現される。
【００２９】
暗号データ登録要求部10-2は、生成した暗号データをデータベース20-iに登録することを要求する機能を備えている。暗号データ生成部10-1は、具体的には、プログラムに従って処理を実行する情報処理装置のＣＰＵおよびネットワークインタフェース部によって実現される。
【００３０】
サービス提供装置60-iは、具体的には、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。図３は、サービス提供装置の構成例を示すブロック図である。図３に示すように、サービス提供装置60-iは、鍵生成部60-i-1と、統合用鍵生成部60-i-2と、プロキシ鍵生成部60-i-3と、部分復号部60-i-4とを含む。
【００３１】
鍵生成部60-i-1は、公開鍵pk_iおよびそれに対応する秘密鍵sk_iを生成する機能を備えている。鍵生成部60-i-1は、具体的には、プログラムに従って処理を実行する情報処理装置のＣＰＵによって実現される。
【００３２】
統合用鍵生成部60-i-2は、秘密鍵sk_iを入力として、他の１つ以上のサービス提供装置60-jと対話する（具体的には、相互に通信を行い処理を実行する。詳細については後述する）ことにより、プロキシ鍵rk_iを生成するための全体公開鍵gpkを生成する機能を備えている。統合用鍵生成部60-i-2は、具体的には、プログラムに従って処理を実行する情報処理装置のＣＰＵによって実現される。
【００３３】
プロキシ鍵生成部60-i-3は、全体公開鍵gpkおよび秘密鍵sk_iを入力として、公開鍵pk_iで暗号化された暗号データを暗号化部分統計データに変換するためのプロキシ鍵rk_iを生成する機能を備えている。プロキシ鍵生成部60-i-3は、具体的には、プログラムに従って処理を実行する情報処理装置のＣＰＵによって実現される。
【００３４】
部分復号部60-i-4は、暗号化統計データを部分的に復号する機能を備えている。部分復号部60-i-4は、具体的には、プログラムに従って処理を実行する情報処理装置のＣＰＵによって実現される。
【００３５】
プロキシ装置30-iは、具体的には、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。図４は、プロキシ装置の構成例を示すブロック図である。図４に示すように、プロキシ装置30-iは、プロキシ鍵rk_iと公開鍵pk_iで暗号化された暗号データとを受け取り、暗号化部分統計データを生成する暗号化データ変換部30-i-1を含む。暗号化データ変換部30-i-1は、具体的には、プログラムに従って処理を実行する情報処理装置のＣＰＵによって実現される。
【００３６】
統合データ生成装置40は、具体的には、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。図５は、統合データ生成装置の構成例を示すブロック図である。図５に示すように、統合データ生成装置40は、プロキシ装置30-1〜プロキシ装置30-Nより暗号化部分統計データをそれぞれ受け取り、暗号化統計データを生成する統計処理部40-1を含む。統計処理部40-1は、具体的には、プログラムに従って処理を実行する情報処理装置のＣＰＵによって実現される。
【００３７】
本実施形態では、暗号化統計処理システムは、複数の装置によって構成されているが、これに限らず、各装置の機能を備えた１台の情報処理装置によって実現されていてもよい。なお、１台の情報処理装置によって実現される場合にも、公開鍵が異なるサービスが提供されているものとする。
【００３８】
本実施形態の暗号化統計処理システムは、サービス提供者鍵生成処理、データ登録処理、プロキシ鍵生成処理、統計情報計算処理および復号処理を実行する。以下、各処理の流れについて説明する。
【００３９】
サービス提供者鍵生成処理について説明する。図６は、サービス提供者鍵生成処理の一例を示す流れ図である。
【００４０】
図６に示すように、サービス提供装置60-i（例えば、鍵生成部60-i-1）は、システムパラメータを入力として、公開鍵pk_iおよび秘密鍵sk_iを生成する（図６のステップKEYGEN1）。
【００４１】
次いで、サービス提供装置60-i（例えば、鍵生成部60-i-1）は、公開鍵pk_iを公開し、秘密鍵sk_iを保管する（図６のステップKEYGEN2）。なお、保管するとは、具体的には、記憶部に記憶することを意味する。
【００４２】
次に、データ登録処理について説明する。図７は、データ登録処理の一例を示す流れ図である。
【００４３】
図７に示すように、データ登録装置10（例えば、暗号データ生成部10-1）は、公開鍵pk_iおよび登録したいデータMを入力として、暗号文E(pk_i,M)を生成する（図７のステップDREG1）。
【００４４】
次いで、データ登録装置10（例えば、暗号データ登録要求部10-2）は、暗号文E(pk_i,M)をデータベース20-iに送信し、記憶させる(図７のステップDREG2)。
【００４５】
次に、プロキシ鍵生成処理について説明する。図８は、プロキシ鍵生成処理の一例を示す流れ図である。
【００４６】
図８に示すように、サービス提供装置60-1〜60-N（例えば、統合用鍵生成部60-i-2）は、それぞれ公開鍵pk_1〜pk_N、秘密鍵sk_1〜sk_Nを入力として、対話的に全体公開鍵gpkを生成する（図８のステップRKGEN1)。
【００４７】
次いで、全体公開鍵gpkおよび秘密鍵pk_iを入力としたサービス提供装置60-i（例えば、プロキシ鍵生成部60-i-3）は、プロキシ鍵rk_iを生成し、プロキシ装置30-iに送信する（図８のステップRKGEN2)。
【００４８】
次に、統計情報計算処理について説明する。図９は、統計情報計算処理の一例を示す流れ図である。
【００４９】
図９に示すように、プロキシ装置30-iは、プロキシ鍵rk_iと、データベースiに記憶された暗号文の集合{E(pk_1,M)}とを入力として受け取る（図９のステップＳ１０１）。
【００５０】
次いで、プロキシ装置30-i（例えば、暗号データ変換部30-i-1）は、プロキシ鍵rk_iと暗号文の集合{E(pk_1,M)}とから、暗号化部分統計データE(gpk,M_i)を生成し、統合データ生成装置40に送信する（図９のステップＳ１０２）。
【００５１】
ここでM_iは、データベースiに記憶された暗号文の集合{E(pk_1,M)}の全平文に対して、統計処理を施した結果を意味する変数とする。
【００５２】
プロキシ装置30-1〜30-Nから、暗号化部分統計データE(gpk,M_1)〜E(gpk,M_N)を受信した統合データ生成装置40（例えば、統合データ生成部40-1）は、暗号化統計データE(gpk,si)を生成する（図９のステップＳ１０３）。ここでsiは、M_1〜M_Nに対して統計処理を施した結果を意味する。
【００５３】
次に、復号処理について説明する。図１０は、復号処理の一例を示す流れ図である。
【００５４】
図１０に示すように、サービス提供装置60-1〜60-Nは、それぞれ秘密鍵sk_1および暗号化統計データE(gpk,si)を入力として受け取る（図１０のステップＳ２０１）。
【００５５】
次いで、サービス提供装置60-1〜60-N（例えば、部分復号部60-i-4）は、秘密鍵sk_Nおよび暗号化統計データE(gpk,si)から、対話的に復号結果siを生成する（図１０のステップＳ２０２）。
【００５６】
次に、具体的な例を用いて本実施形態の動作を説明する。以降、a^{b}と記載することでaのb乗を表す。また、a_iと記載することでaに下添え字iを付けた記号を意味する。
【００５７】
まず、ペアリング関数について説明する。G,G_Tを位数qを持つ巡回群とし、g_1,g_2をそれぞれGの生成元としたとき、ペアリング関数e:G×G→G_Tとは、任意のZ_qの元a,bに対して以下の性質を満たす２入力１出力の関数である。
【００５８】
・e(g_1^a,g_2^b)=e(g_1,g_2)^{ab}
・e(g_1,g_2)≠1
【００５９】
次に参考文献Ａ（G. Ateniese, K. Fu, M. Green, and S. Hohenberger, "Improved Proxy Re-Encryption Schemes with Applications to Secure Distributed Storage", ACM Transactions on Information and System Security (TISSEC), 2006.）に記載されたプロキシ再暗号化方式について説明する。
【００６０】
プロキシ再暗号化方式とは、公開鍵pk_Aで暗号化された暗号文を、プロキシ鍵rk_{A→B}と呼ばれる鍵を用いて、秘密鍵sk_Bで復号できる暗号文にsk_Aを用いずに変換する方法である。
【００６１】
プロキシ再暗号化方式は、鍵生成、プロキシ鍵生成、暗号化、再暗号化および復号の５つのアルゴリズムからなる。以下、各アルゴリズムについて説明する。
【００６２】
（鍵生成）
システムパラメータq,e,Gの生成元g，Z=e(g,g)を入力として受け取る。ユーザAの秘密鍵sk_a=aをZ_{q}からランダムに選択する。Z_{q}とは、位数qの巡回群を意味する。
【００６３】
次に、ユーザAの公開鍵pk_a=y_a=g^{a}を計算する。以下、同様にして、ユーザBが公開鍵pk_b=y_b=g^bを計算し、公開しているものとする。
【００６４】
（プロキシ鍵生成）
ユーザAの公開鍵pk_Aを用いて暗号化された暗号データを、ユーザBの秘密鍵sk_Bを用いて復号できる暗号データに変換するための鍵を生成するときの、動作の流れを説明する。
【００６５】
入力として、ユーザBの公開鍵pk_Bと、ユーザAの秘密鍵sk_Aとを受け取る。
【００６６】
次に、プロキシ鍵rk_{A→B}=y_b^{1/a}=g^{b/a}を計算する。
【００６７】
（暗号化）
ユーザAの公開鍵pk_Aを用いて、メッセージMを暗号化するときの、動作の流れを説明する。
【００６８】
Z_qから乱数rを選択する。
【００６９】
次に、(C_1,C_2)=(y_a^{r},Z^{M}・Z^{r})を計算する。
【００７０】
（再暗号化）
ユーザAの公開鍵pk_Aを用いて生成された暗号データ(C_1,C_2)を変換して、ユーザBの秘密鍵sk_Bを用いて復号できる暗号データ(C'_1,C'_2)を生成するときの、動作の流れを説明する。
【００７１】
入力として、ユーザAの公開鍵pk_Aを用いて生成された暗号データ(C_1,C_2)と、プロキシ鍵rk_{A→B}とを受け取る。
【００７２】
次に、(C'_1,C'_2)=(e(C_1,rk_{A→B}),C_2)=(e(g^{ar},g^{b/a}),Z^{M}・Z^{r})=(e(g,g)^{br},Z^{M}・Z^{r})=(Z^{br},Z^{M}・Z^{r})を計算する。
【００７３】
（復号）
上記の（再暗号化）で生成された(C'_1,C'_2)をユーザBの秘密鍵sk_Bを用いて復号する際の動作の流れを説明する。
【００７４】
まず、C'_1^{1/b}=Z^{r}を計算する。
【００７５】
次に、C'_2/Z^{r}=Z^{M}を計算する。
【００７６】
次に、Z^{M}からMを探索する。
【００７７】
上記参考文献Ａに記載されたプロキシ再暗号化方式は、暗号化の結果の暗号文(C_1,C_2)に対しても、再暗号化の結果の暗号文(C'_1,C'_2)に対しても、暗号化したまま平文に対して加算を行うことが可能である。
【００７８】
今、(C_1,C_2)=(y_a^{r_1},Z^{M_1}・Z^{r_1})，(C_3,C_4)=(y_a^{r_2},Z^{M_2}・Z^{r_2})とする。
【００７９】
このとき、(C_5,C_6)=(C_1・C_3，C_2・C_4)=(y_a^{r_1+r_2},Z^{M_1+M_2}・Z^{r_1+r_2})となり、(C_5,C_6)は、M_1+M_2の暗号文となる。この暗号文はユーザAの秘密鍵sk_Aを用いて復号可能である。
【００８０】
また、(C'_1,C'_2)=(Z^{b・r_1},Z^{M_1}・Z^{r_1})，(C'_3,C'_4)=(Z^{b・r_2},Z^{M_2}・Z^{r_2})とする。
【００８１】
このとき、(C'_5,C'_6)=(C'_1・C'_3，C'_2・C'_4)=(Z^{b(r_1+r_2)},Z^{M_1+M_2}・Z^{r_1+r_2})となり、(C'_5,C'_6)は、M_1+M_2の暗号文となる。この暗号文はユーザBの秘密鍵sk_Bを用いて復号可能である。
【００８２】
次に、本実施形態における暗号化統計処理システムの具体的な処理の流れについて説明する。本実施形態の暗号化統計処理システムは、サービス提供者鍵生成処理、データ登録処理、プロキシ鍵生成処理、統計情報計算処理および復号処理を実行する。
【００８３】
本例では、統計情報計算処理として、暗号化したままデータの総和を計算する方法を示すが、同様の流れで総積、平均値、分散値の計算が可能である。また、サービス提供装置は１以上の任意の整数N個存在しても構わないが、説明を簡略化するため、３個のときを例として説明する。以下、各処理の流れを説明する。
【００８４】
まず、サービス提供者鍵生成処理について説明する。図１１は、サービス提供者鍵生成処理の一例を示す流れ図である。
【００８５】
図１１に示すように、サービス提供装置60-iは、システムパラメータ(q,e,g,Z)を入力として、公開鍵pk_i=y_i=g^{x_i}と、秘密鍵sk_i=x_iとを生成する（図１１のステップKEYGEN1）。
【００８６】
次いで、サービス提供装置60-iは、公開鍵pk_iを公開し、秘密鍵sk_iを保管する（図１１のステップKEYGEN2）。
【００８７】
なお、ステップKEYGEN1およびKEYGEN2の動作は、サービス提供装置60-1,60-2,60-3によって、それぞれ独立して実行される。
【００８８】
次に、データ登録処理について説明する。図１２は、データ登録処理の一例を示す流れ図である。
【００８９】
図１２に示すように、データ登録装置10は、公開鍵pk_iおよび登録したいデータMを入力として、上記参考文献Ａに記載された方式で暗号化処理を行い、暗号文E(pk_i,M)=(y_i^{r},Z^M・Z^{r})を生成する（ステップDREG1）。
【００９０】
次に、データ登録装置10は、暗号文E(pk_i,M)をデータベース20-iに送信し、記憶させる(ステップDREG2)。以降データベース20-1,20-2,20-3には、それぞれ公開鍵pk_1,pk_2,pk_3を用いて暗号化されたデータが１つ以上記憶されているものとする。
【００９１】
次に、プロキシ鍵生成処理について説明する。図１３は、プロキシ鍵生成処理の一例を示す流れ図である。
【００９２】
図１３に示すように、サービス提供装置60-1〜60-3は、それぞれ公開鍵pk_1〜pk_3、秘密鍵sk_1〜sk_3を入力として、対話的に全体公開鍵gpk=g^{x_1・x_2・x_3}を生成する（ステップRKGEN1)。ここで、対話的にとは、サービス提供装置60-1から順番に、以下の処理を実行することである。
【００９３】
サービス提供装置60-1は、gpk=g^{x_1}を計算し、サービス提供装置60-2に送信する。
【００９４】
次に、サービス提供装置60-2は、gpk=gpk^{x_2}=g^{x_1・x_2}を計算し、サービス提供装置60-3に送信する。
【００９５】
次に、サービス提供装置60-3は、gpk=gpk^{x_3}=g^{x_1・x_2・x_3}を計算し、gpkを公開する。
【００９６】
なお、より安全性を高めるために、以下のように処理を実行するようにしてもよい。
【００９７】
サービス提供装置60-1は、gpk=g^{r_1x_1}を計算し、サービス提供装置60-2に送信する。
【００９８】
次に、サービス提供装置60-2は、gpk=gpk^{r_2x_2}=g^{r_1x_1・r_2x_2}を計算し、サービス提供装置60-3に送信する。
【００９９】
次に、サービス提供装置60-3は、gpk=gpk^{r_3x_3}=g^{r_1x_1・r_2x_2・r_3x_3}を計算し、サービス提供装置60-1に送信する。
【０１００】
次に、サービス提供装置60-1は、gpk=gpk^{1/r_1}=g^{x_1・r_2x_2・r_3x_3}を計算し、サービス提供装置60-2に送信する。
【０１０１】
次に、サービス提供装置60-2は、gpk=gpk^{1/r_2}=g^{x_1・x_2・r_3x_3}を計算し、サービス提供装置60-3に送信する。
【０１０２】
次に、サービス提供装置60-3は、gpk=gpk^{1/r_3}=g^{x_1・x_2・x_3}を計算し、gpkを公開する。
【０１０３】
次いで、全体公開鍵gpkを生成すると、サービス提供装置60-iは、gpkと秘密鍵sk_iとを入力として、rk_{i}=gpk^{1/x_i}を計算し、プロキシ鍵を生成する。すなわち、rk_{1}=g^{x_2・x_3}，rk_{2}=g^{x_1・x_3}，rk_{3}=g^{x_1・x_2}をそれぞれ計算する。そして、サービス提供装置60-iは、プロキシ鍵rk_iをプロキシ装置30-iに送信する（ステップRKGEN2)。
【０１０４】
次に、統計情報計算処理について説明する。図１４は、統計情報計算処理の一例を示す流れ図である。
【０１０５】
図１４に示すように、プロキシ装置30-iは、プロキシ鍵rk_iと、データベースiに記憶された暗号文の集合{E(pk_i,M)}とを入力として受け取る（ステップＳ３０１）。
【０１０６】
ここでM_iは、データベースiに記憶された暗号文の集合{E(pk_1,M)}の全平文に対して、総和を計算した結果を意味する記号とする。また、R_iは、データベースiに記憶された暗号文の集合{E(pk_1,M)}を生成する際に使用された乱数の総和を計算した結果を意味する記号とする。
【０１０７】
まずプロキシ装置30-iは、データベースiに記憶された暗号文の集合{E(pk_i,M)}を入力として、暗号化したまま平文の総和を計算する。
【０１０８】
すなわち、{E(pk_i,M)}={(C_1,C_2),(C_3,C_4)}、(C_1,C_2)=(y_i^{r_1},Z^{M_1}・Z^{r_1})，(C_3,C_4)=(y_i^{r_2},Z^{M_2}・Z^{r_2})としたとき、(C_5,C_6)=(C_1・C_3，C_2・C_4)=(y_i^{r_1+r_2},Z^{M_1+M_2}・Z^{r_1+r_2})を計算する。
【０１０９】
次に、プロキシ装置30-iは、(C_5,C_6)とプロキシ鍵rk_iとを入力として、上記参考文献Ａに記載された方式での再暗号化を行う。すなわち、(C'_5,C'_6)=(e(C_5,rk_i),C_6)=(Z^{x_1x_2x_3・R_i},Z^{M_i}・Z^{R_i}を計算する。そして、プロキシ装置30-iは、計算結果（すなわち、暗号化部分統計データ）を統合データ生成装置40に送信する（ステップＳ３０２）。
【０１１０】
次に、統合データ生成装置40は、プロキシ装置30-1〜30-3から、暗号化部分統計データE(gpk,M_1)〜E(gpk,M_3)を受信する。ここで説明のために、E(gpk,M_1)=(c_1,c_2)，E(gpk,M_2)=(c_3,c_4)，E(gpk,M_3)=(c_5,c_6)とする。
【０１１１】
統合データ生成装置40は、E(gpk,si)=(c_1・c_3・c_5,c_2・c_4・c_6)=(Z^{x_1x_2x_3(R_1+R_2+R_3)},Z^{M_1+M_2+M_3}・Z^{R_1+R_2+R_3})を計算する（ステップＳ３０３）。ここでsiは、M_1からM_3の総和を意味する記号とする。その後、統合データ生成装置40は、統合データ記憶装置50にE(gpk,si)を送信する。
【０１１２】
次に、復号処理について説明する。図１５は、復号処理の一例を示す流れ図である。
【０１１３】
図１５に示すように、サービス提供装置60-1〜60-3は、それぞれ秘密鍵sk_1および暗号化統計データE(gpk,si)，秘密鍵sk_2および暗号化統計データE(gpk,si)=(C_1,C_2)，秘密鍵sk_3および暗号化統計データE(gpk,si)を受信する（ステップＳ４０１）。
【０１１４】
次いで、サービス提供装置60-1から順に以下の処理を行う（ステップＳ４０２）。
【０１１５】
サービス提供装置60-1は、(C'_1,C'_2)=(C_1^{1/x_1}=Z^{x_2x_3(R_1+R_2+R_3)},C_2)を計算し、サービス提供装置60-2に送信する。
【０１１６】
次に、サービス提供装置60-2は、(C''_1,C''_2)=(C'_1^{1/x_2}=Z^{x_3(R_1+R_2+R_3)},C'_2)を計算し、サービス提供装置60-3に送信する。
【０１１７】
次に、サービス提供装置60-3は、(C'''_1,C'''_2)=(C''_1^{1/x_3}=Z^{(R_1+R_2+R_3)},C''_2)を計算する。
【０１１８】
次いで、サービス提供装置60-iは、C'''_2/C'''_1=Z^{M_1+M_2+M_3}を計算する。その後、サービス提供装置60-iは、Z^{M_1+M_2+M_3}よりM_1+M_2+M_3（すなわち、復号結果）を探索する。
【０１１９】
以上のように、本実施形態では、複数のサーバの公開鍵および秘密鍵を用いて対話的に全体公開鍵を生成し、生成した全体公開鍵と秘密鍵とに基づいて個々のプロキシ鍵を生成する。そして、プロキシ鍵と公開鍵で暗号化されたデータとから、暗号化統計データを生成する。従って、異なる公開鍵を用いて暗号化された暗号データに対して、暗号化したまま統計処理を行うことができる。
【０１２０】
なお、本実施形態では、プロキシ装置30-iが、データベースiに記憶された暗号文の集合{E(pk_i,M)}を入力として、暗号化したまま平文の総和を計算しているが、この処理は他の装置で行われることとしてもよく、あらかじめこの処理の結果の暗号文がデータベースiに含まれるようにしてもよい。
【０１２１】
例えば、データ登録装置によってデータベースに暗号データが登録されるたびに、データベースにおいて暗号化したまま平文の和を計算する処理を行うことも可能である。また、本実施形態では、例として、参考文献Ａに記載されたプロキシ再暗号化方式を用いているが、そのほかのプロキシ再暗号化方式を用いてもよい。例えば、エルガマル暗号や楕円エルガマル暗号を用いてもよい。
【０１２２】
また、データベースiに記憶された暗号文の集合{E(pk_i,M)}を入力として、暗号化したまま平文の総和を計算せずに、すべての暗号データを再暗号化し、再暗号化後に統合データ生成装置40において暗号化したまま平文の総和を計算するようにしてもよい。
【０１２３】
また、本実施形態では、各データベースには１つの公開鍵で暗号化された暗号データの集合が記憶されていることとしたが、例えばデータベースが１つで、異なる公開鍵で暗号化された暗号データが記憶されていることとしてもよい。
【０１２４】
また、本実施形態では、gpkの計算、暗号化統計データの復号処理に、複数のサービス提供装置が通信を行いながら処理する方法を記載したが、他のマルチパーティ計算方法を利用しても構わない。
【０１２５】
本実施形態では、プロキシ装置30-1はプロキシ鍵rk_1=g^{x_2・x3}を保持するが、これに加えてx_1,x_2が分かったとしても、x_3を求められないことが数学的に証明可能である。また、暗号化統計データを復号するためには、x_1,x_2,x_3のすべての鍵が必要である。したがって、プロキシ装置の管理者が悪意を持ち、かつ、N人中N-1人のサービス提供者と結託した場合であっても、残る1人のサービス提供者の秘密鍵が漏れないかぎり、復号を行うことができない。
【０１２６】
以上のように、本発明は、複数サーバに対応可能な暗号化統計処理システムに関する。特に、異なる公開鍵を用いて暗号化された暗号データに対して、暗号化したまま統計処理を行う暗号化統計処理システムに関する。また、本発明は、上記に示した実施例に限定されるものではなく、本発明の技術思想の範囲内において、実施例を適宜変更して実施可能である。
【０１２７】
次に、本発明による暗号化統計処理システムの最小構成について説明する。図１６は、暗号化統計処理システムの最小の構成例を示すブロック図である。図１６に示すように、暗号化統計処理システムは、最小の構成要素として、複数のサービス提供装置６０と、データ登録装置１０と、データベース２０と、複数のプロキシ装置３０と、統合データ生成装置４０と、統合データ記憶装置５０とを備えている。
【０１２８】
また、サービス提供装置６０は、データを暗号化するためのサービスの公開鍵および公開鍵に対応した秘密鍵を生成する鍵生成手段６１と、プロキシ鍵生成手段６２とを含む。データ登録装置１０は、サービスの公開鍵および所定のデータを入力として、暗号データを生成しデータベースに記憶させる暗号データ生成手段１１を含む。プロキシ装置３０は、暗号化部分統計データ生成手段３１を含む。統合データ生成装置４０は、暗号化統計データ生成手段４１を含む。
【０１２９】
図１６に示す最小構成の暗号化統計処理システムでは、プロキシ鍵生成手段６２は、サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成する。次いで、暗号化部分統計データ生成手段３１は、データベース２０に記憶された暗号データに対して、プロキシ鍵生成手段６２によって生成されたプロキシ鍵を入力として、暗号化部分統計データを生成する。次いで、暗号化統計データ生成手段４１は、暗号化部分統計データを各プロキシ装置３０から入力し、暗号化統計データを生成する。
【０１３０】
従って、最小構成の暗号化統計処理システムによれば、異なる公開鍵を用いて暗号化された暗号データに対して、暗号化したまま統計処理を行うことができる。
【０１３１】
なお、本実施形態では、以下の（１）〜（５）に示すような暗号化統計処理システムの特徴的構成が示されている。
【０１３２】
（１）暗号化統計処理システムは、複数のサービス提供装置（例えば、サービス提供装置60-1）と、データ登録装置（例えば、データ登録装置10）と、データベース（例えば、データベース20）と、複数のプロキシ装置（例えば、プロキシ装置30-1）と、統合データ生成装置（例えば、統合データ生成装置40）と、統合データ記憶装置（例えば、統合データ記憶装置50）とを備え、サービス提供装置は、データを暗号化するためのサービスの公開鍵および公開鍵に対応した秘密鍵を生成する鍵生成手段（例えば、鍵生成部60-i-1）と、サービスの公開鍵および秘密鍵を入力として、プロキシ鍵を生成するプロキシ鍵生成手段（プロキシ鍵生成部60-i-3）とを含み、データ登録装置は、サービスの公開鍵および所定のデータを入力として、暗号データを生成する暗号データ生成手段（例えば、暗号データ生成部10-1によって実現される）を含み、データベースは、暗号データを記憶し、プロキシ装置は、データベースに記憶された暗号データに対して、プロキシ鍵生成手段によって生成されたプロキシ鍵を入力として、暗号化部分統計データを生成する暗号化部分統計データ生成手段（例えば、暗号データ変換部30-i-1によって実現される）を含み、統合データ生成装置は、暗号化部分統計データを各プロキシ装置から入力し、暗号化統計データを生成する暗号化統計データ生成手段（例えば、統合データ生成部40-1によって実現される）を含み、統合データ記憶装置は、暗号化統計データを記憶することを特徴とする。
【０１３３】
（２）暗号化統計処理システムにおいて、プロキシ鍵生成手段は、各サービス提供装置がそれぞれの秘密鍵を入力とし、各サービス提供装置と互いに通信を行うことによって、各サービス提供装置の秘密鍵に対応するプロキシ鍵を生成するように構成されていてもよい。
【０１３４】
（３）暗号化統計処理システムにおいて、サービス提供装置は、統合データ記憶装置に記憶された暗号化統計データと、各サービス提供装置の秘密鍵とを入力として、各サービス提供装置と互いに通信を行うことによって、暗号化統計データの復号を行い、統計情報を生成する統計情報生成手段（例えば、部分復号部60-i-4によって実現される）を含むように構成されていてもよい。
【０１３５】
（４）暗号化統計処理システムにおいて、プロキシ鍵生成手段は、素数位数qを持つ群G，G_T、e()をGの元2つを入力としてG_Tの群への写像であるペアリング関数、gを群Gの生成元、q,e,gおよびZ=e(g,g)をシステムパラメータとし、暗号データを記憶するデータベースの数を１以上の整数N、a_iをサービスiの秘密鍵、y_i=g^{a_i}を公開鍵としたとき、サービスiに対応するプロキシ鍵rk_iとして、g^{a_1a_2…a_N/a_i}を含むプロキシ鍵を生成するように構成されていてもよい。
【０１３６】
（５）暗号化統計処理システムにおいて、暗号データ生成手段は、メッセージをM、1以上q未満の乱数をrとしたとき、サービスiに対応する暗号データとして、(y_i^r,M・Z^r)を含む暗号データを生成し、暗号化統計データ生成手段は、統計情報を計算する対象となる暗号データを生成するために使用された乱数の総和をRとし、gpk=g^{a_1a_2…a_N}、統計情報をSとしたとき、(e(gpk,g)^R,S・Z^R)を含む暗号化統計データを生成するように構成されていてもよい。
【０１３７】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１３８】
この出願は、２０１１年６月１０日に出願された日本特許出願２０１１−１３０４８９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１３９】
本発明は、通信ネットワークを介して、異なる公開鍵を用いて暗号化された暗号データに対して、暗号化したまま統計値を求める統計処理に好適に適用できる。
【符号の説明】
【０１４０】
１０  データ登録装置
１０−１  暗号データ生成部
１０−２  暗号データ登録要求部
１１  暗号データ生成手段
３０−ｉ  プロキシ装置
３０−ｉ−１  暗号データ変換部
３１  暗号化部分統計データ生成手段
４０  統合データ生成装置
４０−１  統合データ生成部
４１  暗号化統計データ生成手段
５０  統合データ記憶装置
６０−ｉ  サービス提供装置
６０−ｉ−１  鍵生成部
６０−ｉ−２  統合用鍵生成部
６０−ｉ−３  プロキシ鍵生成部
６０−ｉ−４  部分復号部
６１  鍵生成手段
６２  プロキシ鍵生成手段
【図１】
0005979141.tif 000002
【図２】
0005979141.tif 000003
【図３】
0005979141.tif 000004
【図４】
0005979141.tif 000005
【図５】
0005979141.tif 000006
【図６】
0005979141.tif 000007
【図７】
0005979141.tif 000008
【図８】
0005979141.tif 000009
【図９】
0005979141.tif 000010
【図１０】
0005979141.tif 000011
【図１１】
0005979141.tif 000012
【図１２】
0005979141.tif 000013
【図１３】
0005979141.tif 000014
【図１４】
0005979141.tif 000015
【図１５】
0005979141.tif 000016
【図１６】
0005979141.tif 000017