小型端末を利用した匿名性を持つ遭遇履歴保証技術の提案 大阪大学　大学院情報科学研究科 堺拓郎　内山彰　中村嘉隆　東野輝夫 2007/3/1 第130回DPS/第36回CSEC合同研究会

研究背景 位置情報、行動履歴を取得することが重要 行動履歴の信頼性を高める 米国のE-911（緊急通報サービス） 行動履歴の信頼性を高める 位置情報と遭遇情報を利用 しかし、サーバに遭遇情報を集中させることは望ましくない 情報漏えい、プライバシー ユーザが自身の遭遇情報を蓄積し、必要時にサーバで解読する方式を考える 以下の特性を満たすようにする 証拠性、リンク不能性 １． 位置情報の信頼性を高めるため、位置情報だけでなく遭遇情報を用いる ２． 「誰かと遭遇した」という遭遇情報は個人情報であるため、 サーバに集中させることは望ましくない ３． そこで、ユーザが自身の遭遇情報を蓄積して、 必要時にサーバで解読する方式を考えた 2007/3/1 第130回DPS/第36回CSEC合同研究会

個人のプライバシーを尊重しながら，他者との遭遇情報に 関する証拠性を提示できるような遭遇情報保証技術を提案する 研究目的 個人のプライバシーを尊重しながら，他者との遭遇情報に 関する証拠性を提示できるような遭遇情報保証技術を提案する 特徴 個人情報の保護を考慮 リンク不能性を保持 証拠性を保証 [誰と・いつ・どこで] (RFIDなどの低性能な)小型端末向けの設計 １．本研究の目的は「～～」である ２． 個人のプライバシーを尊重するため、個人情報の保護＋リンク不能性 誰と・いつ・どこで遭遇したかという証拠性 現実的な実用化を考慮して、小型端末向けの設計 リンク不能性： 任意の二つのデータから，その二つが同じ者によって作成されたかどうかを判断できない 2007/3/1 第130回DPS/第36回CSEC合同研究会

