スライド 1

Higashino Lab.
小型端末を利用した匿名性を持つ
遭遇履歴保証技術の提案
大阪大学大学院情報科学研究科
堺拓郎内山彰中村嘉隆東野輝夫
2007/3/1
第130回DPS/第36回CSEC合同研究会
1
Higashino Lab.
研究背景

位置情報、行動履歴を取得することが重要


米国のE-911（緊急通報サービス）
行動履歴の信頼性を高める


位置情報と遭遇情報を利用
しかし、サーバに遭遇情報を集中させることは望ましくない


情報漏えい、プライバシー
ユーザが自身の遭遇情報を蓄積し、必要時にサーバ
で解読する方式を考える

以下の特性を満たすようにする

2007/3/1
証拠性、リンク不能性
第130回DPS/第36回CSEC合同研究会
2
Higashino Lab.
研究目的
個人のプライバシーを尊重しながら，他者との遭遇情報に
関する証拠性を提示できるような遭遇情報保証技術を提案する
特徴
• 個人情報の保護を考慮
• リンク不能性を保持
• 証拠性を保証 [誰と・いつ・どこで]
• (RFIDなどの低性能な)小型端末向けの設計
リンク不能性：任意の二つのデータから，その二つが同じ者に
よって作成されたかどうかを判断できない
2007/3/1
第130回DPS/第36回CSEC合同研究会
3
Higashino Lab.
提案方式の概要 -遭遇情報の保証P1
P2

遭遇情報の交換

A
B
P3

P4
C


