DEIM Forum 2022 J43-4

TEE を備えた軌跡ベースのプライバシ保護型
接触追跡システムにおける付加情報の利用
Cao Ruixuan†

加藤 郁之††

曹洋††

吉川 正俊††† 京都大学工学部情報学科 〒 606-8501 京都市左京区吉田本町†† 京都大学大学院情報学研究科 〒 606-8501 京都市左京区吉田本町
あらまし 2019 年末より新型コロナウイルス感染症が蔓延しており，感染拡大防止のためにプライバシ保護型接触追跡システムが多く提案されている．しかし，既存の Bluetooth ベースの接触追跡システムには精度と柔軟性に欠けるという問題が存在している．さらに，新型コロナウイルスだけでなく，今後未知のウイルスが蔓延したとしても感染拡大防止に貢献できるような接触追跡システムが望ましい．そこで本研究は，プライバシ保護をしながら，軌跡デー
タと付加情報を利用して，より柔軟で精度が高く，未知のウイルスにも対応できる接触追跡システムを実現するための拡張手法を提案している．また，実際に提案した拡張手法を実装し，実行時間を測った結果，実用可能であることを示した．
キーワード Private Contact Tracing，新型コロナウイルス感染症，プライバシ保護，Trusted Execution Environment，Intel SGX
じたか否か，密閉空間にいたか否かなどの付加情報も扱うこと

1 はじめに2019 年末から流行し始めた新型コロナウイルス感染症は，驚異的な感染力で瞬く間に蔓延し，人々にとって予想していない
事態をもたらした．
新型コロナウイルス感染拡大防止のため，一般に保健所では感染者が出た際，該当の感染者に電話で聞き込み調査をし，過去二週間の濃厚接触者に該当する人に関しての情報を得る．この電話での聞き込み調査を全ての感染者に対して 1 人ずつ行っている．これは非常に膨大な作業量であり，多くの保健所は感染拡大期にはコールセンター状態になっている．もし，ある地
域の住民全員の移動軌跡データを取得して，感染者が発覚した
場合，住民全員とその陽性者の軌跡データを元に接触を追跡するシステムがあれば，保健所の人が 1 人 1 人電話をしなくて済むだろう．だが，市民の軌跡データ [1] というのは機微なパー
ソナルデータであり，それを扱うにはプライバシ保護を考慮す
る [2] ことが前提となる．
プライバシ保護型接触追跡システムの既存手法として，信頼できる実行環境のもと，軌跡データから空間的かつ時間的にどのくらい近いかを計算し，時間的近接性，空間的近接性の閾値を満たしていたら接したと判定する PCT-TEE [3] がある．しかしながら，このシステムには 2 つの不足点がある．(1) 距離ができれば，より柔軟で精度の良い接触追跡システムができると考えられる．
そこで本研究では，プライバシを保護しつつ，接触したか否かの判定条件を自由に決めることができる PCT-TEE で提案されたシステムを付加情報を使ってどのように拡張できるかを検討する．最終目標としては，将来未知のウイルスが発見されても (例えば，新型コロナウイルスとは違う経路で感染する新型のウイルスが蔓延しても)，プライバシを保護しながら，人々の軌跡データによる接触追跡ができるシステムを提案したい．
この論文における貢献を以下に示す：(1) 軌跡データに付加情報を追加することにより，PCT-TEE を拡張する方法を提案した．(2) 実際に提案した拡張手法を実装して，PCT-TEE の論文で検証に使われていた軌跡データを付加情報付きのものに拡張し，実行時間に関する実験を行った．
本稿の構成は以下の通りである．2 章では，プライバシを保護しながら接触を追跡するシステムに関する関連研究について述べる．3 章では，本研究における問題設定と提案手法について，4 章では本研究にて行った実験について述べ，5 章で本論文をまとめる．

2 関連研究が近くても遮りがある場合 (隣り合わせの車とバスなど) は接

新型コロナウイルス感染症拡大防止のため，Bluetooth を触していなくても接触したと判定してしまう．(2) 実際は接触

使った接触追跡システム [4] [5] [6] [7] [8] [9] は既に存在している

したから必ず感染するとは限らず，感染確率の計算をする機能

が，2 つの問題がある．1 つ目は，レストランなどで感染者ががない．この 2 点を改善することで，将来現れうる未知のウイ使ったシートを使用することで感染する場合などの間接的な接ルスにより柔軟に対応できるシステムを作ることができる．

触を検知することができないことである．2 つ目は，直接的なPCT-TEE の問題を改善するために，軌跡データを扱うだけ

接触の場合でも宅配を受け取るくらいの短時間の接触であればでなく，ユーザがマスクをしていたか否か，他者との会話が生感染の確率は低いが，Bluetooth ベースの接触追跡システムでは接触したと判定され，感染者との接触時間や距離の判定基準
を柔軟に変更できないことである．