提案方式の概要 -遭遇情報の保証- 遭遇情報の交換 個人情報の保護 A B C 友人との遭遇情報のみが分かる 遭遇情報はリンク不能 P1 無線通信可能な小型端末を利用 遭遇時に互いの[ID, 位置, 時刻]（遭遇情報）を交換・蓄積 位置，時刻の取得 位置推定手法の応用、GPSなど 個人情報の保護 遭遇情報の作成者を判別不可 許可したユーザにのみ自分との遭遇情報を公開 A P4 P3 B C P1の遭遇情報 07/02/19, 9:00, P2と交差点Aで遭遇 07/02/19, 9:20, ??と交差点Bで遭遇 07/02/19, 9:40, P4と交差点Cから一緒に行動 07/02/19, 9:00, X72DCcXlw0kD 07/02/19, 9:20, UKlw201[z.lxui 07/02/19, 9:40, 10Dlxx/.zjo\^du １．（概要） ユーザが無線通信機能を持った小型端末を保持して行動しており、 ユーザが互いに無線範囲内にいるときに[ID、位置、時刻]の遭遇情報を交換する。 このとき送受信される位置・時刻は何らかの手法を用いて取得できるものとする。 ２． 蓄積した遭遇情報は個人情報なので このように作成者を判別不可能にして 遭遇情報がリンク不能性をみたすようにする ３． ただし、許可されたユーザにのみ自分との遭遇情報を公開してもよいと して、友人との遭遇情報のみがわかる 友人との遭遇情報のみが分かる 遭遇情報はリンク不能 2007/3/1 第130回DPS/第36回CSEC合同研究会

提案方式の概要 -個人情報の保護- 個人情報の匿名性 個人情報の管理 蓄積した遭遇情報はリンク不能 P1 P2 PN 知らないユーザには個人情報を公開したくない 遭遇情報がリンク不能性を満たせばよい 個人情報の管理 小型端末にはメモリ制限 すべての遭遇情報を蓄積することは難しい ユーザ毎にローカルサーバを持つ ローカル サーバ Data1 P1 ホットスポットを介して遭遇情報をローカルサーバへ転送 Data1 ・・・・・・・・・・・・・・・・・・・・・・・・ 07/02/19, 9:00, X72DCcXlw0kD 07/02/19, 9:20, UKlw201[z.lxui 07/02/19, 9:40, 10Dlxx/.zjo\^du ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ 07/02/19, 11:30:00, End １． 個人情報の匿名性のためには先ほども述べたように リンク不能性を満たせばよい ２． それらの情報を管理するためには、 小型端末のみで管理するにはメモリ制約があるため 各ユーザがローカルサーバを持ち、そこで遭遇情報の管理を行う。 ホットスポットを介して、小型端末からローカルサーバに 遭遇情報を転送。 蓄積した遭遇情報はリンク不能 2007/3/1 第130回DPS/第36回CSEC合同研究会

「誰と」「いつ」「どこで」遭遇したかわかる 提案方式の概要 -遭遇情報の確認- 蓄積した遭遇情報を必要時に認証局で解読 遭遇相手の特定 許可されたユーザのみ 遭遇情報に改竄がないことの確認 認証局 [IDリスト] (P1, P2, …, PN) 解読結果 [友人リスト] P1:(P2, P4, …) P2:(P1, …, PN) … 提示 Data1 ・・・・・・・・・・・・・・・・・・・・・・・・ 07/02/19, 9:00, P2, (100, 200) 07/02/19, 9:20, ??, (100, 180) 07/02/19, 9:40, P4, (80, 180) ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ 07/02/19, 11:30:00, End Data1 ・・・・・・・・・・・・・・・・・・・・・・・・ 07/02/19, 9:00, X72DCcXlw0kD 07/02/19, 9:20, UKlw201[z.lxui 07/02/19, 9:40, 10Dlxx/.zjo\^du ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ 07/02/19, 11:30:00, End P1 Data1 P1 P2 PN 蓄積した遭遇情報を必要時に認証局で解読してもらう １．認証局に依頼して遭遇情報を提示する ２．認証局では、IDリストや各ユーザの友人リストを管理しており、 それらを基にして、遭遇相手の特定を行い、また遭遇情報の改竄が ないことを確認する。 ３．解読した結果を依頼ユーザに返すことで、ユーザは 「誰と」 「いつ」「どこで」遭遇したか分かる 認証局に依頼 「誰と」「いつ」「どこで」遭遇したかわかる リンク不能性を満たす遭遇情報 2007/3/1 第130回DPS/第36回CSEC合同研究会

提案方式の実現方法 個人情報の保護 証拠性 リンク不能性 各ユーザが自身の遭遇情報を蓄積する 認証局のみが、遭遇情報からIDに関する情報を得られる 仮定：端末xのID（idx）を知っているのは端末xと認証局のみ 許可されたユーザとの遭遇情報のみを知ることができる 認証局がユーザごとにフレンドリストを持つ 証拠性 ハッシュ関数を利用した遭遇情報の改ざん検証 リンク不能性 既存のハッシュ関数を用いたID照合を利用 Randomized Hash Lock方式 [10] 2007/3/1 第130回DPS/第36回CSEC合同研究会 [10]S.A.Weis, et al., “Security and privacy aspects of low-cost radio frequency identification systems,” In Proc. of Security in Pervasive Computing, pp.201-212,2004.

Randomized Hash Lock方式 ID集合 ユーザi サーバS STEP1： ユーザが認証してもらうハッシュ値をサーバに送信する STEP2： サーバがID集合を利用して総当りでID照合を行う id1, id2, ・ idN STEP1 121,H=MD[idi, 121] 121, 2860127359 STEP2 2860127359 = MD[idx,121]? idx = idi R : 乱数、MD : ハッシュ値 ユーザiの送信データ 時刻 乱数 ハッシュ値 各送信データは全く異なる 送信者が同一人物と分からない Randomized Hash Lock方式の概要 ユーザはサーバに認証してもらうために、 乱数とidを入力としたハッシュ値を生成して、それをサーバに送信する サーバ側ではまた乱数とidのハッシュ値を計算して、受信したハッシュ値と 一致するかどうか、ユーザのidを総当りでID照合を行う。 一致した場合に、そのidがその送信データの作成者であると判断できる ２． ユーザの送信データを時刻ごとに区切って見ると、 乱数を利用しているため、値が毎回全く異なる ここからデータの送信者が同一人物であると判断されることはない よって、リンク不能性を満たす t 121, 2860127359 t+1 379, 7290821452 リンク 不能 リンク不能性を満たす t+2 962, 4531475538 t+3 756, 3581742431 2007/3/1 第130回DPS/第36回CSEC合同研究会

遭遇情報の保証 遭遇情報の交換 遭遇情報の蓄積 遭遇相手が自分と遭遇したことを保証 満たすべき特性 [ID、位置、時刻]を含む情報(MD1, MD’1)を定期的に送信 他端末が自身の[ID、位置、時刻]を含む情報(MD2)を返信 再度IDを含む情報(MD’’1)を返信 遭遇情報の蓄積 他端末が送受信して得られた全ての情報を蓄積 自端末がMD’1と位置，時刻を蓄積 遭遇相手が自分と遭遇したことを保証 MD：ハッシュ値　R：乱数 実際にユーザ同士が遭遇したときに、どのように遭遇情報を得るかを詳しく説明する。 １．図を使って流れを呼んで説明。 以上により、ユーザ2がユーザ1と遭遇したことが保証される。 満たすべき特性 リンク不能性 証拠性 MD1, MD’1 ユーザ1 ユーザ2 MD2 MD’’1 , R1 2007/3/1 第130回DPS/第36回CSEC合同研究会

遭遇者の保証 [ID、位置、時刻]を含む情報（ハッシュ値）を交換 情報作成者=情報送信者の保証 誰がその情報を作成したかは保証される ただし、情報作成者＝情報送信者は保証されない 情報作成者=情報送信者の保証 方法1：送受信の時間制約 送信から受信までの時間制約を設ける ユーザ2の保証（MD1, MD’1～MD2） ユーザ1の保証（MD2～MD’’1） 方法2：遭遇情報の位置・時刻検証 自身の位置・時刻と遭遇相手の位置・時刻から検証可能 お互いが通信可能な範囲にいるかどうか ユーザ1 ユーザ2 MD1, MD’1 Δt MD2 Δt MD’’1 , R1 例：ユーザ１が作成した情報をユーザ3が受信し、それを保持しておき 2007/3/1 第130回DPS/第36回CSEC合同研究会

リンク不能性の検証 検証例 ユーザ1が送信するデータ リンク 不能 各送信データは全く異なる ユーザ1,2が10:30～11:00一緒に行動していた ユーザ1が送信するデータ MD1={id1, 2359450622}, 2359450622 9850578321, 2359450622 MD1={id1, MD’1}, MD’1={id1, (100,200), 10:30} 時刻 MD1, MD’1 ユーザ1 ユーザ2 10:30 9850578321, 2359450622 MD2 10:40 3144212347, 3510541847 リンク 不能 MD’’1 , R1 10:50 2109471127, 7359875201 MD’1={id1, pos1, time1}： ID・位置・時刻を入力としたハッシュ値 リンク不能性を満たしているかどうかを検証する ここでは、例としてユーザ1が始めに送信するデータに関して検証する。 １． MD、MD’の紹介。 具体的に10:30に(100,200)の場所にいたという情報を送信する場合、 このようにユーザ1が送信するデータを得る。 同様にして、10:30～11:00を見ると各送信データは全く異なる値と なるので、データ送信者が同一人物であると判断できない よってリンク不能性を満たす 11:00 5194857291, 6113408287 各送信データは全く異なる 送信者が同一人物と分からない ⇒　リンク不能性を満たす MD1={id1, MD’1}： IDとMD’を入力としたハッシュ値 2007/3/1 第130回DPS/第36回CSEC合同研究会

証拠性の検証 検証例 データ改竄があると、ハッシュ値が一致しない ユーザ1が送信するデータのMD’1が改竄された MD1={id1, MD’1}, MD’1={id1, pos1, time1} 偽データ MD’1= 1083272219 9850578321, 2359450622 9850578321, 1083272219 9850578321 = MD[id1, 2359450622] ? 9850578321 = MD[id1, 1083272219] ? 次に、証拠性を検証する。 ユーザ1の送信データのMD’が改竄された状況を考える。 １．正規データの場合、認証局でID照合を行ったときにハッシュ値が一致するので、 誰が作成したデータなのか判断できる。 ２．しかし偽データに変わると、ハッシュ関数の入力が変わるので、ハッシュ値が 一致しなくなる。このようにデータ改ざんを検出することができるため証拠性を満たす。 データ改竄があると、ハッシュ値が一致しない データ改竄を検出可能 ⇒　証拠性を満たす 2007/3/1 第130回DPS/第36回CSEC合同研究会

遭遇情報の確認 ユーザが認証局に遭遇情報の解読を依頼 認証局による遭遇情報の解読 遭遇情報の解読結果を依頼ユーザに送信 依頼ユーザのフレンドリストから総当たりでID照合 フレンドリストのサイズはID集合に比べて小さい 遭遇相手に対して、位置・時刻情報の提供依頼 遭遇情報の解読結果を依頼ユーザに送信 ID集合 フレンドリスト 遭遇情報 認証局 ユーザ 蓄積した遭遇情報をどのように解読するか詳しく説明する。 １．図を用いて説明 id1 → {id2, id3, ･･･, idN-1} id2 → {id1, id4, ･･･, idN} ・ idN → {id2} Data 解読結果 2007/3/1 第130回DPS/第36回CSEC合同研究会

認証局による解読 例：ユーザ2の遭遇情報 を解読する MD1, MD’1, MD2, MD’’1 解読作業①：ID照合 = 例：ユーザ2の遭遇情報　　　　　　　　　　　　　　　　を解読する MD1, MD’1, MD2, MD’’1 解読作業①：ID照合 MD1, MD’1 = 9850578321, 2359450622 9850578321 = MD[idx, 2359450622]? idx = id1 ユーザ2のフレンドリスト{id1, id4, ･･･, idN} 解読作業②：遭遇相手に位置・時刻情報の提供依頼 MD’1=2359450622, idx=id1 2359450622 = MD[id1, (100,200), 10:30] ? 以上より、MD1とMD’1を解読すると遭遇情報作成者ID・位置・時刻を求まる 他のハッシュ値を解読すると MD2ならば自身のID・位置・時刻、MD’’1ならば遭遇情報の作成者=送信者が求まる。 Data pos1=(100,200), time1=10:30 ユーザ1 7892935196, (86, 177), 10:00 2359450622, (100, 200), 10:30 4217981230, (152, 106), 12:00 9768769412, (92, 53), 18:00 MD1,MD’1 ： 遭遇情報作成者ID・位置・時刻 MD2 ： 自身のID・位置・時刻 MD’’1 ： 遭遇情報の作成者=送信者 2007/3/1 第130回DPS/第36回CSEC合同研究会

10分間一緒に行動していたユーザとの遭遇情報を全て持つ必要があるか？ 実装上の問題と工夫 問題点：小型端末のメモリ制限 メモリが一杯になると遭遇しても遭遇情報を蓄積できない 工夫:同一ユーザとの遭遇情報を必要数に抑える ユーザIDとは別の識別子を遭遇情報に付与 短期的なリンク不能性を諦める 識別子を定期的に変更 長期的なリンク不能性を満たす 10分間一緒に行動していたユーザとの遭遇情報を全て持つ必要があるか？ 提案方式における実装上の問題点と工夫 １．小型端末のメモリ制限 ２． 2007/3/1 第130回DPS/第36回CSEC合同研究会

性能評価 実装実験 シミュレーション実験 ハッシュ関数の計算時間を評価 パケット衝突を考慮した時に、遭遇情報をどの程度取得できるかを評価 小型端末MICAz MOTE上にハッシュ関数SHA-1を実装 シミュレーション実験 パケット衝突を考慮した時に、遭遇情報をどの程度取得できるかを評価 人の動きを記述可能なMobiREALシミュレータを利用 2007/3/1 第130回DPS/第36回CSEC合同研究会

評価結果：ハッシュ関数の計算時間 低性能な小型端末で 実装可能 MOTE ハッシュ関数の実装 提案方式は MOTEの性能 SHA-1（160bitハッシュ関数） 実行時間 データサイズ：1024 bit 1回の計算に約64 ms 提案方式は 無線通信機能 を搭載した センサーノード MOTEの性能 無線通信 ZigBee プログラムメモリ 128 kB クロック周波数 7.37MHz SRAM 4 kB ログ用メモリ 512 kB 低性能な小型端末で 実装可能 入力データサイズを変えて実験できない？ 無理ならこの話はしなくても良い 2007/3/1 第130回DPS/第36回CSEC合同研究会

性能評価：シミュレーション環境 ネットワークシミュレータMobiREALを利用 実験環境 人の動き 観測値に基づき現実的な人の流れを再現したUPFモビリティモデルを利用 パケット衝突 パケット衝突モデル： P ： パケット受信成功確率 N ： 1秒間のスロット数 （帯域/送信データサイズ） k ： 無線範囲内の送信パケット数 実験環境 エリア：大阪駅前500m四方 シミュレーション時間：600秒 ユーザ数：915人 データ送信間隔：5秒 帯域：250kbps 送信データ：40byte 通信帯域をスロットと呼ばれる単位に分割して、1パケットがそのスロットを占有します。同一スロットにパケットが入ったら衝突が起きると考えます。 この式は あるパケットに着目して、そのパケットが1つのスロットを占有します。 そのとき、残りk-1個のパケットがN-1個の他のスロットにいく確率を表しています。 2007/3/1 第130回DPS/第36回CSEC合同研究会

評価結果：遭遇情報取得率 滞在時間が送信間隔に近いほど、遭遇情報取得率は高い ⇒ 一緒に行動するユーザとの遭遇情報は90%以上取得可能 遭遇情報取得率＝（遭遇情報の取得数）/（実際に遭遇した人数）×100 無線半径が大きくなるとパケット衝突率が高くなる 取得率低下 シミュレーション結果です ユーザの無線範囲内滞在時間ごとに遭遇情報取得率を求めました。 無線範囲を5m～20mとして求めたグラフです 縦軸が取得率、横軸が無線範囲内滞在時間です。 この結果より、無線半径が大きくなるとパケット衝突率が高くなるため、取得率が低下していると読み取れる パケット衝突率は無線半径内のユーザ密度により決まり、 ここで半径5mのとき平均3.27人、半径20mのとき平均13.54人で取得率が98.5から91.9に減少している。 データ通信間隔が5秒であり、無線範囲内滞在時間が5秒なので・・・ シミュレーションは結果出そう？ 条件：データ送信間隔5秒、歩行速度2.0m/s、ユーザ数150人、無線範囲５～３０m（5m間隔） 無線範囲滞在時間（1秒、2秒、3秒、4秒、5秒）ごとに求めました この場合のノード密度は考慮したほうがよいですか？ ノード密度はそれほど高くないので、5秒以上だったらかなり精度は良いです。 4秒の場合もまあまあの結果が得られます ただ、無線範囲が狭いときは遭遇数自体がかなり少ないこともあるので、 これから確率をとるのか・・・どうなんだろう？思います ↑1つのノードだけに着目してデータをとっているから、遭遇数自体が少なくなる。 全てのノードについて、統計データをとることはできないのか？ シミュレーションをループさせればできるでしょう。難しくはないと思います。 無線範囲を広げるorノード密度を増やすようにすれば、遭遇数は増えるが、一方でパケット衝突の 影響が出てくる。「このくらいの密度（無線範囲内に何ノードいるか。ノード数、無線範囲に依存）で、 送信間隔このくらいなら、滞在時間ｘ秒以上のノードとの遭遇情報は確実に取得できます。」ということが言えればよい。 密度・・・遭遇ノード数 / 600秒 ユーザ密度　3.27人 → 13.54人　　取得率　98.5％ → 91.9％ 滞在時間が送信間隔に近いほど、遭遇情報取得率は高い ⇒ 一緒に行動するユーザとの遭遇情報は90%以上取得可能 2007/3/1 第130回DPS/第36回CSEC合同研究会

まとめ 本研究で行ったこと 今後の課題 小型端末を利用して匿名性を保ちながら遭遇情報の証拠性を保証する技術を提案した 現実の歩行流を再現したシミュレーションにより、 一緒に行動するユーザとの遭遇情報取得率が90%以上であることを確認した 今後の課題 シミュレーション評価 取得した遭遇情報から正しい移動経路が得られるか 様々な攻撃に対する頑強性の検討 実装実験 実環境における評価 まとめ 今後の課題 モビリティ評価・・・移動体についてどれくらいの間隔でパケットを投げれば良いか？ スケーラビリティ評価・・・集団でいる時に、どれくらいまでなら 位置推定手法の導入・・・携帯端末同士での遭遇時により正確な位置を求める 2007/3/1 第130回DPS/第36回CSEC合同研究会