(57)【要約】      （修正有）【課題】データ再暗号化を介して機密データを保護するためのコンピュータ実施方法を提供する。【解決手段】暗号化データが保持されているデータベースに、公開鍵および秘密鍵と関連付けられるユーザのコンピューティングデバイス２４からデータクエリが送信されると、暗号化データの少なくとも一部分を識別すること及び暗号化データの識別されている部分に関するプレーンテキストを結果として加えることによって、クエリの結果が計算される。ユーザの公開鍵を使用して、その結果のための再暗号化鍵が生成され、再暗号化鍵を使用して結果が再暗号化される。再暗号化結果はその後、ユーザに送信される。【選択図】図１
2017225116.tif 000002
【特許請求の範囲】
【請求項１】
データ再暗号化を介して機密データを保護するためのコンピュータ実施システムであって、
暗号化データを保持するためのデータベースであり、前記暗号化データは、前記暗号化データの根底にあるプレーンテキストの加算をサポートする特性を含む、データベースと、
中央処理装置、メモリ、入力ポート、および出力ポートを備えるサーバであり、前記中央処理装置は、複数のユーザのうちの１人の公開鍵を使用して前記暗号化データの再暗号化鍵を生成するように構成されている、サーバと、
中央処理装置、メモリ、前記データベースからの前記暗号化データの少なくとも一部分および前記サーバからの前記再暗号化鍵を受信するための入力ポート、および、出力ポートを備えるさらなるサーバと
を備え、前記中央処理装置は、
前記再暗号化鍵を使用して前記暗号化データの部分を再暗号化し、
前記ユーザに前記再暗号化データを送信するように構成されている、システム。
【請求項２】
前記ユーザからのクエリに応答して前記暗号化データを処理し、前記クエリの結果を判定するための検索生成器であって、前記結果は前記暗号化データの部分を含む、検索生成器をさらに備える、請求項１に記載のシステム。
【請求項３】
前記ユーザの公開パラメータを生成し、前記公開パラメータの少なくとも１つを使用して前記公開鍵を生成するための公開鍵生成器をさらに備える、請求項１に記載のシステム。
【請求項４】
前記ユーザの秘密パラメータを生成し、前記秘密パラメータの少なくとも１つを使用して前記ユーザの秘密鍵を計算するための秘密鍵生成器をさらに備える、請求項１に記載のシステム。
【請求項５】
各メッセージをセグメントへと分割し、各セグメントを、第１のブロックおよび第２のブロックを含む２つのブロックへとさらに分割し、前記メッセージ内の各セグメントから前記第１のブロックを収集して暗号文を生成し、前記メッセージ内の各セグメントから前記第２のブロックを収集して暗号文を生成し、そのメッセージの暗号化として、前記第１のブロックからの前記暗号文と前記第２のブロックからの前記暗号文とを組み合わせることによって、各メッセージを暗号化するためのメッセージ暗号化器をさらに備える、請求項１に記載のシステム。
【請求項６】
データ再暗号化を介して機密データを保護するためのコンピュータ実施方法であって、
暗号化データを保持するステップであり、前記暗号化データは、前記暗号化データの根底にあるプレーンテキストの加算をサポートする特性を含む、保持するステップと、
複数のユーザのうちの１人の公開鍵を使用して前記暗号化データの再暗号化鍵を生成するステップと、
前記再暗号化鍵を使用して前記暗号化データの少なくとも一部分を再暗号化するステップと、
前記ユーザに前記再暗号化データを送信するステップと
を含む、方法。
【請求項７】
前記ユーザからのクエリに応答して前記暗号化データを処理するステップと、
前記クエリの結果を判定するステップであって、前記結果は前記暗号化データの部分を含む、判定するステップと
をさらに含む、請求項６に記載の方法。
【請求項８】
前記ユーザの公開パラメータを生成するステップと、
前記公開パラメータの少なくとも１つを使用して前記公開鍵を生成するステップと
をさらに含む、請求項６に記載の方法。
【請求項９】
前記ユーザの秘密パラメータを生成するステップと、
前記秘密パラメータの少なくとも１つを使用して前記ユーザの秘密鍵を計算するステップと
をさらに含む、請求項６に記載の方法。
【請求項１０】
各メッセージを暗号化するステップであって、
各メッセージをセグメントへと分割するサブステップと、
各セグメントを、第１のブロックおよび第２のブロックを含む２つのブロックへとさらに分割するサブステップと、
前記メッセージ内の各セグメントから前記第１のブロックを収集して暗号文を生成するサブステップと、
前記メッセージ内の各セグメントから前記第２のブロックを収集して暗号文を生成するサブステップと、
そのメッセージの暗号化として、前記第１のブロックからの前記暗号文と前記第２のブロックからの前記暗号文とを組み合わせるサブステップと
を含む、暗号化するステップをさらに含む、請求項６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、データ暗号化に関し、特に、データ再暗号化を介して機密データを保護するためのコンピュータ実施システムおよび方法に関する。
【背景技術】
【０００２】
企業は、通常の営業過程の間に大量のデータを収集する傾向にある。データの少なくとも一部分は、金融取引、医療既往歴、および、社会保障番号を含む顧客識別情報のような、機密情報を含む。収集されると、企業は、企業の方針によって、または、政府の指導および方針によって必要とされるように、時として長時間にわたってデータを保管しなければならない。しかしながら、ほとんどの企業は、相当量の保管空間が必要とされることに起因してデータ自体を保管することが不可能であり、したがって、より大規模な企業からのリースストレージおよび計算能力に依拠する。より大規模な企業によってデータを保管するために使用されるサーバは公共のものであり、多くの場合、クラウドベースである。
【０００３】
加えて、ビジネスインテリジェンスの分野は、傾向を識別し、戦略を導き、商行為の成功をサポートするために、分析に依存する。分析は一般的に、企業に雇われるアナリストによって実施される。これらのアナリストは一般的に、分析の前に保管されているデータを解読するための解読鍵を含む、重要なツールを託される。しかしながら、敵対者のような権限のない個人が暗号鍵を取得すると、データを記憶しているデータベース全体に対するアクセスが許可されてしまう。不都合なことに、アナリストのモバイルデバイスは、強力な侵入防止メカニズムを備えていないことが多く、これによって、アナリストは、敵対者による攻撃に対する弱点となる。
【０００４】
データ所有者の機密情報を、権限のない個人から保護することは、データの不正流用を防止するために極めて重要である。現在、機密データは、データが保管されているサーバにあるアクセス制御メカニズムを介して保護することができ、それによって、サーバは、最初に、データに関心のあるパーティと関わりをもち、その後、データがアクセスされる前に、関心のあるパーティが、アクセス制御メカニズムによって確立される認証プロトコルをパスするために必要な認証情報を入力することを要求する。不都合なことに、権限を与えられたユーザの認証情報の不正アクセスに起因して、多数のセキュリティ侵害が最近増大している。
【０００５】
ユーザが認証情報を入力することを要求することに加えて、データ内容に対するアクセスを防止することによって侵害の影響を低減するための追加のセキュリティ層として、保管されるデータは、保管する前に暗号化することができる。しかしながら、暗号化自体は、一般的に、データ内容の開示を防止するのに十分なほど安全ではない。たとえば、データを暗号化するために、企業は一般的に、保管する前に公開鍵を利用してデータを暗号化する。その後、企業と関係があるユーザがデータにアクセスする必要があるが、そうするためには、暗号化データを解読するための企業の秘密鍵を取得しなければならない。複数のユーザに秘密鍵に対する企業アクセスを許可すると、ユーザは、権限のないユーザに鍵を提供することができるため、データが弱い立場に置かれてしまう。加えて、秘密鍵は、権限のないユーザによって直接アクセスされる可能性があり、結果としてデータ内容がアクセスされてしまうことになる。不都合なことに、人間は単純なソーシャルエンジニアリング攻撃によって容易にだまされてしまうため、多くの場合、秘密鍵を取得することは極めて容易であり得る。
【０００６】
それゆえ、データ保護および侵害防止を改善するための手法が必要とされている。データ保護および侵害防止は、データ自体に対する、または、データにアクセスする権限を与えられている個人を介した、不正アクセスの影響を低減するために、大量のプレーンテキストデータの再暗号化方式を含むことが好ましい。
【０００７】
従来のセキュリティ方法よりも、機密データの安全性を増大させ、侵害の機会を低減するために、セキュアクラウドコンピューティングアーキテクチャを使用することができる。機密データをクラウドベースのサーバ上に保管しているデータ所有者、および、データにアクセスする権限を与えられている各個人のために、公開暗号鍵および秘密暗号鍵を生成することができる。保管する前に、データは、データ所有者の公開鍵を使用して暗号化される。ユーザは、暗号化データにアクセスするためにクエリを提出することができ、クエリの結果は、保管されている暗号化データに基づいて決定される。ユーザの公開鍵を使用して、要求しているユーザの再暗号化鍵が生成される。ある暗号文形態にある暗号化データ結果はその後、再暗号化鍵を使用して異なる暗号文形態へと再暗号化される。再暗号化結果は要求している個人に提供され、その後、分析およびさらなる使用のために解読される。具体的には、再暗号化暗号文の解読によって、根底にあるプレーンテキスト、すなわちクエリ結果が明らかになる。
【発明の概要】
【課題を解決するための手段】
【０００８】
一実施形態は、データ再暗号化を介して機密データを保護するためのコンピュータ実施方法を提供する。暗号化データが保持されている。公開鍵および秘密鍵と関連付けられるユーザからデータクエリが受信される。暗号化データの少なくとも一部分を識別することによって、および、暗号化データの識別されている部分に関するプレーンテキストを結果として加えることによって、クエリの結果が計算される。ユーザの公開鍵を使用して、その結果のための再暗号化鍵が生成され、再暗号化鍵を使用して結果が再暗号化される。再暗号化結果はその後、ユーザに送信される。
【０００９】
本発明のまた他の実施形態が、当業者には、以下の詳細な説明から容易に諒解される。以下の詳細な説明においては、本発明を実行するために企図される最良の形態を示すことによって、本発明の実施形態が記載されている。認識されるように、本発明は、他の実施形態および異なる実施形態が可能であり、そのいくつかの詳細は、様々な自明の関連事項において修正が可能であり、これらはすべて、本発明の趣旨および範囲から逸脱しない。したがって、図面および詳細な説明は、本質的に例示として考えられるべきであり、限定として考えられるべきではない。
【図面の簡単な説明】
【００１０】
【図１】図１は、一実施形態による、データ再暗号化を介して機密データを保護するためのコンピュータ実施システムを示すブロック図である。
【図２】図２は、一実施形態による、データ再暗号化を介して機密データを保護するためのコンピュータ実施方法を示す流れ図である。
【図３】図３は、暗号化設定を実施するためのプロセスを一例として示す流れ図である。
【図４】図４は、公開鍵および秘密鍵を生成するためのプロセスを一例として示す流れ図である。
【図５】図５は、図４の公開鍵を使用してデータを暗号化するためのプロセスを一例として示す流れ図である。
【図６】図６は、再暗号化鍵を生成するためのプロセスを一例として示す流れ図である。
【図７】図７は、図６の再暗号化鍵を使用して暗号文を再暗号化するためのプロセスを一例として示す流れ図である。
【図８】図８は、暗号文を解読するためのプロセスを一例として示す流れ図である。
【発明を実施するための形態】
【００１１】
企業は、大量のデータを収集および保管する。雇われたアナリストは、ビジネスインテリジェンスなどに使用するために、収集されているデータを分析することができる。しかしながら、アナリストは、各々が、分析の前に暗号化データを解読するための解読鍵のような、極めて重要なツールを託されているため、弱点であると考えられることが多い。不都合なことに、アナリストのほとんどは、強力な侵入防止メカニズムを備えておらず、したがって、日常的に攻撃が行われている。各データ所有者について別個にデータを暗号化し、データ所有者によって権限を与えられている特定のユーザに対してデータを再暗号化することが、サーバに対する不正アクセス、信用できないユーザ、または、データのセキュリティ情報に精通したユーザに対する攻撃に起因するデータの侵害を防止する一助となる。
【００１２】
再暗号化によって、暗号化データベースを解読するために使用される解読鍵がもはやエンドポイントに存在しないことが促進される。図１は、一実施形態による、データ再暗号化を介して機密データを保護するためのコンピュータ実施システム１０を示すブロック図である。経時的に、データ所有者は、通常の営業過程の間に大量のプレーンテキスト鍵１６を収集することができ、これらは元々、所有者と関連付けられるサーバ１１に対して相互接続されているローカルデータベース１５上に保管されているものであり得る。プレーンテキスト鍵１６は、文書、メッセージ、音声記録、ビデオクリップ、医療記録、金融取引、および位置データ、ならびに、他のタイプのデータを含むことができる。データベース１５はまた、データ所有者の公開鍵１７および秘密鍵１８をも含むことができる。
【００１３】
サーバ１１は、暗号化器１２と、設定モジュール１３と、鍵生成器１４とを含む。暗号化器１２は、データ所有者の公開鍵を使用して、データベース１５上に保管されているプレーンテキスト鍵１６を暗号化する。暗号化されると、データ２３は、クラウドベースのサーバ１９と関連付けられるデータベース２２内に記憶するために送信される。クラウドベースのストレージは、極めて大容量の記憶空間を提供し、データ所有者がすべてのデータをローカルに保管する負担が軽減する。クラウドベースのサーバから暗号化データ２３にアクセスするために、権限を与えられているユーザは各々、公開鍵２９および秘密鍵３０と関連付けられ、ここで、公開鍵は、そのユーザのコンピューティングデバイス２４と関連付けられるデータベース２８内に保持することができる。代替的に、公開鍵２９は、クラウドベースのサーバのデータベース内に記憶されてもよい。ユーザの公開鍵２９および秘密鍵３０は、設定モジュール１３を介して所有者のサーバ１１によって生成することができ、設定モジュール１３は、図３を参照して下記にさらに説明するように、鍵生成器１４によって暗号化データ２３にアクセスする権限を与えられている各ユーザの鍵を生成するために使用することができるパラメータを出力する。
【００１４】
権限を与えられている各ユーザは、データに対する分析を実施するために、デスクトップまたはラップトップコンピュータ、および、モバイルデバイスのようなコンピューティングデバイス２４を介して所有者の暗号化データ２３にアクセスすることができる。具体的には、コンピューティングデバイス２４は、クエリを生成するためのクエリ生成器２６と、解読器２７を有するサーバ２５と関連付けられている。クエリはクラウドベースのサーバ１９に送信され、サーバ１９は、クエリを受信および解析するためのクエリ受信機２０と、クエリに応答して暗号化データ２３を処理し、１つまたは複数の暗号化結果を生成する結果ファインダ２１とを含む。クエリの結果は、結果の根底にあるプレーンテキストを加えることによって計算される。しかしながら、暗号化結果をユーザに提供する前に、結果はプロキシ再暗号化サーバ３１に送信され、当該サーバ３１は、鍵生成器３２と、再暗号化器３３とを含む。鍵生成器３２は、図６を参照して下記にさらに詳細に説明するように、データ所有者の秘密鍵およびその要求しているユーザの公開鍵に基づいて、権限を与えられている各ユーザの再暗号化鍵３５を生成する。ユーザの再暗号化鍵３５は、暗号文領域における加法的準同型演算をサポートすることができ、プロキシ再暗号化器３１と関連付けられるデータベース３４内に記憶される。再暗号化器３３は、暗号化データ結果の暗号文を、データ所有者の公開鍵の下から要求しているユーザの公開鍵へと再暗号化し、要求しているユーザに再暗号化結果を送信する。要求しているユーザによって受信されると、再暗号化データは、解読器２７によって要求しているユーザの秘密鍵を使用して解読することができる。再暗号化暗号文の解読によって、根底にあるプレーンテキスト、すなわちクエリ結果が明らかになる。
【００１５】
モバイルコンピューティングデバイスおよびサーバは各々、本明細書において開示されている実施形態を実行するための１つまたは複数のモジュールを含むことができる。モジュールは、従来のプログラミング言語でソースコードとして書かれているコンピュータプログラムまたは手順として実装することができ、オブジェクトまたはバイトコードとして、中央処理装置による実行のために提示される。代替的に、モジュールはまた、集積回路としてハードウェア内に実装されてもよく、クライアントおよびサーバの各々は、特化したコンピュータとして機能することができる。ソースコードならびにオブジェクトおよびバイトコードの様々な実施態様は、フロッピーディスク、ハードドライブ、デジタルビデオディスク（ＤＶＤ）、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）および同様の記憶媒体のような、コンピュータ可読記憶媒体上に保持することができる。他のタイプのモジュールおよびモジュール機能、ならびに、他の物理ハードウェア構成要素が可能である。
【００１６】
再暗号化暗号文は、データ侵害を防止する一助となるとともに、解読鍵の共有を防止し、さらなるレベルのセキュリティを追加することによって、発生する任意の侵害の影響を最小限に抑える。具体的には、再暗号化鍵が盗まれた場合、権限のないすべてのユーザが鍵についてできることは、暗号文を１つの公開鍵から別の公開鍵へと変換することである。言い換えれば、権限のないユーザは、暗号文を解読することは不可能である。図２は、一実施形態による、データ再暗号化を介して機密データを保護するためのコンピュータ実施方法４０を示す流れ図である。データ所有者は、データ所有者自身および所有者のデータにアクセスする権限を与えられているユーザの公開鍵および秘密鍵自体を生成する（ブロック４２）ためのパラメータを識別することを含む、設定を実施する（ブロック４１）。パラメータの生成はさらに、図３を参照して下記に詳細に説明されており、一方で、データ所有者およびユーザの公開鍵および秘密鍵の生成はさらに、図４を参照して下記に説明されている。設定と同時に、または、設定の後に、図６を参照して下記にさらに説明されているように、１人または複数の権限を与えられているユーザの再暗号化鍵を、ユーザの公開鍵を使用して生成することができる（ブロック４３）。
【００１７】
図５を参照して下記にさらに説明されているように、所有者によって収集されるデータを、所有者の公開鍵を使用して暗号化することができ（ブロック４４）、１つまたは複数のクラウドベースのサーバ上に保管することができる。１人または複数の権限を与えられているユーザは、データの少なくとも１つの部分集合に対するクエリを提出する（ブロック４５）ことによって、暗号化データに対する分析を実施することができる。加法的準同型アルゴリズムを使用して、また、暗号化データに基づいて、クエリを満たす暗号化結果の根底にあるプレーンテキストを加えることによって、クエリの結果が計算される（ブロック４６）。要求しているユーザに結果を提供する前に、暗号化結果およびプレーンテキスト結果を含む結果は、図７を参照して下記にさらに説明されているように、再暗号化鍵を使用して再暗号化される（ブロック４７）。その後、再暗号化結果は、要求しているユーザに提供することができ（ブロック４８）、図８を参照して下記にさらに説明されているように、ユーザによる使用のために解読することができる（ブロック４９）。
【００１８】
所有者のデータにアクセスする権限を与えられている各ユーザは、公開鍵および秘密鍵を関連付けられる。ユーザの鍵は、ユーザの、データ所有者との共通の関係に基づいて関連付けられるべきである。設定フェーズは、権限を与えられているすべてのユーザの鍵が共通のパラメータセットに基づいて関係付けられるように、鍵を生成するためのパラメータを決定する。図３は、暗号化設定を実施するためのプロセス５０を一例として示す流れ図である。設定中、各々の次数がＮ＝ｐ１ｋｐ２ｋｐ３である２つの乗法巡回群ＧおよびＧＴを生成するために、双線形群生成アルゴリズムが実行される（ブロック５１）。ｐ１、ｐ２、およびｐ３の各々は、
【００１９】
【数１】
2017225116.tif 000003
【００２０】
、Ｇの生成元、および双線形写像ｅ：ＧｘＧ→ＧＴとともに同じく双線形群生成アルゴリズムを介して出力される個別の素数であり、ｋはＮ未満の正の整数である。したがって、実行されると、双線形群生成器は、以下のパラメータ、すなわち、
【００２１】
【数２】
2017225116.tif 000004
【００２２】
の各々を識別し（ブロック５２）、
【００２３】
【数３】
2017225116.tif 000005
【００２４】
は群生成元である。
【００２５】
要素の集合ＺＮ＝｛０，１，．．．，Ｎ−１｝がアクセスされ（ブロック５３）、要素の２つの部分集合が集合ＺＮからランダムに選択される（ブロック５４）。ランダムに選択された各要素は、２つの計算された要素集合を生成するために、累乗法を通じて処理される（ブロック５５）。たとえば、要素の２つの部分集合α０，α１，．．．，αｋ−１およびβ０，β１，．．．，βｋ−１を集合ＺＮからランダムに選択することができ、以下の式において別個に利用して、
【００２６】
【数４】
2017225116.tif 000006
【００２７】
パラメータｈ０，．．．，ｈｋ−１，ｆ０，．．．，ｆｋ−１を生成することができる。
【００２８】
また、設定フェーズの間、図８を参照して下記にさらに説明されているように、素数のうちの１つを使用して暗号化および再暗号化暗号文を解読するために復号アルゴリズムとともに使用するための解読オラクルも構築される（ブロック５６）。最後に、パラメータＧ、ＧＴ、Ｎ、ｇ、ｅ、および計算されたパラメータ群ｈ０，．．．，ｈｋ−１，ｆ０，．．．，ｆｋ−１が、公開パラメータとして出力され（ブロック５７）、一方で、ｐ１、ｐ２、およびｐ３は、秘密パラメータとしてデータ所有者によって保管される（ブロック５８）。
【００２９】
設定が実施されると、データ所有者および１人または複数のユーザの公開鍵および秘密鍵を生成することができる。たとえば、新たな被雇用者が雇われると、その被雇用者がクラウドベースのサーバ上に保管されており、雇用者によって所有されている暗号化データにアクセスするために、公開鍵および秘密鍵を生成することができる。図４は、公開鍵および秘密鍵を生成するためのプロセス６０を一例として示す流れ図である。群Ｇが、公開設定パラメータからアクセスされ、群から２つの要素がランダムに選択される（ブロック６１）。一実施形態において、要素は、群ＺＮからγおよび
【００３０】
【数５】
2017225116.tif 000007
【００３１】
、すなわち、別の公開設定パラメータをサンプリングし、その後、
【００３２】
【数６】
2017225116.tif 000008
【００３３】
のように、設定フェーズからの群生成元を使用することによって決定することができる。
【００３４】
加えて、２つの要素から成る２つの群が各々、集合ＺＮからランダムに選択される（ブロック６２）。たとえば、
【００３５】
【数７】
2017225116.tif 000009
【００３６】
である。Ｇからのランダム要素およびＺＮのランダム要素の２つの群を使用して、公開鍵が計算される（ブロック６３）。具体的には、ＧおよびＺＮからのランダム要素が計算されて、
【００３７】
【数８】
2017225116.tif 000010
【００３８】
が生成される。その後、公開鍵が、
【００３９】
【数９】
2017225116.tif 000011
【００４０】
として出力される（ブロック６５）。
【００４１】
その間に、ＺＮから選択されるランダム要素と秘密パラメータのうちの１つの両方に基づいて、秘密鍵が計算される（ブロック６４）。一実施形態では、ｐ１が秘密パラメータに使用されるが、別の秘密パラメータが使用されてもよい。その後、秘密鍵が
【００４２】
【数１０】
2017225116.tif 000012
【００４３】
として出力される（ブロック６５）。出力されると（ブロック６５）、公開鍵および秘密鍵は、データ所有者によって保持されるとともに、保管されているデータにアクセスするために観覧付けられるユーザに提供され得る。設定フェーズからのパラメータの使用はまた、上記で識別されたプロセスを使用してデータ所有者の公開鍵および秘密鍵を生成するために使用することもできる。
【００４４】
データ、特に機密データをクラウドベースのサーバ上に保管する前に、データ所有者は、侵害を防止するとともに、侵害が発生しそうなデータへのアクセスを低減するのを助けるために、データを暗号化することができる。図５は、図４の公開鍵を使用してデータを暗号化するためのプロセス７０を一例として示す流れ図である。メッセージのような、暗号化されるべきデータが、データ所有者の公開鍵とともに受信される（ブロック７１）。各メッセージがセグメントＭｉに分割され（ブロック７２）、その後、各セグメントは２つのブロックＭｉ［１］およびＭｉ［２］に分割される（ブロック７３）。一実施形態では、メッセージセグメントは秘密共有を使用して分割されるが、メッセージセグメントを分割するための他のプロセスが可能である。
【００４５】
各メッセージについて、第１のメッセージブロックＭｉ［１］のすべてが収集され（ブロック７４）、第２のメッセージブロックＭｉ［２］のすべてが収集される（ブロック７７）。その後、符号化アルゴリズムが、第１のブロック集合および第２のブロック集合に対して別個に実行される（ブロック７５、７８）。各ブロック群に対するアルゴリズムは、同時にまたは非同期的に実行することができる。符号化アルゴリズムは入力として、データ所有者の公開鍵
【００４６】
【数１１】
2017225116.tif 000013
【００４７】
およびメッセージを受信する。一実施形態において、符号化アルゴリズムは以下のようなものである。
【００４８】
【数１２】
2017225116.tif 000014
【００４９】
符号化アルゴリズムの実行中、ＺＮから２つの要素から成る２つの群
【００５０】
【数１３】
2017225116.tif 000015
【００５１】
がサンプリングされ、メッセージを符号化するために使用される。具体的には、以下の式に従って、第１のメッセージブロック群が符号化されて、暗号文Ｃ１が生成される（ブロック７６）。
【００５２】
【数１４】
2017225116.tif 000016
【００５３】
式中、ｈｉは、図３を参照して上記で説明されているように、設定フェーズ中に識別される公開パラメータの一部分を表す。その間、以下の式に従って、第２のメッセージブロック群が符号化されて、暗号文Ｃ２が生成される（ブロック７９）。
【００５４】
【数１５】
2017225116.tif 000017
【００５５】
式中、ｆｉは、図３を参照して上記で説明されているように、設定フェーズ中に識別される公開パラメータの一部分を表す。第１のメッセージブロックの暗号文Ｃ１と第２のメッセージブロックの暗号文Ｃ２はその後、メッセージの暗号文Ｃ＝（Ｃ１，Ｃ２）として組み合わされ（ブロック８０）、その後、暗号化メッセージとして出力される（ブロック８１）。
【００５６】
暗号化データが記憶されると、ユーザは、クエリを提出することによってデータを分析することができる。クエリの結果は、たとえば、クラウドベースのサーバを介して識別することができる。しかしながら、要求しているユーザに結果を提供する前に、暗号化結果は、データ所有者の公開鍵の下からユーザの公開鍵の下へと再暗号化される。図６は、再暗号化鍵を生成するためのプロセス９０を一例として示す流れ図である。データ所有者の秘密鍵
【００５７】
【数１６】
2017225116.tif 000018
【００５８】
およびユーザの公開鍵
【００５９】
【数１７】
2017225116.tif 000019
【００６０】
が、入力として受信される（ブロック９１）。データ所有者の秘密鍵およびユーザの公開鍵の各々は解析され（ブロック９２）、集合ＺＮから２つの要素
【００６１】
【数１８】
2017225116.tif 000020
【００６２】
がランダムに選択される（ブロック９３）。再暗号化鍵ｒｋが、以下のように２つの部分において計算される。
【００６３】
【数１９】
2017225116.tif 000021
【００６４】
、式中、
【００６５】
【数２０】
2017225116.tif 000022
【００６６】
具体的には、再暗号化鍵の第１の半部が、集合ＺＮから選択される第１のランダム要素ｚ、データ所有者の秘密鍵の第１の部分（ａ，ｂ，ｇ）、および、ユーザの公開鍵の第１の部分（ａ，ｇａ、ｇｂ）を使用して計算される（ブロック９４）。また、再暗号化鍵の第２の半部が、集合ＺＮから選択される第２のランダム要素
【００６７】
【数２１】
2017225116.tif 000023
【００６８】
、データ所有者の秘密鍵の第２の部分
【００６９】
【数２２】
2017225116.tif 000024
【００７０】
、および、ユーザの公開鍵の第２の部分
【００７１】
【数２３】
2017225116.tif 000025
【００７２】
を使用して計算される（ブロック９５）。計算されると、再暗号化鍵の２つの部分は組み合わされ（ブロック９６）、暗号化データ結果を再暗号化するために出力される（ブロック９７）。
【００７３】
暗号化データの再暗号化暗号文は、ユーザが、データ所有者の秘密鍵ではなく、自身の秘密鍵を使用してデータを解読することを可能にし、さらなるレベルのセキュリティを提供する。図７は、図６の再暗号化鍵を使用して暗号文を再暗号化するためのプロセス１００を一例として示す流れ図である。要求しているユーザの再暗号化鍵
【００７４】
【数２４】
2017225116.tif 000026
【００７５】
および暗号化データ結果の暗号文Ｃ＝（Ｃ１、Ｃ２）が、入力として受信される（ブロック１０１）。一実施形態において、Ｃ１＝（Ｗ，Ｘ，Ｙ）であり、式中、
Ｗ＝（ｇａ）ｒ
Ｘ＝（ｇｂ）ｓ
【００７６】
【数２５】
2017225116.tif 000027
【００７７】
であり、
また、
【００７８】
【数２６】
2017225116.tif 000028
【００７９】
であり、式中、
【００８０】
【数２７】
2017225116.tif 000029
【００８１】
である。
【００８２】
再暗号化鍵の第１の半部と暗号文の第１の半部との構成要素ごとのペアリングが、再暗号化暗号文の第１の部分として以下のように計算される（ブロック１０２）。
Ｅ＝ｅ（Ｗ，Ｚ１）
Ｆ＝ｅ（Ｘ，Ｚ２）
Ｇ＝ｅ（Ｙ，Ｚ３）
【００８３】
再暗号化鍵の第２の半部と暗号文の第２の半部との構成要素ごとのペアリングが、再暗号化暗号文の第２の部分として以下のように計算される（ブロック１０３）。
【００８４】
【数２８】
2017225116.tif 000030
【００８５】
再暗号化暗号文の第１の部分と第２の部分とが
【００８６】
【数２９】
2017225116.tif 000031
【００８７】
のように組み合わされ（ブロック１０４）、再暗号化データとして出力される（ブロック１０５）。
【００８８】
ユーザが再暗号化データ結果を受信すると、ユーザの秘密鍵を使用して、再暗号化データを解読することができる。加えて、データ所有者が、必要に応じて、データ所有者の秘密鍵を使用して暗号化データを解読することができる。図８は、暗号文を解読するためのプロセス１１０を一例として示す流れ図である。暗号文および解読鍵が、入力として受信される（ブロック１１１）。暗号文は、データ所有者によって暗号化されているデータのようなフレッシュ暗号文Ｃ＝（Ｃ１、Ｃ２）、または、再暗号化暗号文
【００８９】
【数３０】
2017225116.tif 000032
【００９０】
を含む、フレッシュ暗号部の総和とすることができる。また、解読鍵は、解読されるべき暗号文に応じて、データ所有者の秘密鍵
【００９１】
【数３１】
2017225116.tif 000033
【００９２】
またはユーザの秘密鍵を含むことができる。ユーザまたはデータ所有者が、暗号文の解読を求める要求を提出し（ブロック１１２）、復号アルゴリズムがアクセスされる（ブロック１１３）。暗号文がフレッシュであるか、または、再暗号化暗号文のようなフレッシュ暗号文の総和であるかを含む、暗号文タイプの判定が行われる。一実施形態において、暗号文は、自動的に分類することができ、または、代替的に、個人もしくは他のユーザによって分類タイプを入力することができる。
【００９３】
暗号文がフレッシュである場合、設定中に生成されているオラクルがアクセスされ（ブロック１１４）、オラクルおよび復号アルゴリズムを介してフレッシュ暗号文の第１の部分が処理される（ブロック１１５）。具体的には、フレッシュ暗号文の第１の部分Ｃ１＝（Ｗ，Ｘ，Ｙ）が使用されて、以下が計算される。
【００９４】
【数３２】
2017225116.tif 000034
【００９５】
、式中、ａおよびｂは秘密鍵から取得される。
【００９６】
図５に関連して上記で提供されるＷ、Ｘ、およびＹの値が入力されると、式は以下のように考えられる。
【００９７】
【数３３】
2017225116.tif 000035
【００９８】
オラクルは、符号化アルゴリズムを介して問い合わせされ、
【００９９】
【数３４】
2017225116.tif 000036
【０１００】
がオラクルへと入力され、オラクルは、下記の復号アルゴリズムを使用して暗号文の第１の部分と関連付けられる第１のメッセージブロックＭｉ［１］を出力する（ブロック１１６）。
【０１０１】
【数３５】
2017225116.tif 000037
【０１０２】
式中、ｐ１は秘密パラメータであり、ｈｉは公開パラメータを含み、これらは両方とも、図３に関連して上記で論じられている。さらに、復号アルゴリズムの最小値ｉ＝０および最大値ｋ−１パラメータは、元のプレーンテキスト値の予測される範囲２＾｛ｋ（ｗ−１）｝を表す。オラクルの出力は、メッセージセグメントの第１のブロック（ｍ０［１］，．．．，ｍｋ−１［１］）のプレーンテキストを含む。
【０１０３】
暗号文の第１の部分の処理と同時に、またはこれと非同期的に、暗号文の第２の部分
【０１０４】
【数３６】
2017225116.tif 000038
【０１０５】
の処理（ブロック１１７）を、オラクルを用いずに復号アルゴリズムを介して行うことができる。具体的には、以下のように、暗号文の第２の部分を使用して以下が計算される。
【０１０６】
【数３７】
2017225116.tif 000039
【０１０７】
図５に関連して上記で提供される
【０１０８】
【数３８】
2017225116.tif 000040
【０１０９】
の値が入力されると、式は以下のように考えられる。
【０１１０】
【数３９】
2017225116.tif 000041
【０１１１】
その後、下記に与えられているような、復号アルゴリズムが実行される。
【０１１２】
【数４０】
2017225116.tif 000042
【０１１３】
復号アルゴリズムの結果は、メッセージセグメントの第２のブロック（ｍ０［２］，．．．，ｍｋ−１［２］）（ブロック１１８）のプレーンテキストを含む。最後に、メッセージセグメントの第１のブロックおよび第２のブロックのプレーンテキストが解読されたメッセージとして組み合わされ（ブロック１１９）、これは、市場調査の実行または挙動傾向およびパターンの識別のような、処理および分析のためにユーザに出力される（ブロック１２０）。
【０１１４】
暗号文が、再暗号化暗号文のような、フレッシュに生成されている暗号文の総和であると判定される場合、解読は、復号アルゴリズム内の最小値および最大値パラメータが元のフレッシュ暗号文のプレーンテキストメッセージの予測範囲およびそのような加えられるフレッシュ暗号文の総数に基づいて計算されることを除いて、上記で与えられているように実施することができる。
【図１】
2017225116.tif 000043
【図２】
2017225116.tif 000044
【図３】
2017225116.tif 000045
【図４】
2017225116.tif 000046
【図５】
2017225116.tif 000047
【図６】
2017225116.tif 000048
【図７】
2017225116.tif 000049
【図８】
2017225116.tif 000050