言われている [11])，かつユーザ u はマスクをしており 2 人の間には会話がなかったというケースでは，ユーザ u の感染確率 p

本章では，プライバシを保護しながら接触を追跡するシステム

は極めて低いはずだ．従って，この場合は低い数値で接触確率に関する関連研究としてと信頼できる実行環境のもとで軌跡デーを出力することでより正確な接触追跡ができるだろう．本研究タを利用したプライバシ保護型接触追跡システム PCT-TEE [3]では，このようなケースをはじめとした，あらゆるケースを付について述べる．

加情報を使って正確に判定できるようにシステムを拡張したい．

2. 1 PCT-TEE

で，ユーザの軌跡データを利用して接触を検知する，軌跡デー  (u)(v)

1 ∃xi ∈ Xu , xj ∈ Xv s.t.



(u)
(v)
(u)
(v)
<
<
li − lj
Θgeo and ti − tj
Θtime
=
=



0( others )(1)

タベースの Private Contact Tracing (以下 PCT) という手法

上記の式 (1) の変数の定義は以下の通りである．

PCT-TEE は既存の Bluetooth ベースの接触追跡システムの問題を解決し，セキュアなハードウェア Intel SGX を使用することで構築可能な，信頼できる実行環境 TEE [10] のもとを使い，より安全で，効率の良い接触追跡システムを提案した．

PCT-TEE の接触追跡システムでは，医療機関が感染が確認された患者の軌跡データ (このデータは暗号化されているか，

•

li

(u)

: ユーザ u の i 番目の軌跡データの位置 (緯度，経度)

•

ti

(u)

: ユーザ u の i 番目の軌跡データの時間•Θgeo : 空間的近接性の閾値•Θtime : 時間的近接性の閾値


(i)
(i)
Xi = x1 , . . . , xn : Xi はユーザ i の軌跡データ集合，

患者の同意の下で公開されている) をクライアントから管理者が信頼されていないサーバに登録する．サーバは，クライアン
トからの問い合わせとして暗号化されたクライアントの軌跡
データを受け取り，サーバ内の軌跡データとクライアントの軌跡の交点を秘密裏に計算することで，感染リスクのある接触があったかどうかを示すブール値を返す．

•(i)

xn はユーザ i の n 番目の軌跡データ

保健所の問題にこれを適用すると，保健所が住民の暗号化された軌跡データをサーバに登録し，感染者が発覚した場合に，感染者の軌跡データを入力として問い合わせをすると，保健所
は住民の軌跡データの生データを知ることなく濃厚接触者を追跡することができる．

3 付加情報を利用したプライバシ保護型接触追跡手法

まず，基本的な時空間近接性の判定について式 (1) で説明する．例えば，ユーザ m の軌跡データを(m)x1 = (2022/1/11 13 : 30 : 00, 35.67, −65.34),

 (m)

Xm = 
 x2 = (2022/1/11 13 : 31 : 00, 35.34, −65.69), (m)x3 = (2022/1/11 13 : 32 : 00, 35.67, −65.34)

説明を行う．

とし，ユーザ n の軌跡データを(n)x1 = (2022/1/11 13 : 27 : 00, 22.67, −77.67),

 (n)

Xn = 
 x2 = (2022/1/11 13 : 28 : 00, 25.21, −72.43), (n)x3 = (2022/1/11 13 : 29 : 00, 28.88, −67.22)

3. 1 問 題 設 定として，Θgeo = 10，Θtime = 3 とすると，x2

本章では，まず接触追跡タスクの問題設定について述べ，次に，具体的に考えうる付加情報やシステムの拡張方針について

まず，本研究において，時刻データと位置データの対をポイ
ントレコードと呼び，一つ以上のポイントレコードから成る時
系列データを軌跡データと呼ぶ．

(m)

(n)

と x3

など

が式 (1) の上段の条件を満たしており，ユーザ m と n は時間的近接性と空間的近接性を満たしていると判定される．
一方で，上記の判定方法は厳密すぎて効率が悪いので，PCT-

次に，本研究において想定してるシステムは，サーバ側にはTEE では軌跡データを xyz 軸をそれぞれ経度，時間，経度と大量の住民の軌跡データが保存されており，感染者が発覚した

した三次元の地理的時間的空間 A にマッピングし，計算効率を場合，サーバ側に保存されているユーザ u となる住民一人一人の軌跡データ Xu と，ユーザ v となる感染者の軌跡データ Xv

高めている．図 1 を使って説明すると，ユーザ m の軌跡データ
を Xm = (x1 , x2 , x3 )，ユーザ n の軌跡データを Xn = (x4 , x5 )を地理的時間的空間にマッピングし，交わりを計算することで，とすると，x1 は部分空間 A1 に含まれており，x2 , x3 , x4 , x5 は接触を検知する．ただ，接触の際の環境やユーザの状態によっ部分空間 A2 に含まれている．これにより，軌跡データ Xm はて感染の確率が変わるので，付加情報 a を用いてより正確な感部分空間 A1 , A2 にマッピングされ，Xn は A2 にマッピングさ

