(57)【要約】【課題】準同型暗号化による暗号化データを管理する。【解決手段】本発明の暗号化データ・セットを保存し、該暗号化データ・セットに論理演算を実行するシステムは、暗号化データを保存する記憶手段と、プロセッサを有する計算処理手段と、を備える。前記暗号化データは対称準同型暗号化によって暗号化されている。前記計算処理手段は、暗号化結果を生成するために前記記憶手段に保存されている前記暗号化データに少なくとも一つの論理演算を実行するために前記プロセッサを使用し、前記暗号化結果は暗号化データに対応した単一のキーもしくはキー・セットのいずれかによって復号化される。【選択図】図６
2011232727.tif 000002
【特許請求の範囲】
【請求項１】
暗号化データ・セットを保存し、該暗号化データ・セットに論理演算を実行するシステムであって、
暗号化データを保存する記憶手段と、
プロセッサを有する計算処理手段と、
を備え、
前記暗号化データは対称準同型暗号化によって暗号化されており、
前記計算処理手段は、暗号化結果を生成するために前記記憶手段に保存されている前記暗号化データに少なくとも一つの論理演算を実行するために前記プロセッサを使用し、
前記暗号化結果は前記暗号化データに対応する単一のキーもしくはキー・セットのいずれかによって復号化される、
暗号化データ・セット保存および論理演算実行システム。
【請求項２】
複数の集合手段をさらに備え、
前記複数の集合手段の各々は少なくとも一つのソースから受信したデータ・セットを受信して暗号化し、
前記複数の集合手段の各々は、前記記憶手段に暗号化された前記データ・セットを送信する、
請求項１に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項３】
前記対称準同型暗号化はワン・タイム・パッド・ベース準同型暗号化を含む、
請求項１に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項４】
アーカイブ暗号化手段をさらに備え、
前記アーカイブ暗号化エンジンは暗号化を実行し、前記記憶手段に暗号化された前記データ・セットを送信する、
請求項１に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項５】
前記複数の集合手段は前記データ・セットを暗号化するためにキーを使用する、請求項２に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項６】
少なくとも２つの異なるキーが前記データ・セットを暗号化するために前記複数の集合手段によって使用される、請求項５に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項７】
暗号化された前記データ・セットは少なくとも２つの異なるキーで暗号化されており、
前記少なくとも１つの論理演算が実行された場合、単一のキーによって復号化可能な前記暗号化結果を生成するために、少なくとも１つのパッドを取り消す、
請求項１に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項８】
前記暗号化結果は、単一のキーによって復号化可能であり、
前記論理演算で使用される前記暗号化データは前記単一のキーによって復号化可能ではない、
請求項１に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項９】
前記少なくとも１つの論理演算は、少なくとも２つの暗号化されたデータ・セットの和を求めることを含む、請求項６に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項１０】
前記システムはクラウド・サービス・プロバイダである、請求項１に記載の暗号化データ・セット保存および論理演算実行システム。
【請求項１１】
サード・パーティ・システムにおいて暗号化データを保存し、該暗号化データに論理演算を実行する方法であって、
暗号化データを受信し、
前記暗号化データを前記サード・パーティ・システムの記憶手段に保存し、
前記サード・パーティ・システムの計算処理手段のプロセッサを使用して、暗号化結果を生成するために少なくとも１つの論理演算を実行し、
前記暗号化データは対称準同型暗号化を使用して暗号化され、
前記暗号化結果は前記暗号化に対応する単一のキーもしくはキー・セットのいずれかによって復号化される、
暗号化データ保存および論理演算実行方法。
【請求項１２】
暗号化はアーカイブ暗号化手段によって実行される、請求項１１に記載の暗号化データ保存および論理演算実行方法。
【請求項１３】
集合手段にデータを集合して暗号化し、
前記サード・パーティ・システムに暗号化データを送信する、
ことをさらに含む、
請求項１１に記載の暗号化データ保存および論理演算実行方法。
【請求項１４】
前記対称準同型暗号化はワン・タイム・パッド・ベース準同型暗号化を含む、請求項１１に記載の暗号化データ保存および論理演算実行方法。
【請求項１５】
前記暗号化結果は単一のキーによって復号化可能であり、
前記論理演算で使用される暗号化データは前記単一のキーによって復号化可能ではない、
請求項１１に記載の暗号化データ保存および論理演算実行方法。
【請求項１６】
前記暗号化データは複数の暗号化されたデータ・セットを含み、
前記暗号化されたデータ・セットの各々はキーによって暗号化され、
少なくとも１つの論理演算は、単一のキーによって復号化可能な前記暗号化結果を生成するためにデータ・セットの各々を暗号化する際に使用される少なくとも１つのパッドを取り消す、
請求項１１に記載の暗号化データ保存および論理演算実行方法。
【請求項１７】
暗号化データを保存し、該暗号化データに演算を実行するシステムであって、
データ記憶手段と、
計算処理手段と、
を備え、
前記データ記憶手段は準同型暗号化によって暗号化された複数のデータ・セットを受信し、
前記計算処理手段は受信した指示にもとづいて処理を実行し、
前記処理はプロセッサによって実行され、
前記処理は、
少なくとも２つの暗号化データ・セットを選択し、
暗号化結果を生成するために受信した前記指示にもとづいて選択された前記暗号化データ・セットに論理演算を実行し、
前記暗号化結果は前記暗号化データに対応する単一のキーもしくはキー・セットのいずれかによって復号化される、
暗号化データ保存および演算実行システム。
【請求項１８】
前記暗号化結果は単一のキーによって復号可能であり、
前記論理演算で使用される暗号化データは前記単一のキーによって復号化可能ではない、
請求項１７に記載の暗号化データ保存および演算実行システム。
【請求項１９】
暗号化データ・セットの各々はキーによって暗号化され、
前記少なくとも１つの論理演算は、単一のキーによって復号化可能である前記暗号化結果を生成するために、少なくとも１つのワン・パッドを取り消す、
請求項１７に記載の暗号化データ保存および演算実行システム。
【請求項２０】
前記システムはクラウド・サービス・プロバイダである、請求項１７に記載の暗号化データ保存および演算実行システム。
【請求項２１】
暗号化データ・セットを記憶手段に保存し、
暗号化結果を生成するために前記記憶手段に保存されている前記暗号化データに少なくとも一つの論理演算を実行する、
ことをコンピュータに実行させるためのプログラムであって、
前記暗号化データは対称準同型暗号化によって暗号化されており、
前記暗号化結果は前記暗号化データに対応する単一のキーもしくはキー・セットのいずれかによって復号される、
暗号化データ・セット保存および論理演算実行プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化データへ演算を行う方法およびシステムに関し、より詳細には、暗号化データへの演算の通信、記憶、検索、計算に関する。
【背景技術】
【０００２】
クラウド・コンピューティングを含む処理演算およびデータ・ストレージの様々なトレンドによって、多くの企業がサード・パーティのデータおよびコンピューティング・プロバイダに処理演算ニーズの多くをアウトソースすることを選択するようになってきている。しかしながら、アウトソースされているデータのセキュリティと該データを扱う際の処理演算およびフレキシビリティとの間にはトレードオフがある。したがって、データをまず復号化する必要なく、暗号化されたデータに処理演算を実行することができるように、データを暗号化することが強く所望されている。長年、研究者らはこのような所望を満たす手段を探してきたが、雑多な問題を解決することは困難であった。最近のブレークスルーはこの領域を進展させているが、比較的単純なケースについてさえ、実用的なソリューションを提供するためにはまだ多くの作業がなされなければならない。
【０００３】
準同型（Homomorphic）暗号化はこの問題に対抗するために使用されている技術の一つである。ほとんどすべての準同型暗号化技術はそれらのベースとして非対称（すなわち、パブリック・キー）暗号化を使用する。非対称暗号化は、対称暗号化と比較して、暗号化および復号化にかなり時間を必要とし、セキュリティを実現するために暗号化する間にデータを展開する必要がある。非特許文献１は、ワイヤレス・センサ・ネットワークにおけるデータ集合という事例で、対称暗号化にもとづく準同型暗号化について記載している。非特許文献１に記載されているスキームは、パブリック・キー・ベース・スキームを使用する場合と比較して、短い時間でコンパクトな準同型暗号化を提供する。さらに、非特許文献１のスキームは比較的シンプルなので、強い裏付けをセキュリティに提供することができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】キャステルシアら（Castelluccia et al.）、「ワイヤレス・センサ・ネットワークにおける暗号化データの効率的かつ実証可能で安全な集合（Efficient and Provably Secure Aggregation of Encrypted Data in Wireless Sensor Networks）」、センサ・ネットワークに関するＡＣＭ議事録（ACM Transactions on Sensor Networks）、２００９年、第５巻、第３号、頁２０：１〜２０：３６
【発明の概要】
【発明が解決しようとする課題】
【０００５】
信頼はできるが、好奇心が強いサード・パーティ、例えば、データの収集者、もしくは、サード・パーティ・サービス・プロバイダは、暗号化データを扱うプログラムを実行することについては信頼できるかもしれないが、データ解析について好奇心が強すぎる場合に、当事者が秘密にしておきたいデータから、何かの情報を取得しようとしてしまうかもしれない。
そこで、本発明は、このような場合であっても、より安全性が高い暗号化データを管理する準同型暗号化のためのシステム、方法およびコンピュータプログラムを提供する。
【課題を解決するための手段】
【０００６】
実施形態の一つにおいて、本発明の例示的な実施形態のシステムは、サード・パーティが運営するクラウド・サービス・ネットワーク、もしくは、暗号化データを復号化する能力を有さないプライベート・ネットワークのサード・パーティなどが運営するパブリック・ネットワークに暗号化データを送信する。サード・パーティの運営するネットワーク中のサーバーに暗号化されたデータが保存され、および／または、暗号化されたデータに対して計算処理を実行し、次に、暗号化されたデータおよび実行された計算の結果を、ユーザがデータを復号化し、見ることができるパブリック・ネットワークもしくはプライベート・ネットワークに送信することができる。
【０００７】
本発明の第１の態様は、暗号化データ・セットを保存し、該暗号化データ・セットに論理演算を実行するシステムであって、暗号化データを保存する記憶手段と、プロセッサを有する計算処理手段と、を備え、前記暗号化データは対称準同型暗号化によって暗号化されており、前記計算処理手段は、暗号化結果を生成するために前記記憶手段に保存されている前記暗号化データに少なくとも一つの論理演算を実行するために前記プロセッサを使用し、前記暗号化結果は前記暗号化データに対応する単一のキーもしくはキー・セットのいずれかによって復号化される。
【０００８】
本発明の第２の態様は、第１の態様の暗号化データ・セット保存および論理演算実行システムであって、複数の集合手段をさらに備え、前記複数の集合手段の各々は少なくとも一つのソースから受信したデータ・セットを受信して暗号化し、前記複数の集合手段の各々は、前記記憶手段に暗号化された前記データ・セットを送信する。
【０００９】
本発明の第３の態様は、第１の態様の暗号化データ・セット保存および論理演算実行システムであって、前記対称準同型暗号化はワン・タイム・パッド・ベース準同型暗号化を含む。
【００１０】
本発明の第４の態様は、第１の態様の暗号化データ・セット保存および論理演算実行システムであって、アーカイブ暗号化手段をさらに備え、前記アーカイブ暗号化エンジンは暗号化を実行し、前記記憶手段に暗号化された前記データ・セットを送信する。
【００１１】
本発明の第５の態様は、第２の態様の暗号化データ・セット保存および論理演算実行システムであって、前記複数の集合手段は前記データ・セットを暗号化するためにキーを使用する。
【００１２】
本発明の第６の態様は、第５の態様の暗号化データ・セット保存および論理演算実行システムであって、少なくとも２つの異なるキーが前記データ・セットを暗号化するために前記複数の集合手段によって使用される。
【００１３】
本発明の第７の態様は、第１の態様の暗号化データ・セット保存および論理演算実行システムであって、暗号化された前記データ・セットは少なくとも２つの異なるキーで暗号化されており、前記少なくとも１つの論理演算が実行された場合、単一のキーによって復号化可能な前記暗号化結果を生成するために、少なくとも１つのパッドを取り消す。
【００１４】
本発明の第８の態様は、第１の態様の暗号化データ・セット保存および論理演算実行システムであって、前記暗号化結果は、単一のキーによって復号化可能であり、前記論理演算で使用される前記暗号化データは前記単一のキーによって復号化可能ではない。
【００１５】
本発明の第９の態様は、第６の態様の暗号化データ・セット保存および論理演算実行システムであって、前記少なくとも１つの論理演算は、少なくとも２つの暗号化されたデータ・セットの和を求めることを含む。
【００１６】
本発明の第１０の態様は、第１の態様の暗号化データ・セット保存および論理演算実行システムであって、前記システムはクラウド・サービス・プロバイダである。
【００１７】
本発明の第１１の態様は、サード・パーティ・システムにおいて暗号化データを保存し、該暗号化データに論理演算を実行する方法であって、暗号化データを受信し、前記暗号化データを前記サード・パーティ・システムの記憶手段に保存し、前記サード・パーティ・システムの計算処理手段のプロセッサを使用して、暗号化結果を生成するために少なくとも１つの論理演算を実行し、前記暗号化データは対称準同型暗号化を使用して暗号化され、前記暗号化結果は前記暗号化に対応する単一のキーもしくはキー・セットのいずれかによって復号化される。
【００１８】
本発明の第１２の態様は、第１１の態様の暗号化データ保存および論理演算実行方法であって、暗号化はアーカイブ暗号化手段によって実行される。
【００１９】
本発明の第１３の態様は、第１１の態様の暗号化データ保存および論理演算実行方法であって、集合手段にデータを集合して暗号化し、前記サード・パーティ・システムに暗号化データを送信する、ことをさらに含む。
【００２０】
本発明の第１４の態様は、第１１の態様の暗号化データ保存および論理演算実行方法であって、前記対称準同型暗号化はワン・タイム・パッド・ベース準同型暗号化を含む。
【００２１】
本発明の第１５の態様は、第１１の態様の暗号化データ保存および論理演算実行方法であって、前記暗号化結果は単一のキーによって復号化可能であり、前記論理演算で使用される暗号化データは前記単一のキーによって復号化可能ではない。
【００２２】
本発明の第１６の態様は、第１１の態様の暗号化データ保存および論理演算実行方法であって、前記暗号化データは複数の暗号化されたデータ・セットを含み、前記暗号化されたデータ・セットの各々はキーによって暗号化され、少なくとも１つの論理演算は、単一のキーによって復号化可能な前記暗号化結果を生成するためにデータ・セットの各々を暗号化する際に使用される少なくとも１つのパッドを取り消す。
【００２３】
本発明の第１７の態様は、暗号化データを保存し、該暗号化データに演算を実行するシステムであって、データ記憶手段と、計算処理エンジンと、を備え、前記データ記憶手段は準同型暗号化によって暗号化された複数のデータ・セットを受信し、前記計算処理エンジンは受信した指示にもとづいて処理を実行し、前記処理はプロセッサによって実行され、前記処理は、少なくとも２つの暗号化データ・セットを選択し、暗号化結果を生成するために受信した前記指示にもとづいて選択された前記暗号化データ・セットに論理演算を実行し、前記暗号化結果は前記暗号化データに対応する単一のキーもしくはキー・セットのいずれかによって復号化される。
【００２４】
本発明の第１８の態様は、第１７の態様の暗号化データ保存および演算実行システムであって、前記暗号化結果は単一のキーによって復号可能であり、前記論理演算で使用される暗号化データは前記単一のキーによって復号化可能ではない。
【００２５】
本発明の第１９の態様は、第１７の態様の暗号化データ保存および演算実行システムであって、暗号化データ・セットの各々はキーによって暗号化され、前記少なくとも１つの論理演算は、単一のキーによって復号化可能である前記暗号化結果を生成するために、少なくとも１つのワン・パッドを取り消す。
【００２６】
本発明の第２０の態様は、第１７の態様の暗号化データ保存および演算実行システムであって、前記システムはクラウド・サービス・プロバイダである。
【００２７】
本発明の第２１の態様は、暗号化データ・セットを記憶手段に保存し、暗号化結果を生成するために前記記憶手段に保存されている前記暗号化データに少なくとも一つの論理演算を実行する、ことをコンピュータに実行させるためのプログラムであって、前記暗号化データは対称準同型暗号化によって暗号化されており、前記暗号化結果は前記暗号化データに対応する単一のキーもしくはキー・セットのいずれかによって復号化されることができる。
【００２８】
本発明に関連する他の態様の一部が以下において記載され、他の態様の別の一部は以下の記述から明らかであるか、もしくは、本発明の実施によって習得される。本発明の態様は、複数の構成要素および様々な構成要素の組み合わせ、および、以下の詳細な記述において示される特定の態様によっても実現することができる。
【００２９】
以上および以下の記載は単なる例示であり、本発明および本発明の適用を制限することを意図していない。
【発明の効果】
【００３０】
本発明は、本発明を使用しない場合よりも、データの機密性を高めることができる。
【図面の簡単な説明】
【００３１】
【図１】本発明の例示的実施形態の一つによる暗号化データを管理するためのシステム・アーキテクチャのブロック図である。
【図２】本発明の例示的実施形態の一つによるデータ・ソース・ネットワークのブロック図である。
【図３】本発明の例示的実施形態の一つによるクラウド・サービスのブロック図である。
【図４】本発明の例示的実施形態の一つによるクライアント・ネットワークのブロック図である。
【図５】本発明の例示的実施形態の一つによる暗号化データを管理するためのシステム・アーキテクチャである。
【図６】本発明の例示的実施形態の一つによる、クラウド・サービスで暗号化データを保存し、該クラウド・サービスで暗号化データに演算を実行する方法を示すフロー・チャートである。
【図７】本発明のシステムを実装することが可能なコンピュータ・システムのブロック図を例示する。
【発明を実施するための形態】
【００３２】
以下の詳細な説明において、図面を参照する。図面は例示のためのものであり、限定を意図していない。特定の実施形態および実装は本発明の原理を説明するためのものである。これらの実装は、当業者が本発明を実施することができる程度に十分に記載されており、他の実装も可能である。また、本発明の範囲および思想から逸脱することなく、構造の変更および／または様々な構成要素の置き替えも可能である。それゆえ、以下の詳細な説明は、限定的な意味で解釈されるべきではない。さらに、上記されたように、本発明の様々な実施形態は、汎用目的コンピュータで稼働するソフトウェアの形態で実装されてもよいし、専用ハードウェアの形態で実装されてもよいし、ソフトウェアおよびハードウェアの組み合わせの形態で実装されてもよい。
【００３３】
本発明の実施形態の一つのシステムは、本システムとは別の場所に暗号化されたデータを保存し、別の場所に蓄積されている暗号化されたデータを検索し、別の場所に蓄積されている暗号化されたデータに対して計算処理することを支援するために、非特許文献１に記載されている対称準同型暗号化プロトコルを使用する。すなわち、本発明のこの実施形態のシステムは、蓄積されている暗号化されたデータの任意のサブセットに対する処理拡張するものである。従来の技術は、安全に通信を行う方法の改良であり、狭い帯域制限下にある固定されたデータの集合の処理に限定されていた。具体的には、過去の技術では、データの保存場所については示していない。
【００３４】
実施形態の一つでは、本システムは、「高信頼であるが、好奇心が強い」サード・パーティ、すなわち、暗号化データを扱うプログラムを実行させるには信頼できるが、暗号化データからなにかを取得しようとする程度に十分好奇心が強いかもしれないサービス・プロバイダ、による情報アクセスや収集を防ぐことができる。なお、サード・パーティは、暗号化されたデータの主たる利用者であるプライマリ・パーティの少なくとも一つと同じ組織に属する別のグループであってもよいし、サービス・プロバイダなどの外部のエンティティであってもよい。本発明の実施形態の目標の一つは、様々な統計的論理的クエリに対する回答の処理をサードパーティ（サービス・プロバイダ）に支援させながら、データについての何らかの情報を、好奇心が強いサードパーティ(サービス・プロバイダ)に取得させないことである。
【００３５】
「擬似ランダム関数」（Pseudo random functions）
擬似ランダム関数ファミリは、セキュリティ・パラメータλによって添字付けされる関数Ｆλ＝｛ｆｓ｝の集合である。関数ｆｓはλビットからλビットへの関数ｆｓ：｛０，１｝λ→｛０，１｝λである。擬似ランダム関数(PRF)の暗号化グレードは、関数の多くの値を多角的に見ることは任意のさらなる値を予測するためには些細な支援としかならない、という特性を有する。実証可能でかつ安全なPRFが存在するが、それらは実用的にはあまりにも処理速度が遅くなる。代わりに、本発明の実施形態は、HMAC（Hash-based Message Authentication Code）などの鍵付きハッシュ関数を使用する。ランダム性およびセキュリティを改善するために、鍵付きハッシュ関数を、たとえば、ｆｓのλビット出力を長さμのサブストリングに分割し、合計する、非暗号グレード・ハッシュ関数と組み合わせることができる（ｈ：｛０，１｝λ→｛０，１｝μ）。一般に、ハッシュ関数ｈは一様な出力分布を有するが、衝突耐性（同じハッシュ値を有する異なる２メッセージの生成が十分に困難であること）を有する必要はない。
【００３６】
「ワン・タイム・パッド・ベース対称準同型暗号化スキーム」
このセクションは非特許文献１のワン・タイム・パッド（乱数鍵を１回だけ使用する暗号の運用方法）・ベース・スキームについて説明する。このスキームはシンク（受信データ蓄積装置）を有するセンサ・ネットワークのためのものである。
【００３７】
「セットアップ」：
Ｍ＞Ｎ＊Ｔを選択する。Ｎはセンサの数であり、Ｔは考えられるセンサ値の数である。説明を簡単にするために、すべてのセンサの考えられるセンサ値の数が同一であると仮定する。一様でない場合のスキームへの適応は容易である。メッセージはｍビット・ストリングとして符号化される。ｎ＝ｌｏｇ（Ｎ）についてｍ＝ｌｏｇ（Ｍ）＝ｎ＋ｔであり、ｔ＝ｌｏｇ（Ｔ）である。擬似ランダム関数ファミリＦλ＝｛ｆｓ：｛０，１｝λ→｛０，１｝λ｝が設定され、λ値が所望されるセキュリティ・プリファレンスに応じて選択される。実施形態の一つにおいて、値をλ＝８０とすることは高いセキュリティを取得するために一般的な選択である。ハッシュ関数ｈ：：｛０，１｝λ→：｛０，１｝ｍも設定される必要がある。このハッシュ関数は暗号的に安全な関数である必要はない。すなわち、衝突耐性を有する必要はないが、一様な入力に対して一様な出力を有することだけは必要とする。最後に、ノンス・スキームは、ノンス（Number used once一回だけ用いられる番号）が秘密もしくはランダムである必要はないが、循環すべきではない、ことを承認すべきである。ノンスを設定するための一般的な方法はタイム・スタンプとして設定することである。
【００３８】
「鍵生成」：
ランダムλビット・ストリングＫをシンクのためのキーとして選択することができる。各々のセンサ・ノードｉ(所望のセンシングを行うための処理装置のうちノードｉにあたる装置)はシンクから暗号化キーｅｋｉ＝ｆＫ（ｉ）を受信する。
【００３９】
「暗号化」：
メッセージｍｉはｃｉ＝ｍｉ＋ｈ（ｆｅｋｉ（ｒ））  ｍｏｄ  Ｍとしてノードｉによって暗号化される。ｈ（ｆｅｋｉ（ｒ））は、パッド（保存されたデータ）として参照される。ノードＩＤ  ｉを含むヘッダーが送信され、次に暗号文ｃｉが送信される。
【００４０】
「集合」：
ノードは、ｍｏｄ  Ｍを求め、加算することにより、暗号文セットを集合化して、集合暗号文ｃを得る。
【００４１】
「復号化」：
１以上の暗号文の集合の復号は３つのステップで行うことができる。ヘッダーから、集合に寄与するノードＩＤを決定する。これらのすべてのＩＤのパッドが、ｈ、擬似ランダム関数、ノンスを用いて計算処理される：ｈ（ｆｅｋｉ（ｒ））  ｍｏｄ  Ｍ。パッドのすべてを加算し、集合暗号文ｃから減算すると、対応する平文メッセージｍｉの合計ｍとなる。
【００４２】
このスキームのセキュリティは、擬似ランダム関数ファミリＦλのセキュリティに依存する。同様のアプローチを、倍数型準同型スキームを生じるために使用することができる。残念ながら、２つのスキームは同様の暗号化を行わないので、完全な準同型スキームを生じるために該２つのスキームをまとめることはできない。
【００４３】
「例示的なシステム・アーキテクチャ」
本発明の実施形態の一つの高レベル・システム・アーキテクチャについて説明する。この実施形態において、システムのある部分はプライベート・ネットワーク上にあり、ある部分はパブリック・インターネット上にあり、ある部分はクラウド・サービスなどのサード・パーティの運営するシステム上にある。
【００４４】
図１は、本発明の実施形態の一つによって、暗号化データを保存し、検索し、計算処理するための手段を提供する準同型暗号化システムの基本的なアーキテクチャを例示する。データ・ソース・ネットワーク１００のデータ・ソースは、クラウド・サービス１０１に暗号化されたデータを送信する。クラウド・サービス１０１は暗号化されたデータを保存し、クライアント１０２からの要求にもとづいて暗号化されたデータに論理演算を行うことができる。クライアント１０２およびデータ・ソースの双方に暗号化キーを送出するために、キー・サーバ１０３を使用してもよい。
【００４５】
図２は本発明の実施形態によるデータ・ソース・ネットワークを例示する。データ・ソース・ネットワーク１００はパブリックであってもよいし、プライベートであってもよい。未処理データ・ソース２００は考えられるメタ・データ（ソースＩＤ、タイムスタンプなど）とともに未処理データを集合手段２０１に送信する。データ・ソース・ネットワーク１００における通信は何らかの方法により安全である。たとえば、データ・ソース・ネットワーク１００は安全なプライベート・ネットワークの一部であってもよいし、データを搬送するチャネルが物理的に安全であってもよいし（たとえば、物理的に安全な領域内の短距離ワイヤレス信号など）、通信が暗号化されていてもよい。データ・ソース・ネットワーク１００における通信チャネルを安全にするいくつかの方法があるが、重要なことは、通信がこのポイントで安全であるか否かだけであり、安全にするための方法ではない。
【００４６】
実施形態の一つにおいて、集合手段２０１は未処理データを受信し、保存を必要とするものだけを送信するように、該未処理データを処理する。たとえば、センサからのビデオ・フィードを処理する集合手段は、未処理ビデオ・ストリームではなく、観察されたふるまい／イベントの記述だけを送信してもよい。集合手段２０１によるこの処理は、センサの未処理データが意図しない目的のために使用されないようにすることにも有効である。集合手段２０１がセンサ情報を処理すると、準同型暗号化スキームを用いて処理されたデータを暗号化し、以下で説明するように、クラウド・サービスなどのサード・パーティのシステムに対してヘッダーとともに送信する。
【００４７】
図２に示されるように、キー・サーバ１０３は、データを暗号化および復号化するために使用されるマスター・キーを生成する。実施形態の一つにおいて、キー・サーバ１０３は暗号化キーｅｋｉを集合手段２０１の各々に配布する。さらに、キー・サーバ１０３は、プライベート・ネットワークの複数の計算処理エンジン４００（計算処理手段）にマスター・キーもしくは暗号化キー・セットを配布してもよい（図４）。マスター・キーもしくは暗号化キー・セットから、プライベート・ネットワークの計算処理エンジンは復号化パッドを求めることができる。キー・サーバ１０３は、さらに、プライベート・ネットワークの外部の任意のクライアントの計算処理手段にマスター・キーもしくは暗号化キー・セットのいずれかを配布する。代替的に、データのすべてを暗号化するアーカイブ暗号化エンジン（アーカイブ暗号化手段）を使用するなどの集中化された手法で、暗号化がなされてもよい。暗号化エンジンは異なるデータに異なるキーを使用してもよい。
【００４８】
図３は、本発明の実施形態によるクラウド・サービス１０１およびクラウド・サービス１０１に含まれるコンポーネントを例示する。フィード・サーバ３００は、データ・ソース・ネットワーク１００の集合手段から提供される暗号化データおよびクライアント１０２からのクエリなどのデータ・フィードを受信する。フィード・サーバ３００は、暗号化データ記憶手段３０１などのデータ・ストレージ・ユニットに集合手段から提供される暗号化データを送信する。フィード・サーバ３００はクライアント１０２から計算処理エンジン３０２へクエリを送信してもよい。
【００４９】
暗号化データ記憶手段３０１は、暗号化データと該暗号化データのメタデータを保存する。計算処理エンジンによって実行された計算処理の結果を、暗号化データ記憶手段３０１に保存してもよい。クラウドの計算処理エンジン３０２は暗号化データへの処理を実行し、クライアント１０２に送信されるべき結果をフィード・サーバ３００に戻す。計算処理エンジン３０２は、クエリに応答するために実行される必要がある処理のどの部分を暗号データに行うことができるのか、どの部分をクライアントによる復号化の後に実行する必要があるか、を決定してもよい。クラウド・サービスはキー・サーバ１０３からキーを受信せず、したがって、暗号化データを復号化することができないので、この決定は必須である。代替的に、この決定はクライアントによって行われてもよい。計算処理エンジン３０２は、暗号化データへ行われた処理の結果を保存するキャッシング・ストラテジー(caching strategy)を実行することに関与してもよい。
【００５０】
図４は本発明の実施形態のクライアント・ネットワーク１０２を例示する。クライアント・ネットワーク１０２はパブリックであってもよいし、プライベートであってもよい。クライアント・ネットワーク１０２がプライベートならば、プライベート・ネットワーク・レベル計算処理エンジン４００はクラウド・サービスの計算処理エンジン３０２から提供される暗号化された処理結果を受信してもよい。該処理結果は、フィード・サーバ３００を介してプライベート・クライアント・ネットワーク１０２へ渡される。プライベート・ネットワーク・レベル計算処理エンジン４００は処理結果を暗号化し、実施形態の一つにおいては、該処理結果に他の計算処理を実行してもよい。処理結果は、次に、少なくとも一のユーザに提示するために、クライアント・インタフェース４０１に渡される。実施形態の一つにおいて、複数のプライベート・ネットワークがあるならば、複数の計算処理エンジンがあってよい。クライアント・インタフェース４０１は、クラウド・サービス１０１もしくはクライアント・ネットワーク１０２へ、データに関連するクエリをユーザに入力させることができる。クライアント・インタフェース４０１は、さらに、少なくとも一のユーザにクライアント計算処理手段４０２から受信した情報を提示する。実施形態の一つにおいて、クライアント計算処理手段４０２が備えられていてもよい。クライアント計算処理手段４０２はクエリのソースとして動作してもよいし、クラウド・サービスの計算処理エンジン３０２が当該決定をしていない場合、クエリに回答するために必要とされる計算処理のどの部分が暗号化データに実行されることができるか、を判断してもよい。
【００５１】
他の実施形態においては、システム・アーキテクチャはよりシンプルであってよく、複数のコンポーネントが一つのネットワークもしくは一つのエレメントの中にあってもよい。たとえば、同一のネットワークの内部であるだけでなく、同一のネットワーク・エレメントの内部に未処理データ・ソース、集合手段、およびクライアント・インタフェースが配置されていてもよい。
【００５２】
図５は本発明の実施形態の一つのシステム・アーキテクチャを例示している。詳細には、データ・ソース・ネットワークは、プライベート高信頼データ・ソース・ネットワーク１００Ａであってもよいし、パブリック・データ・ソース・ネットワーク１００Ｂであってもよい。これらのデータ・ソース・ネットワークのどちらかが、対称準同型暗号化プロトコルを用いて未処理データを暗号化するために集合手段２０１を使用する。サード・パーティ・クラウド・サービス・ネットワーク１０１は、フィード・サーバ３００で暗号化データを受信する。上記したように、フィード・サーバ３００は暗号化データを暗号化データ記憶手段３０１に保存する。図５に例示されている実施形態は、クライアント・ネットワークが、どのようなプライベート高信頼クライアント・ネットワーク１０２Ａであり、どのようなパブリック・クライアント・ネットワーク１０２Ｂであるか、を示している。さらに、キー・サーバ１０３は、プライベート高信頼ネットワーク１００Ａ、１０２Ａおよびパブリック・ネットワーク１００Ｂ、１０２Ｂにキーを提供する別個の高信頼ネットワークの中に示されている。しかしながら、キーはサード・パーティ・クラウド・サービス・ネットワーク１０１に提供されない。
【００５３】
図６は、本発明の実施形態の一つの暗号化データに論理演算を行う方法を例示するフロー・チャートである。まず、システムは準同型暗号化によって暗号化された複数のデータを受信する（６００）。次に、システムは、データ・ストレージ・システム（記憶手段）に複数の暗号化データを送出する（６０１）。計算処理を実行するためにクライアントから指示を受信し、該指示を処理すると（６０２）、システムは暗号化データの選択されたセットに論理演算を行う（６０３）。生成された結果は、次に、クライアントに送信される。
【００５４】
図７は、コンピュータ／サーバ・システム７００を例示しており、コンピュータ／サーバ・システム７００に本発明の実施形態を実装することができる。システム７００は、プロセッサ７０２およびメモリ７０３を含む、コンピュータ／サーバ・プラットフォーム７０１を含み、コンピュータ／サーバ・プラットフォーム７０１は、指示を実行するために動作する。ここで使用される用語「コンピュータ可読媒体」は、実行のためにプロセッサ７０２に指示を提供することに関与する任意の媒体を示す。さらに、コンピュータ・プラットフォーム７０１は複数の入力手段７０４（キーボード、マウス、タッチ・デバイス、言葉による指示を入力する装置、など）から提供される入力を受信する。コンピュータ・プラットフォーム７０１は、脱着可能な記憶手段７０５（ポータブル・ハード・ディスク・ドライブ、光媒体（ＣＤもしくはＤＶＤ）、ディスク媒体、コンピュータが実行可能なコードを読み込むことができるその他の媒体、など）にさらに接続されていてもよい。コンピュータ・プラットフォーム７０１は、さらに、ネットワーク・リソース７０６に接続されていてもよく、ネットワーク・リソース７０６は、インターネット、もしくは、ローカル・パブリック・ネットワークまたはプライベート・ネットワークのその他のコンポーネントに接続されていてもよい。ネットワーク・リソース７０６は、ネットワーク７０７上のコンピュータ・プラットフォーム７０１と離れた位置からコンピュータ・プラットフォーム７０１に命令およびデータを提供してもよい。ネットワーク・リソース７０６への接続は、８０２．１１規格、ブルートゥース、もしくはセルラ・プロトコル(cellular protocols)などのワイヤレス・プロトコルを介していてもよいし、ケーブルまたはファイバー・オプティクスなどの物理的伝送を介していてもよい。ネットワーク・リソース７０６は、コンピュータ・プラットフォーム７０１とは分離した位置にデータおよび実行可能な指示を記憶するための記憶手段を含んでいてもよい。コンピュータは、データおよびその他の情報をユーザに対して出力（表示）し、ユーザに追加情報を要求し、ユーザが何らかの情報を入力することができるようにするために、表示手段７０８とインタラクションを行う。表示手段７０８は、ユーザとインタラクションを行うために、入力手段７０４として動作してもよい。
【００５５】
「システム・エレメント間のインタラクション」
上記された本発明のセンサ・ネットワークの実施形態において、興味深いシステムの要素は、集合手段、計算処理エンジン、および、クライアントの間の（間接的）インタラクションである。
【００５６】
実施形態の一つは、非特許文献１のワン・タイム・パッド・ベース対称準同型暗号化スキームにもとづいている。１つより多くのエンティティが復号化パワーを有し、暗号化値を記憶し、様々なクエリによって問い合わせをし、暗号化値について回答する、という点で、この実施形態で使用されているスキームは、非特許文献１のスキームとは異なる。さらに、キー構造がアクセス制限を実施するために使用される。
【００５７】
この実施形態において、キー・サーバ１０３は一般復号化キーＫをランダムに選択し、集合手段が関与する（図示されない）各センサのキーｅｋｉを各集合手段２０１に送信する。代替的な実施形態では、各集合手段２０１が多くのセンサに関与する場合、各集合手段２０１は単一の暗号化キーｅｋｓを与えられ、センサＩＤがノンスに含まれてもよい。プライベート・ネットワークの外部のクライアントのいくつかは、一般復号化キーＫを与えられ、その他のクライアントは該クライアントがアクセス権を有するセンサに対応するキーだけを与えられてもよい。同様に、各プライベート・ネットワークの計算処理エンジンは一般キーもしくはキー・サーバ１０３から提供される暗号化キー・セットのいずれかを受信する。
【００５８】
集合手段２０１はセンサ・データを暗号化するためにキーを使用する。より効率的でよりパワフルな暗号化データへの処理が可能となるように、データは複数の形態で暗号化されることがある。たとえば、暗号化値の加算を促進するために加算指向(additive)対称準同型暗号化を用いてデータを暗号化してもよいし、暗号化値の乗算を促進するために乗算指向(multiplicative)対称準同型暗号化を用いてデータを暗号化してもよい。その他の例として、データ値の二乗が分散計算をサポートするために暗号化されてもよい。集合手段２０１はフィード・サーバ３００に暗号化センサ・データを送信し、フィード・サーバ３００は記憶手段に暗号化値を保存する。
【００５９】
実施形態の一つにおいて、クラウド計算処理エンジン３０２は現在行われているスタンダード・クエリを記憶し、積極的に計算し、効率的な集合データを送信する。集合データはクエリに回答するために計算処理エンジンによって使用される。クライアント１０２は、場合によっては、プライベート・ネットワーク計算処理エンジン４０２による処理の後、クエリを生成してもよい。クエリは、クラウドの計算処理エンジン３０２にフィード・サーバ３００によって送信される。クラウドの計算処理エンジン３０２は暗号化データを使用して可能な限り多くのクエリを処理し、プライベート・ネットワーク計算処理エンジン３０２に計算結果を戻す。プライベート・ネットワーク計算処理エンジン３０２は、提供されたキーを用いて、クライアント・クエリについての完全な回答を取得するためにデータを復号化し、暗号化されていないデータをさらに処理する。
【００６０】
暗号化データを用いて計算することができる量を示す上記実施形態による例を以下に示す。
【００６１】
「暗号化データへの計算処理」
以下に記載されるように、上記システムは計算処理されるデータを合計することができる。上記センサ・ネットワークの実施形態において、センサ・データは加算指向準同型スキームによって暗号化されていなければならない。クライアント１０２は、クライアント１０２が合計を所望するデータのサブセットを示す式(expression)をクラウド・サービス１０１に送信する。クラウド・サービス１０１は、暗号化されたデータ・エントリの合計を計算し、合計を暗号化してクライアント１０２に戻す。一方、クライアント１０２は、関心を有するデータ・ポイントに対応するパッドの合計を計算し、クラウド・サービス１０１から暗号化された合計を受信すると、暗号化された合計から計算されたパッドの合計を減算する。同様に、クラウド・サービス１０１は、暗号化された値の加重平均を計算することができ、パッドの加重平均を減算することにより、クライアント１０２は復号化された加重平均を復元することができる。このシステムはクライアント・マシンが実行しなければならない計算量を低減しないかもしれない。しかしながら、暗号化の観点で、高信頼であるが、好奇心の強いサード・パーティから安全などこかに大量のデータを蓄積することができる。このシステムは、計算処理されるべきデータ全体で統計の暗号化を可能にする。
【００６２】
データのサブセットの合計を取得するための機能が、関連する量の計算処理を即時にサポートする。すなわち、１）データのサブセットの合計を計算する、２）データのサブセットで「論理和」を求める、３）データのサブセットの平均を計算する、４）データの加重平均を計算する。
【００６３】
たとえば、センサ・データのサブセットで「論理和」を求める場合、特定のセンサ読み込みセットのいずれかが、異常を示すことができる非ゼロであるか否かを知ることが所望されるかもしれない。クライアントがキーの合計を減算することによってデータを復号化した後、合計が非ゼロであれば異常があり、さらなる調査が必要である。ゼロ値合計はすべてが良好であることを示す。
【００６４】
データのサブセットの平均を計算する場合、クライアントがサブセットの値の数Ｎを知っていれば、クライアントはＮによって合計を除算することによって平均を計算することができる。エントリＮの合計数はクライアントによって既に知られていてもよいし、クラウドによってクライアントに送信されてもよい。
【００６５】
データの加重平均を計算する際に、加重平均に寄与する様々なデータ・ポイントの重みから、クライアントはパッドの加重平均を計算することができ、次に、暗号化されていない加重平均を取得するために、クラウド・サービスによって戻される値からパッドの加重平均を減算することができる。
【００６６】
パッドを加える代わりに、パッドを乗じることによって暗号化することは、暗号化値の乗算および幾何学的合計などのエンティティの計算をサポートする乗算指向準同型暗号化スキームを生成する。
【００６７】
「他の計算処理」
加算および乗算の組み合わせは、複数のクエリおよびクライアントの部分のいくつかの計算処理を用いることによって取得されることができる。クエリの数および計算処理の量は式による。加算および乗算の組み合わせを含めることは通信および計算処理費用の観点からは効率的でないかもしれない。いくつかの実施形態において、加算情報はそのような計算処理を可能にするために暗号化される。多くの有用なクエリを、簡易に、かつ、効率的に、求めることができる。たとえば、分散および標準偏差は、センサが値ｍｉとともに、値ｍｉの二乗を計算し、暗号化し、送信するならば、暗号化データによって効率的に計算することができる。Ｖａｒｉ＝Σｍｉ２／ｎ−Ａｖｅ２。これらの暗号化値は、記憶手段の要求に加えて、クラウド・サービスでも保存されていなければならない。システムは、同時に、加算指向準同型および乗算指向準同型の双方ではないため、これらの値を分離して記憶することが必要とされる。他の実施形態では、その他のモーメントが類似した方法で他の暗号化データから求められる。さらに、多くの計算が初期ステップとして、値の加算もしくは平均を必要とする。これらの初期の計算は、暗号化データに対してクラウド・サーバによって行われる。次に、クライアントはデータを復号化し、計算処理を終了することができる。クラウド・サービスとクライアントとの間で負荷を分割することは作業の適用をかなり拡張する。
【００６８】
「効率的な復号化および複雑なアクセス・コントロール」
すでに記述したように、クライアントがデータのどの部分にアクセスすることができるか、を制御することを、システムはサポートする。しかしながら、より複雑な制御を達成することもできる。たとえば、集合手段の各々に少しだけ作業を増加するように求めることによって、クライアントは、その成分のどれかではなく、合計を復号化することができる。この実施形態はサブデータへのクライアントのアクセスを制限するが、クライアントの復号化処理速度は向上し、擬似ランダム関数への呼び出し回数を低減する。以下は、１つのクライアントとＬ個の集合手段による上記スキームがどのように作用するかを例示する。集合手段の各々は一つの値ｖｉを暗号化する。
【００６９】
キー・サーバは、キーｋ０をクライアントに、キーｋｉおよびｋｉ−１を集合手段Ａｉに送信する（0 < i < L）。キーｋＬ−１は集合手段ＡＬに送信される。
【００７０】
最後の集合手段ＡＬを除いて、集合手段Ａｉの各々は、キーｋｉについてｖｉからｈ（ｆｋ（ｒ））を減算し、キーｋｉ−１についてｈ（ｆｋ（ｒ））を加算することによって値ｖｉを暗号化する。最後の集合手段ＡＬはキーｋ＝ｋＬ−１について値ｈ（ｆｋ（ｒ))を加算するだけである。
【００７１】
暗号化値セットの全体を合計する場合、キーｋ＝ｋ０のｈ（ｆｋ（ｒ））を除いて全ての項(term)を消去する。クライアントはキーｋ０を有しているので、合計を復号化することができる。クライアントは他のキーを有していないので、個々の暗号化値ｖｉはもちろん、任意の小計を復号化することはできない。すなわち、この復号化を実行するために、クライアントはキーｋ＝ｋ０についての一つの項ｈ（ｆｋ（ｒ））だけを計算する必要がある。したがって、この実施形態において、復号化はより効率的である。
【００７２】
同様のアプローチを、その他のより複雑なアクセス・コントロールを取得するために使用することができる。その他の実施形態において、各々が各々の集合手段によって暗号化される４つのセンサ値と３つのクライアントＣ１、Ｃ２、Ｃ３がある。目標は、どのクライアントも個別の値を復号化することができないことを確実にすることである。この実施形態において、クライアントＣ１はすべての値の合計を復号化することができるだけであり、クライアントＣ２は２つの完全な合計および２つの値の２つの小計を復号化することができ、クライアントＣ３は２つの値の小計の１つを復号化することができる。この状況は以下のように取り扱われる。
【００７３】
キー・サーバはクライアントＣ１にキーＫを送信し、クライアントＣ２にキーＫおよびｋ１を送信し、クライアントＣ３にキーｋを送信し、キーＫ、ｋおよびｋ１を集合手段Ａ１に送信し、キーｋ１を集合手段Ａ２に送信し、キーｋおよびｋ２を集合手段Ａ３に送信し、キーｋ２を集合手段Ａ４に送信する。
【００７４】
集合手段Ａｉの各々は、列挙された第１キーｋについてｈ（ｆｋ（ｒ））を加算し、集合手段Ａｉの各々が有する他のキーについてｖｉからｈ（ｆｋ（ｒ））を減算することによって、値ｖｉを暗号化する。
【００７５】
暗号化値セットの全体を合計する場合、キーｋ＝Ｋについてｈ（ｆｋ（ｒ））を除く項のすべてを消去する。クライアントＣ１およびＣ２は双方ともこの合計を復号化することができる。クライアントＣ２はキーｋ１を有するので、最初の２つのセンサ値の合計を復号化することもできる。クライアントＣ３はキーｋを有するので、最後の２つのセンサ値の合計を復号化することができる。
【００７６】
これらの実施形態は、集合手段毎に複数のセンサ値があり、小計階層により多くのレベルがあり、センサ値、集合手段、クライアントの数がより多い場合にまで拡張することができる。
【００７７】
「適用例」
上記実施形態について多くの可能な適用領域があるが、その内の２つについて以下で例示する。以下の例示は工場センサ・データおよびアウェアネス(awareness)・データに関連する。その他の適用は、会計データ、顧客データ、医療記録、ユーザ学習データを含むが、本発明はこれらのデータに限定されるものではない。これらの例は、本発明の実施形態の一つによるシステムの様々な特性を示すが、これらは例示に過ぎず、様々な他の実施形態がその他の多くの適用を有する。
【００７８】
例１：工場監視（ブール・ケース(Boolean case)）
目標：何かが間違っていることをセンサ・データが示唆するならば工場管理者の注意を喚起する。詳細には、適正な範囲外のセンサ値が警報のきっかけとなる。
【００７９】
製造プロセスにおいてもっとも注意を要する重要なことの一つは、プロセス全体にわたって非常に正確な温度制御を維持することである。さらに、プロセスにおける異なるポイントでの理想温度設定は往々にして秘密に保持されているプロプライエタリな知識である。したがって、温度センサは、温度が適正な範囲内にあることを確認するために常に監視されていなければならない。 
【００８０】
セットアップ：Ｍ個のセンサがあると仮定する。ｍをＭ＜２ｍである最小の整数とする。
【００８１】
センサｉの各々は、自身の集合手段に自身の値を送信する。センサ値ｍｉはｐビットによって所望される精度で示すことができる。
【００８２】
集合手段は各センサからの値についての適正な範囲を保存する。適正な範囲は一定であってもよいし、時間に依存してもよいし、特定の時間に実行されているプロセスに依存してもよい（この場合、プロセスＩＤおよび開始時間を集合手段に伝送しなければならない）。集合手段はキー・サーバから擬似ランダム関数キーｅｋｉも受信する。集合手段は、センサ値が適正な範囲にある場合、０であるブール値ｂｉを生成し、センサ値が適正な範囲にない場合、１であるブール値ｂｉを生成する。キー・サーバおよび集合手段のすべては、（出力が一様であればよく、セキュリティ・グレードであることは必要としない）２つのハッシュ関数を承諾する。ｈｂ：｛０，１｝λ→｛０，１｝ｍ、ｈｘ：｛０，１｝λ→｛０，１｝ｐビット
【００８３】
ノンスｒ＝ｒ（ｔ，ａ，σ）は、タイム・スタンプｔ、値のタイプ（ブール値もしくは未処理センサ値）を示す符号ａを含み、ノンスが長さλを満たすために付加的なストリングσを必要とするかもしれない。
【００８４】
集合手段はブール値ｂｉをｃｂｉ＝ｂｉ＋ｈｂ（ｆｅｋ（ｉ）（ｒ（ｔ，１，σ）））  ｍｏｄ  Ｍとして、未処理センサ値ｍｉをｃｘｉ＝ｘｉ＋ｈｘ（ｆｅｋ（ｉ）（ｒ（ｔ，０，σ）））  ｍｏｄ  Ｐとして暗号化する。Ｐ＝２ｐである。ｈｂ（ｆｅｋ（ｉ）（ｒ（ｔ，１，σ）））およびｈｘ（ｆｅｋ（ｉ）（ｒ（ｔ，０，σ）））は、予め、すなわち、センサ値を受信する前に、計算することができる。
【００８５】
集合手段は、フィード・サーバに、ストリング、該ストリングのノードＩＤ、暗号化ブール暗号文ｃｂｉ、暗号化センサ値ｃｘｉの連鎖(concatenation)を送信する。
【００８６】
計算処理エンジンは複数の固定クエリ(standing queries)を有する。たとえば、計算処理エンジンは、あるプロセスの暗号化ブール値のすべてのｍｏｄ  Ｍを求め、加算し、ｃｐｊとして一時的に保存してもよい。次に、ある工場の暗号化されたプロセスの合計のすべてのｍｏｄ  Ｍを求め、加算し、ｃｆｋとして保存してもよい。最後に、これらのすべてのｍｏｄ  Ｍを求め、加算し、ｃＴとして保存してもよい。次に、これらの和をフィード・サーバに送信する。実施形態の一つでは、これらの和は適切なパーティのモバイル・デバイスにさらに送信される。たとえば、いくつかの工場を管理するチーフ・オペレーティング・オフィッサーは暗号化された最終合計を受信し、次に、暗号化された工場の合計を受信し、さらにその次に、暗号化されたプロセスの合計を受信してもよい。工場の管理者は管理者自身の工場の合計だけを受信し、次に、この工場におけるプロセスのプロセス合計を受信してもよい。プロセス管理者はプロセスの合計だけを受信することができる。
【００８７】
実施形態の一つにおいて、監視モードがオンである場合、モバイル・デバイスはモバイル・デバイスの所有者が指定する固定クエリの各々についての次のステップのために２つのワン・タイム・パッドを計算する。ｈｂ（ｆｅｋ（ｉ）（ｒ（ｔ，１，σ）））、ｈｘ（ｆｅｋ（ｉ）（ｒ（ｔ，０，σ）））モバイル・デバイスは、次に、各クエリについてのパッドのｍｏｄ  Ｐおよびｍｏｄ  Ｍを求め、各々合計する。たとえば、工場管理者は工場の各プロセスに対応するパッドのすべてを加算し、該合計をｈｐｊとして保存し、該合計をすべて加算し、この合計をｈｆｋとして保存してもよい。
【００８８】
暗号化センサ値を受信すると、モバイル・デバイスは、ｃｆｋ  ｍｏｄ  Ｍからｈｆｋを減算することにより、最大レベル・ブール合計、工場管理者の場合における工場合計を復号化する。合計がゼロである場合、すべてのセンサは適正な範囲にあり、モバイル・デバイスはこれ以上何もしない。合計がゼロでない場合、モバイル・デバイスは警報を登録し、どのプロセスが通常範囲を越えるセンサ値を有するのか、を見つけるためにプロセス合計を復号化することによってより多くの情報を集めるプロセスを開始する。モバイル・デバイスは、次に、このプロセスについてセンサ値のすべてを要求するフィード・サーバにクエリを送信し、センサ値を受信すると、ユーザにグラフィックを用いてセンサ値を提示する。モバイル・デバイスもしくはユーザは、以降の時間ステップにおけるこのプロセスについてのより多くの情報を取得するために、固定クエリを変更してもよい。
【００８９】
「非準同型暗号化システムとの比較」
本発明の実施形態によるシステムを使用することによって、ブール値はｍビット・ストリングとして暗号化される。ブール値の暗号文は非準同型暗号化スキームにおいてはより小さくなるかもしれないが、クライアントは、要約値だけでなくすべてのデータを受信しなければならない。したがって、クライアントは、各期間、各センサについてＭビットを受信する。結果的に、クライアントが関心を有する合計毎に、クライアントが受信するｍビットよりも受信するデータは大きくなる。クライアントは、予め、パッドの合計を計算することができるので、本発明の実施形態において使用されるシステムの処理はより迅速となり、帯域幅の負荷も低減することができる。暗号化値の合計を計算し、合計を送信するためのサーバの処理時間も値のすべてを送信する時間よりも短縮される可能性がある。工場監視の場合、センサ値が範囲外となり、クライアントが未処理値を要求する事象が増加すると、この実施形態が有するシステムの効果は小さくなる。最終的に、個々の値はこの実施形態では復号化されないので、より安全である。たとえば、工場監視の場合、個々のセンサ値は、問題が検出された場合を除いて、集合手段によって暗号化された後は見られることがない。したがって、この実施形態は、帯域幅、速度、セキュリティについて優位性を有する。
【００９０】
「パブリック・キー・ベース準同型システムとの比較」
ＲＳＡなどの決定論的パブリック・キー暗号化スキームは意味論的セキュリティ(semantic security)を達成することができない。ＯＡＥＰを用いたＲＳＡの確率的変動(probabilistic variants)は準同型ではない。もっともよく知られている準同型である確率的パブリック・キー暗号化スキームはエル・ガマルである。したがって、エル・ガマルを比較のために使用する。エル・ガマルは大きな素数Ｐを選択することを必要とする。必要とされる長さは所望されるセキュリティに依存するが、一般にＰは少なくとも１０２４ビットの長さとされる。暗号文は２つの部分を有し、各々は整数  ｍｏｄ  Ｐである。このように、ブール値についてでさえ、暗号文は少なくとも２０４８ビットの長さを有する。非常に大量のセンサを使用する場合でなければ、使用される暗号文のサイズはエル・ガマルによって使用される暗号文のサイズより数桁小さい。その他の準同型暗号化スキームはその他の様々な効率のトレードオフを有し、そのすべては比較的長い暗号文を有する。暗号化、復号化、および暗号文の結合のすべての処理は、実質的に本発明の実施形態のスキームより遅い。なぜならば、暗号文がより長く、暗号化および復号化の双方が（計算の負荷が大きい）累乗法を使用するからである。さらに、すべてが一つのパブリック・キーで暗号化されるので、いずれかのデータを復号化することができる個々は、すべてのデータを復号化することができる。反対に、本発明の実施形態は各センサに異なるキーを使用して、個々が復号化することができるデータを限定する手段を提供し、一方で、異なるキーによって暗号化されるデータ全体への計算処理をサポートする。この能力は、プロキシ再暗号化によってパブリック・キー・スキームに付与されることができるが、スキームの複雑さは実質的に増加する。すなわち、本発明の実施形態のシステムは帯域幅について、より効率的であり、より迅速に暗号化、復号化を行うことができ、より柔軟に暗号文結合を行うことができる。スキームをさらに複雑にすることなく、目的に適合したデータへのアクセスもサポートする。
【００９１】
例２：工場改善計画
目標：プロセスのどの部分が理想値からのずれがもっとも大きいか、および、どの部分がもっとも大きい分散を有するかを決定する。
【００９２】
例１で記載したように、製造プロセスにおいて適正な範囲に温度を維持することは重要である。熱損失がどこで生じるか、もしくは、熱い部分もしくは冷たい部分がいつ、どこに現れるか、を知ることは重要である。これを達成するために、時間に沿って変化を追跡することが必要である。どの部分が理想値からそれ、どの部分が大きい分散を有するかを判断することによって、プロセスの部分を改善し、もしくは置換するために、どの部分に最大の努力を払えばよいかを、工場管理者が決心することが可能となる。
【００９３】
プロトコル：統計は最大Ｔ個の異なる期間にわたって求められると仮定する。ｔはＴ＜２ｔとなる最小の整数である。
【００９４】
センサｉの各々は自身の値を自身の集合手段に送信する。センサ値ｍｉはｐビットの所望される精度で示されることができる。
【００９５】
集合手段はキー・サーバから擬似ランダム関数キーｅｋｉを受信する。
【００９６】
ノンスｒ＝ｒ（ｔ，ｖ，σ）はタイム・スタンプｔ、ノンスが未処理センサ値を暗号化するために使用されるか、未処理センサ値の二乗を暗号化するために使用されるか、を示す符号ｖを含み、ノンスを長さλとするための付加的なストリングσを必要とするかもしれない。
【００９７】
集合手段はｍｉ２を計算する。
【００９８】
集合手段はセンサ値ｍｉをｃｍｉ＝ｍｉ＋ｈｍ（ｆｅｋ（ｉ）（ｒ（ｔ，０，σ）））  ｍｏｄ  Ｎとして、センサ値の二乗ｍｉ２をｃｖｉ＝ｍｉ２＋ｈｖ（ｆｅｋ（ｉ）（ｒ（ｔ，１，σ）））  ｍｏｄ  Ｎ’として暗号化する。Ｎ＝ＰＴであり、Ｎ’＝Ｐ２Ｔである。ｈｍ（ｆｅｋ（ｉ）（ｒ（ｔ，０，σ）））およびｈｖ（ｆｅｋ（ｉ）（ｒ（ｔ，１，σ）））は、センサ値を受信する前に、予め計算することができる。
【００９９】
集合手段はストリング、ストリングのノードＩＤ  ｉ、暗号化ブール暗号文ｃｍｉ、暗号化センサ値ｃｖｉをフィード・サーバに送信する。
【０１００】
フィード・サーバはデータ記憶手段にこれらの値のすべてを保存する。
【０１０１】
クライアントは、期間τにわたるセンサｉ各々の統計を要求する。
【０１０２】
計算処理エンジンは、合計Ｓｉを取得するために、期間τにおけるセンサｉの暗号化センサ値のすべてを合計する。合計Ｖｉを取得するために同一の期間におけるセンサの暗号化されたセンサ値の二乗のすべての合計を計算する。計算処理エンジンはＳｉおよびＶｉの双方をクライアントに送信する。
【０１０３】
計算処理エンジンはこの計算を実行し、クライアントはこのセンサについての、もしくは、この期間におけるセンサ値の暗号化値のパッドのすべての合計、および、この期間におけるこのセンサの暗号化値の暗号化値のパッドのすべての合計を計算する。計算エンジンは、この期間にいくつの値ｎが含まれるかを知っている。
【０１０４】
クライアントが合計ＳｉおよびＶｉを受信する場合、暗号化されていない合計ｓｉおよびｖｉを取得するために、以前のステップにおいて計算されたＳｉおよびＶｉをパッドの合計から減算することによって復号化する。クライアントは平均値Ａｖｅｉ＝Σｓｉ／ｎおよび分散Ｖａｒｉ=Σｖｉ／ｎ−Ａｖｅ２を計算することができる。
【０１０５】
クライアントは、次に、プロセスのどの部分が理想からもっともそれた平均センサ値を有し、どの部分が大きい分散を有し、今後これらの統計を改善するためにどの部分を調整し、もしくは、置換するために努力を払えばよいかを決定するために、これらの値を使用することができる。
【０１０６】
「非準同型システムとの比較」
例示的な適用１（例１）に示されるように、クライアントが復号化するアプローチは、本発明の実施形態によって使用されるアプローチより帯域幅の効率が低い。統計値が計算される値の数が多くなると、この実施形態のシステムが有する効果はより高くなる。さらに、上記したように、この実施形態のシステムはより迅速であり、より安全である。
【０１０７】
「パブリック・キー・ベース準同型システムとの比較」
本発明の上記実施形態で使用される暗号文は長さｔ＋ｐを有する。ｐは精度であり、ｔ＝ｌｏｇ２Ｔであり、Ｔは統計値が計算される期間の最大数である。したがって、使用される暗号文はナノ秒毎に百年(millennia)にわたって取得され平均化される倍精度値についてさえ２０４８ビットより短い。たとえば、一年にわたって毎秒取得される倍精度値および平均化される倍精度値は４５ビットより短い長さの暗号文を必要とする。未処理データおよび未処理データの二乗の双方の暗号化されたデータを記憶するためには９０ビットを必要とし、これは、上記実施形態におけるシステムが記憶手段の使用において桁違いに効率的であることを意味する。例１に関して記述されたように、本発明の実施形態によるシステムはパブリック・キー・スキームに比べ、より迅速な暗号化、復号化、および暗号文のより柔軟な結合を実行し、データへのきめ細かいアクセス制限をサポートする。
【０１０８】
他の例において、例２のより効率的でない暗号化スキームと例１の未処理値の暗号化データを置き換えることにより、例１および例２を組み合わせてもよい。すなわち、例１のブール暗号化の部分によって例２を拡張することができる。
【０１０９】
「アウェアネス・データ例」
本発明の実施形態は既存のアウェアネス集合システムに直接適用することができる。ユーザふるまいおよび動作についての検知センサ・ベース情報は、中央データ記憶手段に送信される前に安全に暗号化することができる。情報のセキュリティは企業レベルおよび個人レベルの双方において重要である。企業は、競争者の詮索好きな目から、もしくは、協力者の目からさえも、従業者のアクティビティについての情報を保護することを望むかもしれない。個人のプライバシーは従業者にとって重要かもしれない。一箇所に暗号化データだけを集中的に保存することによって、信頼されないサード・バーティが非常にセンシティブなふるまいについての情報にアクセスを行うことができないことを確実にする。さらに、クラウド・サービス・レベルにおいてデータの部分的要約および統合のみをサポートすることによって、低信頼の一般的なクラウド・サービスにサービスを移動することを可能にする。
【０１１０】
例３：アウェアネス・データの位置統計値
プロトコル：Ｎは追跡されている人数であり、Ｍはセンサの数であり、ｐはセンサ値の精度である。Ｔは統計値が計算される期間の最大数であり、Ｗは任意の加重平均で使用される最大重みである。
【０１１１】
各センサについて、集合手段は一連のブール値を含む列を生成する。該列は、センサが追跡する人物の各々について、該人物が検出されたか否かを示す。ある場合、このブール値はセンサからの未処理値である。カメラからの画像検出などのその他の場合、集合手段はこの値を取得するために多くの処理を実行してもよい。コンピュータ・アクティビティの検出、ある人物のオフィスにおける動きのカメラ検出などの場合において、一連のセンサ値は一つのブール値を含むだけであってよく、その値は（適正であろうとなかろうと）一般にコンピュータもしくはオフィスを使用する人物と関連する。ブルートゥース・センサもしくはＲＦＩＤリーダなどのその他の場合、多くの人物のブール値が戻される。集合手段は、ブール値の列をｒビット・ストリングとして暗号化し、フィード・サーバに送信する。ここで、ｒ＝ｍ＋ｐ＋ｔ＋ｗである。フィード・サーバは記憶手段に暗号化されたデータを送信し、計算処理エンジンによって処理する。
【０１１２】
計算処理エンジンは各クライアントの固定クエリに関する値を各クライアントに送信する。たとえば、クライアントは、クライアントのワーク・グループにおける人々の状態にだけ関心を有するかもしれない。その場合、これらの人々の値だけがクライアントに送信される。これらのクライアントはデータを復号化し、状態を推測することができる。より長い期間の統計値を多様な目的のために計算してもよい。
ａ．位置予測：
ユーザは、同僚との対面会話を試みるために、将来のある期間に、同僚がいる位置に関心を有するかもしれない。計算処理エンジンは、過去の複数の週における同一の時間における当該人物の考えられる位置の各々についての暗号化値の加重平均を計算することができ、その場合、現在により近い週ほど大きい重みが付与される。クライアントが重みをすでに知っていてもよいし、暗号化加重平均とともに暗号化されていない重みがクライアントに送信されてもよい。クライアントは、パッドの加重平均を計算するために重みを使用し、各位置についての復号化された加重平均を取得するために、クラウド・サービスによって戻される値から加重和を減算する。クライアントは、その時間その位置に該人物がいる相対的な確率をユーザに提示することができる。クエリが一般的なものである場合、計算処理エンジンは加重平均を計算し、保存してもよい。
ｂ．位置使用統計値：
計算処理エンジンは、ある位置に対応するすべての人物についての暗号化値のすべての和を計算し、この和を検出するために、データを復号化することができるクライアントにこの和を送信する。この場合、クライアントはスペースを使用している人物についてなんら知ることなく、スペースの合計使用量を知ることができる。
ｃ．ワークグループ位置：
ワーク・グループにおけるすべての人物についての位置の暗号化値を加算することによって、ワーク・グループの特定のメンバの位置についての情報をなんら明らかにすることなく、ワーク・グループの人々の位置についての統計値をクライアントに付与することができる。
【符号の説明】
【０１１３】
１０１  クラウド・サービス
１０２  クライアント
３０１  暗号化データ記憶手段
３０２  計算処理エンジン
４００  計算処理エンジン
４０２  クライアント計算処理手段
【図１】
2011232727.tif 000003
【図２】
2011232727.tif 000004
【図３】
2011232727.tif 000005
【図４】
2011232727.tif 000006
【図５】
2011232727.tif 000007
【図６】
2011232727.tif 000008
【図７】
2011232727.tif 000009