(57)【要約】  ネットワーク内、特に無線センサネットワーク内でデータを集計する方法を提供する。ネットワーク（１）は、データを測定する複数のセンサノード（Ｎｉ）と、センサノード（Ｎｉ）によって測定されたデータが集計される少なくとも１つのシンクノード（Ｓ）とを有し、各センサノード（Ｎｉ）は、測定したデータを鍵ｋで暗号化し、その結果をシンクノード（Ｓ）へ転送する。ネットワーク（１）内での鍵配布の際に、マスター鍵Ｋが選択され、マスター鍵Ｋは、センサノード（Ｎｉ）が測定データを暗号化するために使用する個別鍵ｋｉへとネットワーク（１）によって自律的に分解され、すべての個別鍵ｋｉの和はマスター鍵Ｋに等しい。
2010524413.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内、特に無線センサネットワーク内でデータを集計する方法において、
前記ネットワーク（１）は、データを測定する複数のセンサノード（Ｎｉ）と、該センサノード（Ｎｉ）によって測定されたデータが集計される少なくとも１つのシンクノード（Ｓ）とを有し、
各センサノード（Ｎｉ）は、測定したデータを鍵ｋｉで暗号化し、その結果を前記シンクノード（Ｓ）へ転送し、
前記ネットワーク（１）内での鍵配布の際に、マスター鍵Ｋが選択され、該マスター鍵Ｋは、前記センサノード（Ｎｉ）が測定データを暗号化するために使用する個別鍵ｋｉへと前記ネットワーク（１）によって自律的に分解され、すべての個別鍵ｋｉの和は前記マスター鍵Ｋに等しいことを特徴とする、ネットワーク内でデータを集計する方法。
【請求項２】
前記マスター鍵Ｋが前記シンクノード（Ｓ）によって選択されることを特徴とする請求項１に記載の方法。
【請求項３】
前記マスター鍵Ｋが前記シンクノード（Ｓ）のみに記憶されることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記ネットワーク（１）内のデータフローが収束キャストトラフィック構造を有することを特徴とする請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
前記センサノード（Ｎｉ）は、前記シンクノード（Ｓ）を例外として、それぞれ１個の先行ノード（ＦＮｉ）を有し、前記センサノード（Ｎｉ）は、場合により、それぞれ１個または複数の後続ノード（ＣＮｉ）を有することを特徴とする請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
各センサノード（Ｎｉ）に前記ネットワーク内でのその相対位置を通知する手段、が提供されることを特徴とする請求項１ないし５のいずれか１項に記載の方法。
【請求項７】
各センサノード（Ｎｉ）は、鍵配布プロセスにおいて、先行ノード（ＦＮｉ）から前記マスター鍵Ｋのある小計Ｋｉを受信すると、その値Ｋｉをｎ個の小計Ｋ′ｉに分解することを特徴とする請求項５または６に記載の方法。
【請求項８】
各センサノード（Ｎｉ）は、直接の後続ノードの個数に従って、小計Ｋ′ｉの個数ｎを設定することを特徴とする請求項７に記載の方法。
【請求項９】
前記センサノード（Ｎｉ）の少なくとも一部は、後続ノード（ＣＡｉ）の測定データを集計することによって集計ノード（Ａｉ）として機能することを特徴とする請求項５ないし８のいずれか１項に記載の方法。
【請求項１０】
集計ノード（Ａｉ）が、後続ノード（ＣＡｉ）によって該集計ノード（Ａｉ）に転送されてきた暗号化データに対して、および、自己の測定し暗号化したデータに対して、集計関数を実行した後、その結果を前記シンクノード（Ｓ）へ転送することを特徴とする請求項９に記載の方法。
【請求項１１】
前記集計関数が、加算、減算、乗算または逆乗算であることを特徴とする請求項１０に記載の方法。
【請求項１２】
暗号化に用いられるアルゴリズムが、暗号化に用いる鍵ｋｉと、暗号化されるべき値ｖｉとの両方に関して準同型であることを特徴とする請求項１ないし１１のいずれか１項に記載の方法。
【請求項１３】
前記準同型アルゴリズムが、決定論的または確率論的なプライバシー準同型であることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記シンクノード（Ｓ）が、ネットワーク全体でダミーな値として乱数値Ｒを選択し、各センサノード（Ｎｉ）が、該乱数値Ｒを後続ノード（ＣＮｉ）の鍵ｋｉで暗号化し代替値Ｅｋｉ（Ｒ）として記憶することを特徴とする請求項５ないし１３のいずれか１項に記載の方法。
【請求項１５】
各集計ノード（Ａｉ）が、集計関数を適用する際に、該集計ノード（Ａｉ）へ測定値を転送することによるデータ集計プロセスへの寄与のない後続ノード（ＣＡｉ）の測定値として、代替値Ｅｋｉ（Ｒ）を使用することを特徴とする請求項１０ないし１４のいずれか１項に記載の方法。
【請求項１６】
前記鍵配布がセキュアな環境で実行されることを特徴とする請求項１ないし１５のいずれか１項に記載の方法。
【請求項１７】
各センサノード（Ｎｉ）の鍵ｋｉが、鍵更新段階の間にときどき更新されることを特徴とする請求項１ないし１６のいずれか１項に記載の方法。
【請求項１８】
鍵更新が、毎回の集計段階の後に実行されることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記センサノード（Ｎｉ）の役割がときどき変更されることを特徴とする請求項１ないし１８のいずれか１項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク内、特に無線センサネットワーク内でデータを集計する方法に関する。ここでネットワークは、データを測定する複数のセンサノードと、センサノードによって測定されたデータが集計される少なくとも１つのシンクノードとを有し、各センサノードは、測定したデータを鍵ｋｉで暗号化し、その結果をシンクノードへ転送する。
【背景技術】
【０００２】
上記のような方法は実際に広く知られており、無線センサネットワーク（wireless sensor network, ＷＳＮ）との関連で特に重要である。ＷＳＮは、一般に、計算能力およびエネルギー容量の限られた小型のセンサノードからなるアドホックネットワークである。センサノードは、一般に、プローブ、処理ユニット、通信デバイス、およびバッテリからなり、データの取得、通信および計算の機能を有する。
【０００３】
無線センサネットワークは、多くの生活部面にますます普及しつつある。センサネットワークの応用分野としては、機械のモニタリング・管理、（体内および体外の）健康パラメータの管理、あるいは環境モニタリング（温度、湿度、地震活動の測定等）が挙げられるが、決してこれらには限られず、応用可能性の範囲はほとんど無限である。例えば水質汚染検査や気象予報等の特定の応用分野において、センサノードは小型に製造可能であり、立ち入り困難な地域においてもセンサネットワークを設置できるという点で、きわめて有利である。
【０００４】
センサノード間の通信は、ブロードキャストメッセージにより無線方式で実行される。これにより、送信動作のコスト上昇・信頼性低下をまねくが、これらはできるだけ避けなければならない。概算で、送信は、１計算ステップのおよそ１００〜１０００倍も多くのエネルギーを消費する。したがって、送信の低減を可能にするメカニズムがあれば、ＷＳＮの寿命を延ばすのに役立つ。
【０００５】
送信低減のための１つの可能な手法として、データ集計がある。一部の実施分野では、ユーザは、個々の測定値ではなく、むしろそれらを集計したもの、例えば総和や平均値に関心がある。このような場合、センサノードからすべての測定値をシンクノードまで送信する必要はない。代わりに、これらのデータをネットワーク内で処理し、その結果のみ、例えば総和を、転送すればよい。総和のデータサイズは、すべての被加算数を連接したものよりもはるかに小さいので、送信オーバーヘッドの低減に有効である。
【０００６】
センサノードは、能力・容量が限られているので、一般に不正操作防止ユニットを含んでいない。そのため、ノード間の秘匿通信に関するセキュリティの問題が重要である。特に、不安定で、信頼性がなく、敵対的でさえある環境に配備するための多数のセンサノードを有するＷＳＮにおいては、ノードは、ノード間のメッセージ交換をサポートするセキュリティメカニズムを備えなければならない。
【０００７】
今後の大規模センサネットワークでは、不正操作防止機能のないセンサノードが用いられる可能性が高い。その場合、ＴｉｎｙＳｅｃ（ＴｉｎｙＯＳのセキュリティモジュール）等の独自仕様ソリューションや、ＩＥＥＥ８０２．１５．４等の標準化されたセキュリティプロトコルで提供されているようなホップバイホップセキュリティは、システム全体のセキュリティとしては非常に限られたものしか提供できないと考えられる。このような知見に鑑みると、効率的なソリューションは、エンドツーエンドセキュリティを提供するメカニズムを目指すべきである。なお、エンドツーエンドセキュリティとは、複数のセンサノードによって個別に暗号化されたデータにアクセスできるのはシンクノードのみであり、それ以外のノードはアクセスできないことを意味する。最善の場合、エンドツーエンド暗号化をデータ集計と組み合わせることができるとよい。ＷＳＮの高度に自己組織的な分散構造により、ＷＳＮにおいてデータ集計にエンドツーエンドセキュリティを提供することは困難な課題であるが、すでにこの方向でのいくつかの進展がある。
【０００８】
例えば、非特許文献１が対象としているのは、シンクロナスＷＳＮにおけるリアルタイムトラフィックのエンドツーエンド暗号化であり、ストリーム暗号に基づく対称暗号変換が提案されている。この方式は、ペアごとに異なる鍵を用いることにより、高いシステムセキュリティを提供する。また、鍵はノードにランダムに配布でき、シンクノードだけがすべての鍵を記憶すればよいので、鍵の事前配布はきわめて容易である。しかし、システム全体のセキュリティの便益と引き替えに、追加的オーバーヘッドのコストを伴う。第１に、ノード配備前のノードの設定では、各センサノードとシンクノードとの間のペアごとに、共有鍵に合意することが必要である。第２に、シンクノードはセンサノードよりもはるかに多くのメモリを備えると考えられているが、大規模なセンサネットワークを目標にする場合、数千ないし数十万の（ＩＤ，鍵）のペアを記憶することが重大な問題となる可能性がある。第３に、非常に信頼性の低い媒体上でのセキュリティソリューションを対象にしているので、無線ブロードキャスト媒体上でのパケット損失の影響を無視できない。したがって、非特許文献１によるプライバシー準同型暗号方式で暗号化された収束キャストトラフィックの場合、現時点で関与する全ノードの鍵ＩＤおよびノードＩＤをそれぞれデータ送信ごとに明らかにしなければならなくなる。これは、ノードが送信しなければならない送信データのサイズを極度に増大させる。送信は、エネルギー消費の点で圧倒的に高コストの動作なので、この手法ではＷＳＮの寿命が短くなり、したがってユーザには受け入れがたいものとなる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】C. Castelluccia, E. Mykletun, and G. Tsudik, Efficient aggregation of encrypted data in wireless sensor networks, in 2nd Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, San Diego, CA,  USA, July 2005
【発明の概要】
【発明が解決しようとする課題】
【００１０】
したがって、本発明の目的は、上記のようなネットワーク内でデータを集計する方法において、容易に実施可能なメカニズムを用いることにより、最新式の方式に比べて通信オーバーヘッドを低減しつつ、データ集計プロセスに対して高いセキュリティを提供することである。
【課題を解決するための手段】
【００１１】
本発明によれば、上記の目的は、請求項１に記載の方法によって達成される。請求項１に記載の通り、この方法は、ネットワーク内での鍵配布の際に、マスター鍵Ｋが選択され、マスター鍵Ｋは、センサノードが測定データを暗号化するために使用する個別鍵ｋｉへとネットワークによって自律的に分解され、すべての個別鍵ｋｉの和はマスター鍵Ｋに等しい。
【００１２】
本発明によって初めて認識されたこととして、センサノードが測定データを暗号化するために使用する個別鍵ｋｉへとネットワークによって自律的に分解されるマスター鍵Ｋに基づいて、ネットワーク内での鍵配布プロセスを構成することにより、通信オーバーヘッドを低減しつつ高いセキュリティレベルを実現することができる。マスター鍵Ｋの自律的分解は、すべての個別鍵ｋｉの和がマスター鍵Ｋに等しくなるように実行される。これにより、自己組織的な鍵配布が実現され、ノード配備前のノードの設定で各センサノードとシンクノードとの間のペアごとに共有鍵に合意することが不要になるので、ネットワークの所有者／管理者にとって、このプロセスはより好適となる。また、本発明による方法は、暗号化されたトラフィックをシンクノードの方向に向かって送信する際に、追加的なデータオーバーヘッドを必要としない。さらに、エンドツーエンド暗号化のためにペアごとに一意的な鍵を使用することにより、個々のセンサノードでのセキュリティに不足はないので、システム全体で高いセキュリティが達成される。
【００１３】
有利な態様として、マスター鍵Ｋはシンクノードによって選択される。シンクノードは一般に、センサノードよりもはるかに多くのパワーおよび記憶容量を備える。この要因と、ネットワーク内でのその中心的役割とから、シンクノードが鍵配布プロセスを開始すべきである。また、さらにセキュリティを向上させるには、マスター鍵Ｋをシンクノードのみに記憶すると有利であることがわかる。この場合、シンクノードのみが、受信した暗号にマスター鍵Ｋを適用することによって、最終的な集計値を復号することができる。なお、シンクノードは、個別鍵ｋｉを知ることなしに、センサネットワークに記憶される和Ｋを知る。
【００１４】
好ましい態様として、ネットワーク内のデータフローは収束キャストトラフィック構造を有する。中心点、すなわちシンクノードへ向かうこの種の構造は、エンドツーエンド暗号化のためのペアごとに一意的な鍵の確立をサポートする鍵配布方式に最適である。
【００１５】
具体的態様として、ネットワークの各センサノードは、１個の先行ノード（そのセンサノード自身よりもシンクノードに近いノード）を有し得る。唯一の例外は、収束キャストトラフィック構造の目的地点としてのシンクノードであって、シンクノードは先行ノードを有しない。したがって、ネットワークの中心から見ると、センサノードは、１個または複数の後続ノードを有し得る。この点、当業者には明らかなように、あらゆるセンサノードが後続ノードを有するとは限らない。例えば、ネットワークの最も外側のセンサノードは後続ノードを有しない。このようなノードはリーフ（葉）ノードと呼ぶことができ、それにより、センサネットワークは木構造あるいは木状構造とみなされる。
【００１６】
特に有利な態様として、各センサノードにネットワーク内でのその相対位置を通知する手段が提供される。すなわち、初期起動段階の後、各センサノードは、その先行ノードおよび後続ノードが知らされる。この点、ネットワーク内のセンサノードは、いったん配備された後は、準静的であることが好ましい。なお、相対位置に関するセンサノードの知識は、その絶対位置に関する位置的知識を含まない。
【００１７】
相対位置情報に基づいて、各センサノードは、鍵配布プロセスにおいて、先行ノードからマスター鍵Ｋのある小計Ｋｉを受信すると、値Ｋｉをｎ個の小計Ｋ′ｉに分解するものとすることができる。ネットワークの構造に最適に適合するように、各センサノードは、直接の後続ノードの個数に従って、小計Ｋ′ｉの個数ｎを設定することができる。例えば、センサノードが３個の後続ノードを有することを知っており、このセンサノードが先行ノードから値Ｋｉを受信した場合、この値を４個の小計に分解し、Ｋｉ＝Ｋｉ＊＋Ｋ′１＋Ｋ′２＋Ｋ′３とする。Ｋｉ＊は、このセンサノードが後で自己のデータを暗号化するために使用する。他の小計は後続ノードに渡され、ネットワーク構造に従って再び分解され、以下同様である。セキュリティの観点から、センサノード自身はＫｉ＊のみを永続的に記憶し、他の小計は、適当な後続ノードに渡した後には自己のメモリから削除するのが有利である。鍵配布プロセスの終了時に、各センサノードは、ネットワーク内に配布されたすべての鍵の和がマスター鍵Ｋに等しくなるような１個の鍵を所有する。
【００１８】
好ましい実施形態において、少なくとも一部のセンサノードは、後続ノードの測定データを集計することによって集計ノードとして機能することが可能である。これにより、すべてのセンサノードの測定データをシンクノードへ転送するのに必要なメッセージの個数を大幅に低減することができる。送信は、無線センサネットワークにおける最も高コストの動作なので、データ集計は非常に有益である。
【００１９】
集計ノードによって実行される集計プロセスは、自己の測定し暗号化したデータに対してだけでなく、後続ノードによって当該集計ノードに転送されてきた暗号化データに対して集計関数を実行するステップと、その集計結果をシンクノードへ転送するステップとを含んでもよい。具体的には、集計関数は加算、減算、乗算または逆乗算とすることができる。
【００２０】
特に有利な実施形態において、暗号化に用いられるアルゴリズムは、暗号化に用いる鍵ｋｉと、暗号化されるべき値ｖｉとの両方に関して準同型である。この種の暗号化関数は双準同型と呼ばれる。その意味は、任意の２個の鍵ｋ１およびｋ２と、任意の平文値ｖ１およびｖ２とに対して、次式が成り立つことである。
Ｅｋ１（ｖ１）＋Ｅｋ２（ｖ２）＝Ｅｋ１＋ｋ２（ｖ１＋ｖ２）
【００２１】
このようなアルゴリズムの簡単な一例は、Ｅｋ（ｖ）：＝ｋ＋ｖ  ｍｏｄ  ｎ  である。ただし、鍵ｋおよび値ｖはいずれも、０からｎ−１までの範囲内のある整数である。集計演算が加算である場合、シンクノードは、測定値の和ｖ１＋・・・＋ｖｎを知ろうとする。ここでｎは、ネットワーク内のセンサノードの個数を表す。暗号化アルゴリズムの双準同型構造により、
Ｅｋ１（ｖ１）＋・・・＋Ｅｋｎ（ｖｎ）＝Ｅｋ１＋・・・＋ｋｎ（ｖ１＋・・・＋ｖｎ）
を復号しようとするシンクノードは、値ｋ１＋・・・＋ｋｎ、すなわちマスター鍵Ｋを知ればよい。これに対して、個別鍵ｋｉは復号に不要である。上記の方法は大規模センサネットワークを目標としているので、数千個の（ＩＤ，鍵）のペアを記憶することになれば重大な問題となり得るが、それが不要となる。鍵配布プロセスを開始するシンクノード等のノードは、Ｋ＝ｋ１＋・・・＋ｋｎであるマスター鍵Ｋのみを知ればよい。他方、集計ノードは、従来のホップバイホップ暗号化を用いる場合に必要とされるような、後続ノードから到着するデータに対する復号演算を、実行する必要がない。すでに指摘したように、集計ノードでのセキュリティに不足はないので、これによりシステム全体のセキュリティが向上する。
【００２２】
双準同型アルゴリズムは、決定論的であっても、確率論的であってもよい。決定論的アルゴリズムは、鍵と平文のペアが同一であれば必ず同一の暗号文に写像するのに対して、確率論的アルゴリズムでは、この写像はある確率で変わる。
【００２３】
さらに好ましい実施形態において、シンクノードは、ネットワーク全体でダミーな値として乱数値Ｒを選択し、これを鍵配布プロセスにおいてセンサネットワーク内に配布してもよい。値Ｒは、各センサノードＮｉが後続ノードのそれぞれに対して値Ｅｋｉ（Ｒ）、すなわち、乱数値Ｒの暗号文（ただし、ｋｉは後続ノードの鍵を表す）を記憶するように用いられる。データ集積プロセスの効率を高めるため、各集計ノードは、集計関数を適用する際に、集計ノードへ測定値を転送することによるデータ集計プロセスへの寄与のない後続ノードの測定値として、デフォルト値Ｅｋｉ（Ｒ）を使用する。これにより、無応答ノード（例えば、エネルギー切れやその他の故障により脱落したノード）に対処することができ、最新式の方式とは異なり、応答ノード／無応答ノードのＩＤを提供する必要がない。このため、集計された暗号文のみを転送すればよい。このこともまた、通信オーバーヘッドを低減し、それによりセンサネットワークの寿命が延びる。さらに、集計段階におけるロバスト性が向上する。これは、メッセージがブロードキャストされ、パケット損失の影響が無視できないような非常に信頼性の低い媒体では特に有益である。これにより、信頼性の低いリンクの場合や、一部のノードが測定・転送プロセスに参加できない状況であっても、データ集計を高い効率およびセキュリティで実行できる。これは、無線ボディネットワーク（Ｗ−ＢＡＮ）の場合のように、固定ネットワーク構造を有するセンサネットワークにとって特に有効である。Ｗ−ＢＡＮは、利用者の健康状態の遠隔モニタリングを可能にするので、将来のｅ−ヘルスアーキテクチャにおいて顕著な役割を果たすであろうと考えられる。
【００２４】
有利な態様として、鍵配布は、攻撃者がいないと仮定されるセキュアな環境で実行される。初期化段階における初期鍵配布の後、更新段階を設け、各センサノードの鍵ｋｉをときどき更新してもよい。特に、暗号化に用いられる決定論的なプライバシー準同型に対して鍵を更新することが重要であり、毎回の集計段階の後に更新するのが理想的である。しかし、現実的な状況では、鍵更新の頻度と必要なセキュリティレベルとの間で、うまくバランスをとればよい。なお、鍵更新は、決定論的なプライバシー準同型をサポートする場合にのみ有効である。ペアごとの確率論的なプライバシー準同型の範疇に属するすべての暗号変換に対しては、鍵更新は利益がない。
【００２５】
原則として、鍵更新段階は、初期化段階における鍵配布と同様としてもよい。旧マスター鍵Ｋを新マスター鍵Ｋ＊で置換し、シンクノードは差Ｋ−Ｋ＊＝：Δのみを選択し知るが、個別鍵は知ることがないようにして、鍵ｋｉを変更することができる。
【００２６】
鍵更新のための２種類の実施形態が有利であると考えられる。第１の実施形態によれば、初期化段階におけるマスター鍵Ｋと同様に、差Δを分解して後続ノードに通知する。攻撃者はいないと仮定した初期化段階とは異なり、更新された鍵は盗聴不可能なので、鍵更新段階には、セキュアな環境は不要である。
【００２７】
別法として、各ノードは、相異なるマスター鍵から導出された複数の鍵を同時に記憶する。この場合、実際の鍵は、記憶した鍵の特定の線形結合に等しく、その線形結合は一意的に決定される。第１の実施形態とは異なり、この第２の実施形態では、鍵更新のためのデータの送信が不要である。
【００２８】
さらに有利な実施形態において、センサノードの役割はときどき変更される。このような変更の結果、センサネットワークの寿命が長くなる。というのは、例えば、到着するデータを集計しそれらを転送するのは、単に測定を行い測定値を送信するのに比べて、エネルギーをより多く消費する作業だからである。
【００２９】
本発明を有利な態様で実施するにはいくつもの可能性がある。このためには、請求項１に従属する諸請求項を参照しつつ、図面により例示された、本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例についても説明する。
【図面の簡単な説明】
【００３０】
【図１】本発明による方法の一実施形態における鍵配布を示す模式図である。
【図２】本発明による方法の一実施形態におけるデータ集計を示す模式図である。
【発明を実施するための形態】
【００３１】
図１は、本発明の一実施形態を模式的に示す。すなわち、本発明による鍵配布プロセスを示している。明確化および例示の目的上、図１は、センサネットワーク１の非常に小さい一部分のみを示している。図示した部分は、４個だけのセンサノードを有し、それらをＮ０、Ｎ１、Ｎ２、およびＮ３としている。しかし、実際には、センサネットワーク１は数千個のセンサノードＮｉを含み得る。
【００３２】
初期化は、センサネットワーク１のルート、すなわちシンクノードＳ（図示せず）から、センサノードＮｉへと、トップダウン方式で行われる。簡単に言えば、各センサノードＮｉは、鍵配布中のある時点に、マスター鍵Ｋのうちの自己の取り分を受信する。マスター鍵Ｋは、シンクノードによって選択され、シンクノードの後続ノードへと、制御された方式で配布される。図１に示す実施形態では、センサノードＮ０は、先行ノード（図示せず）から、マスター鍵Ｋのうちの自己の取り分ｋを受信する。センサノードＮ０は、後続ノード、すなわちＮ１、Ｎ２、およびＮ３、を知っている。そこで、マスター鍵Ｋのうちの自己の取り分ｋを４個の小計ｋ０、ｋ１、ｋ２、およびｋ３に、ｋ＝ｋ０＋ｋ１＋ｋ２＋ｋ３と分解し、後ろの３個の小計をそれぞれ後続ノードＮ１、Ｎ２、およびＮ３に配布する。センサノードＮ１およびＮ２はそれぞれ２個の後続ノードを有するので、マスター鍵Ｋのうちの自己の取り分、すなわちそれぞれｋ１およびｋ２、をランダムに３個の小計に分解し、これらの値を後続ノードに配布する。他方、センサノードＮ３は３個の後続ノードを有するので、マスター鍵Ｋのうちの自己の取り分ｋ３を４個の小計に分解する。
【００３３】
配布プロセスの終了時に、各センサノードＮｉは単一の対称鍵ｋｉを受信しているが、すべての鍵ｋｉは、シンクノードのみに記憶されている１個のマスター鍵Ｋから導出されている。上記の初期化段階の間、システムは受動攻撃に対してさえ非常に脆弱である。したがって、この段階の間は、攻撃者がいないことを仮定する。
【００３４】
また、図１には示していないが、シンクノードＳは乱数値Ｒを選択する。値Ｒは、ネットワーク１のすべてのセンサノードＮｉに配布される。ロバスト性のため、各センサノードＮｉは、後続ノードのそれぞれについて、暗号Ｅｋｉ（Ｒ）を記憶する。ここでｋｉは、後続ノードのそれぞれの鍵である。セキュリティ上の理由から、各センサノードＮｉはその後、自己の鍵ｋｉおよび後続ノードに対する暗号化値Ｅｋｊ（Ｒ）以外のすべての値を自己のメモリから削除する。
【００３５】
次に図２を参照する。図２は、センサネットワーク１の図１と同じ小部分を示している。図１とは異なり、図２はデータ集計プロセスを示す。集計段階の間、収束キャストトラフィックが、センサノードＮｉからシンクノードまでエンドツーエンドで暗号化される。各センサノードＮｉは、自己の測定値を自己の一意的な鍵で暗号化した後、得られた暗号文を自己の子（後続）ノードから受信した暗号文に加えることにより、対称準同型暗号変換を適用する。
【００３６】
図２をさらに詳細に参照すると、センサノードＮ１およびＮ３はそれぞれ測定値ｖ１およびｖ３を有する。他方、センサノードＮ２は、例えば電池切れのため止まっており、結果として、データ集計プロセスへの測定値の寄与がない。センサノードＮ１およびＮ３は、自己の測定値を自己の個別対称鍵ｋ１およびｋ３でそれぞれ暗号化し、その結果であるＥｋ１（ｖ１）およびＥｋ３（ｖ３）をそれぞれ先行ノードＮ０へ転送する。
【００３７】
センサノードはネットワーク内での自己の相対位置を知っているので、センサノードＮ０は、後続ノードＮ１、Ｎ２およびＮ３のすべてからはデータを受信していないことを認識する。そこでセンサノードＮ０は、上記のように、ネットワーク全体でダミーな値として初期化段階の間に配布されすべてのセンサノードＮｉによって記憶されている代替値Ｒの暗号により、欠けている暗号を置き換える。結果として、集計ノードＮ０は、Ｅｋ１（ｖ１）＋Ｅｋ２（Ｒ）＋Ｅｋ３（ｖ３）を先行ノードへ転送する。最終的に、シンクノードＳは
ＥΣｋｉ（Σｖｉ）＋ＥΣｋｊ（ｃｔｒ＊Ｒ）
を、値ｃｔｒとともに受信する。ただし、ｃｔｒは、集計に含まれるダミー値Ｒの個数を表す第１のカウンタである。シンクノードＳはさらにＫを知っているので、すべての報告された測定値の和を容易に導出することができる。無応答センサノードについては、シンクノードＳは、集計プロセスの終了時に、何個のダミー値が平文に含まれるかのみを知ればよく、具体的にどのノードが応答したかを知る必要はない。カウンタｃｔｒは、無応答ノードの個数に応じてインクリメントされ、暗号化された測定値とともに送信されてもよい。
【００３８】
上記のような情報から、シンクノードＳは、報告された測定値の和を復元することができるが、全部で何個の値が集計されているかはわからない。この情報は重要となり得るので、応答ノードの個数を計算する第２のカウンタｒｅｓｐを設けてもよい。カウンタｒｅｓｐは、カウンタｃｔｒと同様に扱うことができる。集計ノードは、各応答ノードＮｉから値ｒｅｓｐｉを受信し、その和を先行ノードへ転送する。図２に示した実施形態では、センサノードＮ０は、カウンタｃｔｒを値１（無応答ノードＮ２に由来する）だけインクリメントし、カウンタｒｅｓｐを値２（２個の応答ノードＮ１およびＮ３に由来する）だけインクリメントして、転送することになる。
【００３９】
各センサノードＮｉは自己の鍵だけを記憶するので、子（後続）ノードから到着する暗号を復号することはできない。シンクノードＳのみが、受信した暗号にマスター鍵Ｋを適用することによって、最終的な集計値を復号することができる。すでに述べたように、必ずしもすべてのノードが寄与しているとは限らず、また、無線伝送媒体上の干渉によりパケットが失われる可能性もあるので、それぞれの中間ノードは、集計され暗号化された和に、直接の子ノードのうち入力を提供しないものに対応して、記憶しているデフォルトの暗号Ｅｋｉ（Ｒ）を加える。集計段階の間、システムは受動および能動攻撃に対してセキュアである。どのセンサノードも、受信した暗号を復号できない。実際の部分木の測定値を表す集計値を知り得るのは、部分木ＳＴ（Ｎ）全体を破壊する場合だけである。ここで、ノードＮの部分木ＳＴは、Ｎをルートとする部分木として、Ｎがリーフノードの場合はＳＴ（Ｎ）＝｛Ｎ｝、そうでない場合は
【数１】
2010524413.tif 000003
と定義される。
【００４０】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到しうるであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと理解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【図１】
2010524413.tif 000004
【図２】
2010524413.tif 000005
【手続補正書】
【提出日】平成21年10月15日(2009.10.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワーク内、特に無線センサネットワーク内でデータを集計する方法において、
前記ネットワーク（１）は、データを測定する複数のセンサノード（Ｎｉ）と、該センサノード（Ｎｉ）によって測定されたデータが集計される少なくとも１つのシンクノード（Ｓ）とを有し、
各センサノード（Ｎｉ）は、測定したデータを鍵ｋｉで暗号化し、その結果を前記シンクノード（Ｓ）へ転送し、
前記ネットワーク（１）内での鍵配布の際に、マスター鍵Ｋが選択され、該マスター鍵Ｋは、前記センサノード（Ｎｉ）が測定データを暗号化するために使用する個別鍵ｋｉへと前記ネットワーク（１）によって自律的に分解され、すべての個別鍵ｋｉの和は前記マスター鍵Ｋに等しいことを特徴とする、ネットワーク内でデータを集計する方法。
【請求項２】
前記マスター鍵Ｋが前記シンクノード（Ｓ）によって選択されることを特徴とする請求項１に記載の方法。
【請求項３】
前記マスター鍵Ｋが前記シンクノード（Ｓ）のみに記憶されることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記ネットワーク（１）内のデータフローが収束キャストトラフィック構造を有することを特徴とする請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
前記センサノード（Ｎｉ）は、前記シンクノード（Ｓ）を例外として、それぞれ１個の先行ノード（ＦＮｉ）を有し、前記センサノード（Ｎｉ）は、場合により、それぞれ１個または複数の後続ノード（ＣＮｉ）を有することを特徴とする請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
各センサノード（Ｎｉ）に前記ネットワーク内でのその相対位置を通知する手段、が提供されることを特徴とする請求項１ないし５のいずれか１項に記載の方法。
【請求項７】
各センサノード（Ｎｉ）は、鍵配布プロセスにおいて、先行ノード（ＦＮｉ）から前記マスター鍵Ｋのある小計Ｋｉを受信すると、その値Ｋｉをｎ個の小計Ｋ′ｉに分解し、
各センサノード（Ｎｉ）は、直接の後続ノードの個数に従って、小計Ｋ′ｉの個数ｎを設定し得ることを特徴とする請求項５または６に記載の方法。
【請求項８】
前記センサノード（Ｎｉ）の少なくとも一部は、後続ノード（ＣＡｉ）の測定データを集計することによって集計ノード（Ａｉ）として機能することを特徴とする請求項５ないし７のいずれか１項に記載の方法。
【請求項９】
集計ノード（Ａｉ）が、後続ノード（ＣＡｉ）によって該集計ノード（Ａｉ）に転送されてきた暗号化データに対して、および、自己の測定し暗号化したデータに対して、集計関数を実行した後、その結果を前記シンクノード（Ｓ）へ転送し、
前記集計関数が、加算、減算、乗算または逆乗算であり得ることを特徴とする請求項８に記載の方法。
【請求項１０】
暗号化に用いられるアルゴリズムが、暗号化に用いる鍵ｋｉと、暗号化されるべき値ｖｉとの両方に関して準同型であり、
前記準同型アルゴリズムが、決定論的または確率論的なプライバシー準同型であり得ることを特徴とする請求項１ないし９のいずれか１項に記載の方法。
【請求項１１】
前記シンクノード（Ｓ）が、ネットワーク全体でダミーな値として乱数値Ｒを選択し、各センサノード（Ｎｉ）が、該乱数値Ｒを後続ノード（ＣＮｉ）の鍵ｋｉで暗号化し代替値Ｅｋｉ（Ｒ）として記憶することを特徴とする請求項５ないし１０のいずれか１項に記載の方法。
【請求項１２】
各集計ノード（Ａｉ）が、集計関数を適用する際に、該集計ノード（Ａｉ）へ測定値を転送することによるデータ集計プロセスへの寄与のない後続ノード（ＣＡｉ）の測定値として、代替値Ｅｋｉ（Ｒ）を使用することを特徴とする請求項９ないし１１のいずれか１項に記載の方法。
【請求項１３】
前記鍵配布がセキュアな環境で実行されることを特徴とする請求項１ないし１２のいずれか１項に記載の方法。
【請求項１４】
各センサノード（Ｎｉ）の鍵ｋｉが、鍵更新段階の間にときどき更新され、
鍵更新が、毎回の集計段階の後に実行され得ることを特徴とする請求項１ないし１３のいずれか１項に記載の方法。
【請求項１５】
前記センサノード（Ｎｉ）の役割がときどき変更されることを特徴とする請求項１ないし１４のいずれか１項に記載の方法。
【国際調査報告】
2010524413.tif 000006
2010524413.tif 000007
2010524413.tif 000008