染確率 p を計算できるようにする．例を挙げて言うと，これまれる．両者は部分空間 A2 で時間的近接性と空間的近接性を満での手法では，ユーザ u と感染者 v が空間的近接性と時間的近接性を満たせば，この 2 人は接触したと判定していた．しかし，感染者 v が新型コロナウイルス感染症ワクチンを既に二回接種していて (ワクチンを接種していれば人に移す可能性は低いとたしているので，接触したと判定される．
上記を踏まえて，PCT-TEE で定式化された式をベースに，
軌跡データに付加情報を加えて問題を定式化すると，以下のよ
うな式になる．

表1

システム拡張の分類

拡張の種類

付加情報の具体例

暴露時間に関する拡張

付加情報を使わない

感染確率に関する拡張

年齢，性別，過去の感染歴，基礎疾患の有無，ワクチンの接種回数など
マスク着用の有無など

接触判定に影響する拡張 自家用車の中にいた，バスにいた，教室にいたなど

3. 2 システムの拡張手法
まず，想定するシステムの構造について説明する．システム
は軌跡データ，空間的近接性の閾値，時間的近接性の閾値をクエリとして受け取り，回答として感染確率を返す．回答を構成するアルゴリズムは，接触判定パートと感染確率計算パートの2 部分に分かれている．
接触判定パートでは，軌跡データの位置情報と時間情報が空
間的近接性と時間的近接性を満足しているか否かで接触判定を
図1

地理的時間的空間における接触判定 (この図は PCT-TEE [3] の図 2 を参考に作成した)行う．接触判定の結果，接触したと判定された場合，付加情報を使って感染確率計算パートで感染確率を計算し，それを出力する．接触していない場合は，0 という確率を出力する．つまり，システムの拡張を考える際，接触判定パートと感染確率計 
p ∃A(u) ∩ A(v) =| ∅ s.t.


n 

o


(u)
(u)
(u)

A = f Θ xi
| xi ∈ Xu and
o

n 
(v)
(v)


| xj ∈ X v
A(v) = fΘ xj0 (others)

算パートを独立として考えても問題はない．上記の内容を踏まえた上で，より多くの種類のクエリに対応するためには，以下のような 3 通りの拡張が考えられる．

(2)
暴露時間に関する拡張接触判定パートで，軌跡データから接触の暴露時間を計算し，空間的近接性，時間的近接性だけでなく，暴露時間の上記の式 (2) の変数の定義は以下の通りである．

••

p : クライアントがウイルスに感染した確率


(u)
(u)
(u)
(u)
ai = ai1 , ai2 , . . . , ain : ユーザ u の i 番目の軌跡データの付加情報，添字 1，2，. . . ，n は付加情報の種類を表す•

Ai ∈ A : Ai は i 番目の部分空間，
A は全部分空間の集合•fΘ : x → A : 軌跡データ x を部分空間 A にマッピングする関数

これらを用いて以下のように入力と出力を設定する．

閾値も満たしていたら接触と判定するように拡張する．この拡張により，暴露時間も考慮したより柔軟な接触判定条
件を指定できる．
感染確率に影響を与える付加情報に関する拡張
この拡張では，感染確率計算パートで付加情報を扱い，システムが感染確率を計算できるようにする．付加情報は，(1) ユーザ自身にのみ関係する付加情報と (2) ユーザ自身だけでなく，他者の感染確率にも影響を与えうる付加情報の 2 種類あり，これによって感染確率計算に使う関数の種類が異なる．
接触判定に影響を与える付加情報に関する拡張
この拡張では，システムの接触判定結果に影響を与えうる

入力•

付加情報を含んだユーザ i の軌跡データ






(i)
(i) (i)(i)(i)(i) (i)X i = x 1 = t1 , l 1 , a 1 , . . . , x n= tn, ln , a(i)n•空間的近接性の閾値 Θgeo•

時間的近接性の閾値 Θtime

付加情報を扱い，接触判定の精度を高める．
拡張の分類と対応するクエリの種類を表にまとめると，表 1のようになる．
また，各々の拡張に関して，具体的にどのような付加情報を使うか，詳しい拡張の方針について以下に示す．

3. 2. 1 暴露時間に関する拡張
出力

この拡張は PCT-TEE でも説明されており，式 (2) を少し拡•

ユーザの感染確率 p

このように接触追跡問題を定式化し，正確な感染確率を出力することを目標とする．

張し，以下の式 (3) のようにすると実現できる．


max(pi ) ∃τ s.t. ∀i = (τ, τ + 1, . . . , τ + Θdoe )






∃A(u) ∩ A(v) =| ∅ s.t.


n 

o
(u)
(u)
(u)
A = f Θ xi
| xi ∈ Xu and

n 

o 


(v)
(v)

A(v) = fΘ xj| xj ∈ X v





0( others )
(3)

表2
年齢

仮定となる感染確率

感染確率

過去の感染歴感染確率

10 代未満

0.7

有

0.1

10 代

0.5

無

0.9

20 代

0.3

30 代

0.8

基礎疾患

40 代とそれ以上 0.6
性別Θdoe は暴露時間 (duration of exposure) の閾値を表し，入力と出力は以下のようになる．

感染確率

有

0.7

無

0.3

感染確率

女性

0.4

男性

0.6

入力

•

付加情報を含んだユーザ i の軌跡データとすると，ユーザ m とユーザ n が接触して，実際にユーザ m が感染する確率は，
(i)(i) (i)(i)(i)(i) (i)(i)= tn, ln , an
X i = x 1 = t1 , l 1 , a 1 , . . . , x n•

空間的近接性の閾値 Θgeo•

時間的近接性の閾値 Θtime•

暴露時間の閾値 Θdoe(m)p = f (ai(n)

) · g(ai )となる．
より具体的な例で述べる．これらの付加情報は互いに独立しているもので，関数 f と g は各々の確率を掛け合わせることで出力•導出できると仮定すると，以下のように式が得られる．

ユーザの感染確率 p

p = p年齢 × p性別 × p過去の感染歴 × p基礎疾患 × . . .

ここで，暴露期間は接触したと判定されたケースの数をユー
ザごとに連続してカウントしている．出力の感染確率は，全ての接触判定されたケースにおいて，つまり接触とカウントされている軌跡データの一点ごとに感染確率を計算し，最大の数

ユーザ m が持つ付加情報を以下のように定義し，
(m)

ai

=(

個目の軌跡データで接触したと判定されていたら，5 個目から10 個目の軌跡データを一個ずつ感染確率を計算し，最大値をi = (6, 7, 8, 9) か τ = 7，i = (7, 8, 9, 10) ) になるので，p5 ，p6 ，
p7 ，p8 ，p9 ，p10 の中の最大値 max(pi ) が感染確率となる．
3. 2. 2 感染確率に影響を与える付加情報に関する拡張
この拡張では，まず PCT-TEE を使って接触判定を行い，その結果接触したと判定された場合，付加情報を引数とした関数
によって確率を計算する．

= (性別) 女,

ユーザ n がもつ付加情報を以下のように定義すると，
(n)

ai

=(

(n)

(n)

ai1 = (年齢)40, ai2 = (性別) 女,(n)(n)
ai3 = (過去の感染歴) 無, ai4 = (基礎疾患) 有 . . .)このユーザの感染確率とする．これを上記の式 (3) に当てはめると，Θdoe = 3 で，τ = 5， i = (5, 6, 7, 8) (または τ = 6，(m)

= (年齢)20, ai2(m)(m)
ai3 = (過去の感染歴) 有, ai4 = (基礎疾患) 無 . . .),値を最終的な感染確率とする．例えば，１分ごとに軌跡データ
をとり，暴露期間の閾値が 3 だったとすると，5 個目から 10

(m)

ai1

となる．
付加情報別の感染確率を表 2 のようにすると 1 ，ユーザ m の感染確率は，

p=f ·g= p年齢=20 × p性別=女 × . . . × p過去の感染歴=無 × p基礎疾患=有= 0.3 × 0.4 × 0.1 × 0.3 × 0.6 × 0.4 × 0.9 × 0.7a ) ユーザ自身にのみ関係する付加情報
ここで扱う付加情報は，年齢，性別，過去の感染したことがあるか否か，基礎疾患の有無，ワクチンの接種回数など自分の= 0.36%となる．