P1の遭遇情報
X72DCcXlw0kD
07/02/19, 9:00, P
2と交差点Aで遭遇
UKlw201[z.lxui
07/02/19, 9:20, ??と交差点Bで遭遇
10Dlxx/.zjo\^du
07/02/19, 9:40, P
4と交差点Cから一緒に行動

友人との遭遇情報のみが分かる
遭遇情報はリンク不能
第130回DPS/第36回CSEC合同研究会
位置推定手法の応
用、GPSなど
個人情報の保護


2007/3/1
無線通信可能な小型
端末を利用
遭遇時に互いの[ID,
位置, 時刻]（遭遇情
報）を交換・蓄積
位置，時刻の取得
遭遇情報の作成者を
判別不可
許可したユーザにの
み自分との遭遇情報
を公開
4
Higashino Lab.
提案方式の概要 -個人情報の保護ローカル
サーバ
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合同研究会
5
Higashino Lab.
提案方式の概要 -遭遇情報の確認[IDリスト]
(P1, P2, …, PN)
認証局

蓄積した遭遇情報を必要
時に認証局で解読

解読結果
P
[友人リスト]
P1:(P2, P4, …)
P2:(P1, …, PN)
…
提示
Data1
1
P1
認証局に依頼
P2
PN
遭遇相手の特定


許可されたユーザのみ
遭遇情報に改竄がないこと
の確認
Data1 ・・・・・・・・・・・・・・・・・・・・・・・・
07/02/19, 9:00, P
X72DCcXlw0kD
2, (100, 200)
07/02/19, 9:20, ??,
UKlw201[z.lxui
(100, 180)
07/02/19, 9:40, P
10Dlxx/.zjo\^du
4, (80, 180)
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
07/02/19, 11:30:00, End
「誰と」「いつ」「どこで」遭遇したかわかる
リンク不能性を満たす遭遇情報
2007/3/1
第130回DPS/第36回CSEC合同研究会
6
Higashino Lab.
提案方式の実現方法

個人情報の保護


各ユーザが自身の遭遇情報を蓄積する
認証局のみが、遭遇情報からIDに関する情報を得られる


許可されたユーザとの遭遇情報のみを知ることができる


認証局がユーザごとにフレンドリストを持つ
証拠性


仮定：端末xのID（idx）を知っているのは端末xと認証局のみ
ハッシュ関数を利用した遭遇情報の改ざん検証
リンク不能性

既存のハッシュ関数を用いたID照合を利用

Randomized Hash Lock方式
[10]
[10]S.A.Weis,
et al., “Security and
privacy aspects of low-cost radio frequency identification
2007/3/1
第130回DPS/第36回CSEC合同研究会
systems,” In Proc. of Security in Pervasive Computing, pp.201-212,2004.
7
Higashino Lab.
Randomized Hash Lock方式
サーバS ID集合
id1,
STEP1
id2,
・
R121,
, H =2860127359
MD[id
, R]
121,H=MD[id
,i i121]
・
ユーザi
STEP1：
ユーザが認証してもらうハッ
シュ値をサーバに送信する
STEP2：
サーバがID集合を利用して総
当りでID照合を行う
・
idN
STEP2
H = MD
id x , Rx],121]?
?
2860127359
= [MD[id
ユーザiの送信データ
時刻
t
乱数
R : 乱数、MD : ハッシュ値
ハッシュ値
121, 2860127359

各送信データは全く異なる

t+1
379, 7290821452
t+2
962, 4531475538
t+3
756, 3581742431
2007/3/1
idx = idi
リンク
不能
送信者が同一人物と分からない
リンク不能性を満たす
第130回DPS/第36回CSEC合同研究会
8
Higashino Lab.
遭遇情報の保証

遭遇情報の交換




遭遇情報の蓄積




[ID、位置、時刻]を含む情報(MD1, MD’1)を定期的に送信
他端末が自身の[ID、位置、時刻]を含む情報(MD2)を返信
再度IDを含む情報(MD’’1)を返信
他端末が送受信して得られた全ての情報を蓄積
自端末がMD’1と位置，時刻を蓄積
遭遇相手が自分と遭遇したことを保証
満たすべき特性


2007/3/1
MD：ハッシュ値 R：乱数
ユーザ1
MD1, MD’1
リンク不能性
証拠性
ユーザ2
MD2
MD’’1 , R1
第130回DPS/第36回CSEC合同研究会
9
Higashino Lab.
遭遇者の保証

[ID、位置、時刻]を含む情報（ハッシュ値）を交換

誰がその情報を作成したかは保証される


ただし、情報作成者＝情報送信者は保証されない
情報作成者=情報送信者の保証

方法1：送受信の時間制約


Δt
送信から受信までの時間制約を設ける
 ユーザ2の保証（MD1, MD’1～MD2）
 ユーザ1の保証（MD2～MD’’1）
ユーザ2
MD1, MD’1
MD2
MD’’1 , R1
Δt
方法2：遭遇情報の位置・時刻検証

2007/3/1
ユーザ1
自身の位置・時刻と遭遇相手の位置・時刻から検証可能
 お互いが通信可能な範囲にいるかどうか
第130回DPS/第36回CSEC合同研究会
10
Higashino Lab.
リンク不能性の検証

検証例

ユーザ1
ユーザ1が送信するデータ
ユーザ1,2が10:30～11:00
一緒に行動していた
MD1, MD’1
ユーザ2
9850578321,
MD
2359450622},
1={id1,, MD’
1},
MD’1={id1, (100,200), 10:30}
2359450622
時刻
10:30 9850578321, 2359450622
MD2
10:40 3144212347, 3510541847
MD’’1 , R1
10:50 2109471127, 7359875201
リンク
不能
MD’1={id1, pos1, time1}：
ID・位置・時刻を入力としたハッシュ 11:00 5194857291, 6113408287
値

MD1={id1, MD’1}：
IDとMD’を入力としたハッシュ値
2007/3/1
各送信データは全く異なる

送信者が同一人物と分からない
⇒ リンク不能性を満たす
第130回DPS/第36回CSEC合同研究会
11
Higashino Lab.
証拠性の検証

検証例

ユーザ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] ?

データ改竄があると、ハッシュ値が一致しない

2007/3/1
データ改竄を検出可能
⇒ 証拠性を満たす
第130回DPS/第36回CSEC合同研究会
12
Higashino Lab.
遭遇情報の確認


ユーザが認証局に遭遇情報の解読を依頼
認証局による遭遇情報の解読