属性に当たるものだ．ここで感染確率計算に使う関数は，各々b ) 他者の感染確率にも影響を与えうる付加情報のユーザの付加情報により決まり，他のユーザの付加情報に影

これに該当する付加情報は，例えばマスク着用の有無である．

響されない．

新型コロナウイルス感染症対策では，「マスクは相手のウイルス

具体的には，ユーザ m の各々の属性を引数として，ウイル
スに感染する確率を関数
(m)

f (ai

年齢

(m)

, ai

性別

(m)

, ai

過去の感染歴吸入量を減少させる効果より，自分からのウイルス拡散を防ぐ効果がより高く，仮に 50 センチの近距離に近づかざるを得な

(m)

, ai

基礎疾患の有無(m), ai

ワクチンの接種回数, . . .)

かった場合でも，相手だけがマスクを着用するより，自分だけがマスクを着用する方が，より効果が高い」[12]．一方，未知ので表し，感染者であるユーザ n がウイルスを感染させる確率をウイルスでは，マスクの効果は相手だけが着用する方が効果が関数

高いかもしれない．未知のウイルスも対応できるようなシステ

(n)

g(ai

年齢

(n)

, ai

性別

(n)

, ai

過去の感染歴(n), ai

基礎疾患の有無(n), ai

ワクチンの接種回数, . . .)