依頼ユーザのフレンドリストから総当たりでID照合



フレンドリストのサイズはID集合に比べて小さい
遭遇相手に対して、位置・時刻情報の提供依頼
遭遇情報の解読結果を依頼ユーザに送信
ユーザ
遭遇情報
Data
解読結果
2007/3/1
認証局
ID集合
フレンドリスト
id1 → {id2, id3, ･･･, idN-1}
id2 → {id1, id4, ･･･, idN}
・
・
・
idN → {id2}
第130回DPS/第36回CSEC合同研究会
13
Higashino Lab.
認証局による解読

例：ユーザ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
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
2007/3/1
2359450622 = MD[id1, (100,200), 10:30] ?
MD1,MD’1 ：遭遇情報作成者ID・位置・時刻
MD2 ：自身のID・位置・時刻
MD’’1 ：遭遇情報の作成者=送信者
第130回DPS/第36回CSEC合同研究会
14
Higashino Lab.
実装上の問題と工夫

問題点：小型端末のメモリ制限


メモリが一杯になると遭遇しても遭遇情報を蓄積できない
工夫:同一ユーザとの遭遇情報を必要数に抑える
10分間一緒に行動していたユーザとの遭遇情報を全て持つ必要があるか？

ユーザIDとは別の識別子を遭遇情報に付与


識別子を定期的に変更

2007/3/1
短期的なリンク不能性を諦める
長期的なリンク不能性を満たす
第130回DPS/第36回CSEC合同研究会
15
Higashino Lab.
性能評価

実装実験

ハッシュ関数の計算時間を評価


小型端末MICAz MOTE上にハッシュ関数SHA-1を実装
シミュレーション実験

パケット衝突を考慮した時に、遭遇情報をどの程度取得で
きるかを評価

2007/3/1
人の動きを記述可能なMobiREALシミュレータを利用
第130回DPS/第36回CSEC合同研究会
16
Higashino Lab.
評価結果：ハッシュ関数の計算時間
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合同研究会
17
Higashino Lab.
性能評価：シミュレーション環境

ネットワークシミュレータMobiREALを利用



人の動き
 観測値に基づき現実的な人の流れを再現したUPFモビリティモデルを利用
パケット衝突
N -1 k -1
 パケット衝突モデル： P =
N
 P ：パケット受信成功確率
 N ： 1秒間のスロット数（帯域/送信データサイズ）
 k ：無線範囲内の送信パケット数
( )
実験環境






エリア：大阪駅前500m四方
シミュレーション時間：600秒
ユーザ数：915人
データ送信間隔：5秒
帯域：250kbps
送信データ：40byte
2007/3/1
第130回DPS/第36回CSEC合同研究会
18
Higashino Lab.
評価結果：遭遇情報取得率
遭遇情報取得率＝（遭遇情報の取得数）/（実際に遭遇した人数）×100
遭遇情報取得率（％）
100
無線半径
R=5m
R=10m
R=15m
R=20m
80
60
40
20
0
1
2
3
4
5
無線範囲内滞在時間（秒）
無線半径が大きくなるとパケット衝突率が高くなる
ユーザ密度 3.27人 → 13.54人
取得率低下
取得率 98.5％ → 91.9％
滞在時間が送信間隔に近いほど、遭遇情報取得率は高い
⇒ 一緒に行動するユーザとの遭遇情報は90%以上取得可能
2007/3/1
第130回DPS/第36回CSEC合同研究会
19
Higashino Lab.
まとめ

本研究で行ったこと



小型端末を利用して匿名性を保ちながら遭遇情報の証拠
性を保証する技術を提案した
現実の歩行流を再現したシミュレーションにより、一緒に
行動するユーザとの遭遇情報取得率が90%以上であるこ
とを確認した
今後の課題

シミュレーション評価



様々な攻撃に対する頑強性の検討
実装実験

2007/3/1
取得した遭遇情報から正しい移動経路が得られるか
実環境における評価
第130回DPS/第36回CSEC合同研究会
20

Download Report