1：ここで使っている確率の値は医学的根拠のない架空の数値である．

ムを開発するには，このような想定もする必要がある．この場合，感染確率計算に使う関数は自分の付加情報だけでなく相手の付加情報も引数としたものでなければならない．
具体的には，ユーザ m とユーザ n が接触したとすると，ユー
ザ m が感染する確率は，(m)p = h(ai(n)

マスク着用の有無, . . . , ai

マスク着用の有無, . . .)となる．ここで，関数 h の定義を以下のように仮定する．

(m)
(n)


0.05, aiマスク着用の有無 = 有 and aiマスク着用の有無 = 有




(n)
0.25, a(m)iマスク着用の有無 = 無 and aiマスク着用の有無 = 有
hi =
(m)
(n)


0.3,
ai
= 有 and ai=無
マスク着用の有無
マスク着用の有無



(m)
(n)
0.4,
ai
= 無 and ai=無
マスク着用の有無

マスク着用の有無(m)

上記の仮定のもと，ユーザ m がマスクをしており (ai(m). . . , ai ==(マスク着用の有無) 有, . . .))，ユーザ n もマスクをしている
(n)

(ai

(n)

ai

図2

= (. . . ,実装したシステムのアーキテクチャ(この図は PCT-TEE [3] の図 3 を参考に作成した)

= (マスク着用の有無) 有, . . . ) 場合，ユーザ m の感染確率は，いと判定する．また，ユーザ B とユーザ C は付加情報の値が(m)p = h(ai(n), ai ) = 0.05

同じつまり同じバスに乗っているため，与えられた閾値を満足しているか否かによって接触判定を行う．

である．

3. 2. 3 接触判定に影響を与える付加情報に関する拡張
ここで扱う付加情報は，自家用車の中にいた，バスにいた，教室にいたなどの密閉空間に関連するものである．例えば，現した際，位置情報が近い距離にあるので接触したとされるが，しなければならない．
上記のシステムを実現するために，付加情報を利用した拡張としては，車やバス，教室に番号をつけ，同じ番号の空間にい験

本章では，第 3 章で提案した拡張手法を実際に実装し，その在のシステムでは，自家用車を運転していて，バスの隣に停車
実際は車とバスによる遮りがあるので，接触していないと判定

4 実

実装をもとに実験を行う．今回の実験の目的は，軌跡データに付加情報を追加したことによって，PCT-TEE と比べて，どのくらい実行時間が増加するのか，またその実行時間は実用上許容範囲であるかを検証することだ．

4. 1 実装についてた人同士のみで，接触判定を行うなどが考えられる．具体的に

PCT-TEE の論文で実装されていたシステム 2 をもとに，第は，番号 1 の車を運転しているユーザ A とその車の隣の番号3 章で述べた付加情報の追加を必要とする拡張である感染確率

2 のバスに乗っているユーザ B とユーザ C がいたとして，密に影響を与える付加情報に関する拡張と接触判定に影響を与え

閉空間の番号を 3 つ目の付加情報とすると，ユーザ A の軌跡

る付加情報に関する拡張を実装 3 した．ハッシュ化された軌跡

データ XA には付加情報として車の番号 1 が入っており，



(A)
(A)
(A)
xn
= t(A)= (77, 88), a(A)= (a(A)n , lnnn1 = . . . , an3 = 1, . . .)データに，年齢，過去の感染歴の有無，ワクチンの接種回数，
 マスク着用の有無，密閉空間の番号，合計 5 種類の付加情報を追加したデータに対して接触判定を行い，接触したと判定されとなり，ユーザ B の軌跡データ XB は付加情報としてバスのた場合，ユーザの id とそのユーザの最大の感染確率 4 を出力す

番号 2 が入っており，るように拡張した．また，PCT-TEE の実装では，軌跡データ

 の格納に使うデータ構造は Hashtable の他に，FST というハッ
(B)
(B)
x(B)
= t(B)= (77, 88), a(B)= (a(B)nn , lnnn1 = . . . , an3 = 2, . . .)シュ化された軌跡データを高速に扱えるデータ構造も使用可能となり，ユーザ C の軌跡データ XC は，であったが，今回の実装では，簡単のため，データの格納には

 Hashtable を用いた．

(C)
(C)
(C)
= 2, . . .)= . . . , anx(C)= t(C)= (77, 88), a(C)= (annn , lnn
3
1
実装したシステムのアーキテクチャを図 2 に示す．ここでは，となり，このとき，軌跡データの位置情報 l は 3 人とも同じになっているが，付加情報の値をみると，ユーザ A はユーザ B
やユーザ C とは別の番号になっているので，システムは付加情報により，ユーザ A がユーザ B やユーザ C とは接触していな

2：https://github.com/ylab-public/PCT
3：https://github.com/Hisokalalala/PCT
4：ここで最大としている理由は，接触が複数回あった場合，各々の感染確率のうち最大のものを出力するためである．

表3

データセットのサイズ (この表は PCT-TEE [3] の表 8 を参考に作成した)
図 3 PCT-TEE の結果

クライアント側のデータ サーバ側のデータ
ニューヨーク20160 × 100

20160 × 1000

近畿

1440 × 100

1440 × 14000

東京

1440 × 100

1440 × 14000
図4

本研究のシステムの結果サーバ側に感染者のデータが格納され，クライアントが住民である場合を想定している 5 ．サーバ側のデータは政府や保健所などの公的機関から感染者の軌跡データと付加情報を入手し，それをハッシュ化したのち，共通鍵を使って暗号化し，信頼できる実行環境 (Enclave) へ送る．信頼できる実行環境の中でサーバ側のデータを復号化し，キーを軌跡データのハッシュ値，値を付加情報としたハッシュマップを使ってサーバ側のデータをマッピングする．クライアント側のデータも同様に，ハッシュ化したしたのちに共通鍵で暗号化し，これを信頼できる実行環境に送る．信頼できる実行環境の中で復号化し，データをクエリとして保持し，先ほどハッシュマップに格納したサーバ側のデータと Private Set Intersect (PSI) による比較をする．比較の結果，軌跡データのハッシュ値が一致した場合，その時点で

図5

クライアントサイズ=100 での両手法の実行時間の両者の付加情報を使って感染確率を計算し，それを結果に格納し，結果を共通鍵で暗号化する．暗号化された結果を信頼でが 100 人おり，この 100 人のクライアントを 2 週間にわたってきる実行環境から外部 に送り，復号化すれば，接触があると1 分ごとに軌跡データを記録した場合，クライアント側のクエ判定されたクライアントの id と感染確率が出力される．

リデータには，

614(日) × 24(時間) × 60(分) = 20160

4. 2 実 験 内 容
まず，実験に使うデータセットの軌跡データは，PCT-TEEの論文で使われていた軌跡データと同じものを使う．具体的には，scikit-mobility 7 に実装された密度 EPR モデル [13] によって生成される合成データセットと東京大学空間情報科学研究センターの共同研究利用システム 8 で入手可能な，日本の特定の地域における人々の軌跡のデータを使った実データセット 9 である．合成データセットは，ニューヨーク市における 14 日間の 1 分ごとの個人の軌跡データであり，実データセットは，日本の近畿 10 と東京 11 の人の流れデータセットを使って作成してある．

より，それぞれのクライアントが長さ 20160 個の軌跡データを持っている．従って，この 100 人のクライアントは合計 2016000
個のポイントレコードがある．
これらのデータセットを使い，本研究の実装でサーバ側のデータを格納する際のデータ構造に Hashtable を用いて確率の計算を可能にした実装と PCT-TEE の実装でデータ構造に

FST を使った際の実行時間を比較する．
4. 3 実 験 結 果
まず，PCT-TEE と本研究で実装したシステムの接触判定

データセットのサイズを表 3 に示す．具体的に述べると，の結果 12 を図 3 と図 4 に示す．本研究のシステムの結果は，ニューヨークのクライアント側のクエリデータはクライアント

PCT-TEE で接触したと判定されたクライアントの id と一致しており，その id ごとに感染確率を出力している 13 ．

5：PCT-TEE がそのような前提で実装されていたので，こちらでもその前提で

図 5 では，表 3 で述べたデータセットを使って実行した際の図を書いた．逆の場合でも，つまり，サーバ側に住民のデータを入れ，クライア

実行時間を比較した結果を示す．この図から，PCT-TEE では

ントを感染者のデータを使うことは可能であり，データを変更すれば良いだけで

FST をデータ構造に使っているため，Hashtable を使っているある．

6：ここでいう外部は信頼できる実行環境の外という意味であり，システムの内本研究より PCT-TEE の方が実行速度は速いことが分かる．し部である．

かし，その差は 2 倍程度であり，付加情報を追加したデータで7：https://github.com/scikit-mobility/scikit-mobility

感染確率を計算する実行時間としては十分許容範囲であると思

8：https://www.csis.u-tokyo.ac.jp

われる．

9：正確には，これらの人の流れのデータセットは，実際の軌跡から精巧に作られた合成データセットであるが，本研究ではこれらのデータセットを実際のデータセット

また，図 6 と図 7 でより大きいクライアントサイズを使ってとみなす．データ作成の具体的なプロセスの詳細についてはこちらのサイトに記載されている http://pflow.csis.u-tokyo.ac.jp/data-service/pflow-data/．

12：ここでは，クライアントサイズが 10 の時の結果を示している．

10：https://joras.csis.u-tokyo.ac.jp/dataset/show/id/3038201000

13：実験用のデータを作成する際付加情報を全て同じ値にしたので，ここでの感

11：https://joras.csis.u-tokyo.ac.jp/dataset/show/id/3000200800

染確率は全て同じ値が出力されている．

図6

クライアントサイズ=500 での実行時間 (本研究のメモリ増加前
図8と増加後を含む)

図7

クライアントサイズ=1000 での実行時間 (PCT-TEE のメモリ

図9

フェーズごとの実行時間

手法ごとのクライアントサイズと実行時間の関係

増加前と増加後を含む)

実行時間が長いが，二倍程度の差である 16 ．また，本研究の手実行した時の両手法の比較結果を示す 14 ．これらの図で使われているメモリという用語について説明する．Enclave を起動する際，conﬁg ファイルに書かれている設定をもとに初期化する．
初期化した際のヒープ領域のメモリサイズを超えた場合，私が実行した限りだとメモリ割り当てエラーが発生し，実行が失敗する．これに対処するために，conﬁg ファイルでヒープ領域のサイズを増やす必要があるが，Enclave を起動する際の初期化に時間がかかるようになる．つまり，クライアントサイズをより大きくした場合，メモリ増加前では実行に必要なメモリを確保することができず，実行が失敗してしまうため，conﬁg ファ
イルの設定をすることにより使えるメモリ領域を増やして，大きいクライアントサイズでも実行可能とした．そのトレードオ
フとして，Enclave を起動する際，メモリ増加前より時間がかかるようになる 15 ．
図 6 の本研究の手法 (メモリ増加前) のグラフと PCT-TEE(メモリ増加前) のグラフに注目すると，先ほどと同じように，本研究の手法 (メモリ増加前) は PCT-TEE(メモリ増加前) より

法のメモリ増加前とメモリ増加後のグラフからわかるようにメモリを増加した場合は，Enclave を起動する際の初期化に時間がかかり，実行時間がメモリ増加前より圧倒的に増えていることが分かる．
同様に，図 7 の本研究の手法 (メモリ増加後) のグラフとPCT-TEE(メモリ増加後) のグラフに注目すると，両方メモリ増加後でもやはり実行時間は PCT-TEE の方が短いが，その差は高々二倍であり，許容範囲である．また，PCT-TEE のメ
モリ増加前のグラフ 17 とメモリ増加後のグラフを比較してみると，やはりメモリ増加後の実行時間が圧倒的に長いことより，

Enclave の初期化に時間がかかっていることがわかる．
ここで，本研究の手法と PCT-TEE のメモリ増加前とメモ
リ増加後のフェーズごとの実行時間を図 8 に示す．図 8 より，メモリ増加前とメモリ増加後の実行時間の差分はほぼ Enclaveの初期化の部分だけであり，実際に接触判定をする計算処理の実行時間は許容範囲の速度で実行している．
図 9 に，手法ごとの全体の実行時間をクライアントサイズご16：ニューヨークのデータを本研究の手法で実行するにはメモリが足りず，メモ

14：ここで使ったデータセットは，サーバ側のデータは表 3 と同じであるが，ク

リ増加前の実行時間のデータは存在しない

ライアント側のデータはクライアントのサイズが異なる．

17：ニューヨークのデータをメモリ増加前の PCT-TEE で実行するにはメモリ

15：ただし，Enclave の初期化にかかる時間はどのシステムでもほぼ等しいが足りず，メモリ増加前の実行時間のデータは存在しない

とに示している．図からわかるように，クライアントサイズが大きくなるにつれ，実行時間はほぼ線形的な増加をしている．
このことより，クライアントサイズが非常に大きくなっても，[2]

ほぼ線形的な増加なので，許容範囲の実行速度で実行可能であると思われる．
つまり，軌跡データに付加情報を追加しても，プライバシ保[3]

護型接触追跡システムとして実用化可能である．

5 ま と め

[4]

本研究では，プライバシ保護をしながら，軌跡データを利用した接触追跡システムをベースに，付加情報を利用して，より柔軟で精度が高く，未知のウイルスにも対応できる接触追跡シ[5]

ステムを実現するための拡張手法を提案している．そして，実際に軌跡データに付加情報を追加したデータを使って接触判定を行い，接触したクライアントの感染確率も計算し，それを出[6]

力するシステムを実装した．実験では，このシステムの実行時間を測り，それが PCT-TEE の実行時間とどれくらいの差があ[7]

るかを調べ，実用上では許容範囲内であることを検証した．今後の課題については以下にまとめる．

(1) 付加情報の最大許容サイズと最適サイズを探す．本研究の実験では，一つの付加情報が 1 バイトで，追加した付加情[8]

報は 5 個なので，合計 5 バイト分の付加情報を追加した軌跡データを使った．ここで，付加情報が大きくなった場合，[9]Intel SGX のリソースがメモリ制約の関係でページングに時間がかかり，実行時間が非常に長くなる恐れがあるので，許容できる最大の付加情報のサイズと，最適なサイズを探[10]索する余地がある．

(2) 他のデータ構造を使った実装を試す．本研究では，簡単のためサーバ側のデータを Hashtable を使って格納したが，[11]

FST を使ってデータを格納することによって，ハッシュ化
された軌跡データをより高速に扱うことができ，実行時間[12]を縮めることが可能だと思うわれる．また，年代や性別などの個人の属性を表す付加情報は変化がないため，軌跡
データの中で，全ての行にこれらの属性データを持つ必要はなく，データ構造を工夫して作れば，より高速なシステ
ムになる可能性がある．
最後に，本研究がプライバシ保護型接触追跡システムの中でも未知のウイルスにも対応できるようなあらゆる判定条件を設定できる高精度なシステムとして，新型コロナウイルスだけでな
く今後の疫病対策として貢献できることを期待する．

謝辞

本研究は，JST CREST JPMJCR21M2， JST SICORP JP-

MJSC2107， 科学研究費 21K19767， 19K20269， KDDI 財団調査研究助成の支援を受けたものである．

文[1] HUMAN RIGHTS WATCH.

献
Mobile location data and[13]

covid-19: Q&A, 2020. https://www.hrw.org/news/2020/
05/13/mobile-location-data-and-covid-19-qa.
Hyunghoon Cho, Daphne Ippolito, and Yun William
Yu.
Contact tracing mobile apps for covid-19: Privacy considerations and related trade-oﬀs. arXiv preprint
arXiv:2003.11511, 2020.
Fumiyuki Kato, Yang Cao, and Masatoshi Yoshikawa. PCTTEE: Trajectory-based Private Contact Tracing Systemwith Trusted Execution Environment. ACM Transactions
on Spatial Algorithms and Systems (TSAS), Vol. 8, No. 2,
pp. 1–35, 2022.
Yanan Da, Ritesh Ahuja, Li Xiong, and Cyrus Shahabi.
React: Real-time contact tracing and risk monitoring via
privacy-enhanced mobile tracking. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp.
2729–2732. IEEE, 2021.
Johannes K Becker, David Li, and David Starobinski.
Tracking anonymized bluetooth devices. Proc. Priv. Enhancing Technol., Vol. 2019, No. 3, pp. 50–65, 2019.
Yaron Gvili. Security analysis of the covid-19 contact tracing speciﬁcations by apple inc. and google inc. IACR Cryptol. ePrint Arch., Vol. 2020, p. 428, 2020.
Ronald L Rivest, Jon Callas, Ran Canetti, Kevin Esvelt,
Daniel Kahn Gillmor, Yael Tauman Kalai, Anna Lysyanskaya, Adam Norige, Ramesh Raskar, Adi Shamir, et al.
The pact protocol speciﬁcation. Private Automated Contact
Tracing Team, MIT, Cambridge, MA, USA, Tech. Rep.
0.1, 2020.
Ni Trieu, Kareem Shehata, Prateek Saxena, Reza Shokri,
and Dawn Song. Epione: Lightweight contact tracing withstrong privacy. arXiv preprint arXiv:2004.13293, 2020.
Carmela Troncoso, Mathias Payer, Jean-Pierre Hubaux,Marcel Salathé, James Larus, Edouard Bugnion, Wouter
Lueks, Theresa Stadler, Apostolos Pyrgelis, Daniele Antonioli, et al. Decentralized privacy-preserving proximity
tracing. arXiv preprint arXiv:2005.12273, 2020.
Mohamed Sabt, Mohammed Achemlal, and Abdelmadjid Bouabdallah. Trusted execution environment: what
it is, and what it is not.
In 2015 IEEE Trustcom/BigDataSE/ISPA, Vol. 1, pp. 57–64. IEEE, 2015.
厚生労働省. 感染症専門医が解説！ 分かってきたワクチンの効果と副反応, 2021. https://www.cov19-vaccine.mhlw.go.jp/
qa/column/0001.html.
厚生労働省. 新型コロナウイルスに関する Q&A（一般の方向け）,
2021.
https://www.mhlw.go.jp/stf/seisakunitsuite/bunya/kenkou_iryou/dengue_fever_qa_00001.html#Q4-1.
Luca Pappalardo, Filippo Simini, Salvatore Rinzivillo, Dino
Pedreschi, Fosca Giannotti, and Albert-László Barabási.
Returners and explorers dichotomy in human mobility. Nature communications, Vol. 6, No. 1, pp. 1–8, 2015.