匿名性を有する位置情報特定システム

Higashino Lab.
Certification of Secure Encounter History
Among Low Power Mobile Sensors
Takurou Sakai†, Akira Uchiyama†,
Yoshitaka Nakamura‡ and Teruo Higashino†
†Osaka
University
‡Nara Institute of Science and Technology
Higashino Lab.
Research Background



As the progress of wireless network, it has been easy for users to
acquire information about the location.
Many location-based services have been proposed.
Existing location-based services

Use only location information



“Alice arrived at the school.”
“Bob got through the entrance gate.”
Encounter information with friends might help to increase
“emotional trust” in location-based services.

Examples


Encounter information “Alice is in the park now with her friend ‘Bob’.” eases
her parents’ mind than just knowing that “Alice is in the park now.”
At the same time, we also need to consider user privacy.


2015/9/30
Each user does not want to tell his/her name to unknown persons.
Each person’s encounter information should not be public.
ICDF2008
2
Example Application :
Children
Security System
Alice
Carol
Higashino Lab.
House
Landmark
Bob
Recommended Route
Park
Dave
Teacher
School
・In Japan, children go to their school along the recommended safe routes.
・A system to obtain encounter histories of children might ease their parents’ mind.
2015/9/30
ICDF2008
3
Example Application :
Children Security System
Higashino Lab.
8:00,
House
House
8:08,
Park
8:05,
Bob
Landmark
Recommended Route
Park
8:22,
Dave
8:25,
Teacher
School
Alice
Bob
8:30,
School
・ Alice goes to school with Bob. They met Dave and their teacher, and then they
arrive at school. Those information are much safer than just knowing “Alice
arrives at school”.
2015/9/30
ICDF2008
4
Example Application :
Children Security System
Higashino Lab.
House
Landmark
Recommended Route
Alice’s Actual Route
Deserted
Park
Alice
School
•If Alice goes to school alone and passes the deserted park, and if passing the park
is prohibited for safety reason, Alice’s parents can recognize that Alice passes a
wrong route.
5
2015/9/30
ICDF2008
Higashino Lab.
Problem : User Privacy
Alice
Server

*****
8:35,
*****
Dave
Ellen
*****
8:30,
*****
Dave
Carol
8:08,
8:08,
Landmark
Landmark
*****
Alice
Alice
*****
Bob
Bob
Carol
*****
8:22,
*****
Alice
Bob
Dave
8:05,
*****
Ellen
*****
Carol
*****
8:25,
*****
Alice
Bob
Teacher
8:00,
*****
Carol
*****
Teacher
School
8:30,
Landmark
*****
Alice
*****
Bob
Problem


*****
8:05,
House
*****
Landmark
*****
8:05,
Alice
*****
Alice
Bob
Without user privacy, everyone can acquire the information of others.
To solve this problem,


No one can recognize who creates the information.
Each user can obtain the information involving him/her.
2015/9/30
ICDF2008
6
Higashino Lab.
Research Goal

We propose a secure technique for gathering encounter
information with friends.

GPS



Implement the technique on low power sensors



It might not be used in some places such as underground city.
It also consumes much energy power.
We rely sensors called “landmarks” for knowing accurate locations.
Landmarks are assumed to be deployed on walls of buildings/houses.
User privacy


2015/9/30
Encounter information should have strong anonymity (Unlinkability)

No one can recognize whether senders of multiple encounter
information are the same or not.
Encounter information with Alice can be decoded by Bob iff Alice has
allowed its decoding to Bob in advance.
ICDF2008
7
Higashino Lab.
System Model

Landmarks (fixed node)




Sparsely deployed over the service area.
Provide accurate location information
and time.
Some of them are connected to the
Internet.
Users (mobile node)


Data
[Landmark List]
(id, private key)
[User List]
(id, private key, friend list)
Interne
t
・
・
・
Hold low power sensors.
Each user manages his/her own Local
Server


Local Servers
Certification
Authority
Landmarks
Accumulation of his/her encrypted
encounter information
Certification Authority (CA)

Maintains



Landmark List : (id, private key)
User List : (id，private key，friend list)
Decodes the encrypted encounterICDF2008
information with landmarks and friends.
2015/9/30
Users
8
Higashino Lab.
Overview
Alice
Gathering
Process
Decoding
Process

CA
[Alice’s friend list]
Fred
No!
Ellen
No!
No!
Dave
Who?
Who?
Who?
Who?
Bob!
…
Bob
…
Yes!
Gathering Process



Bob
Bob periodically broadcasts a beacon.
If Alice receives the beacon, she obtains encrypted encounter information by
encounter information gathering protocol.
Decoding Process


Alice sends the encrypted encounter information to CA.
CA decodes the encrypted encounter information.

Searches the sender of the information using all members in Alice’s friend list.
2015/9/30

CA sends Alice
ICDF2008 with the searched friend (Bob).
the encounter information
9
Higashino Lab.
Our Approach

Gathering Process : Encounter Information Gathering Protocol

For the design on low power sensors, we use




We design it so that the encounter information has Unlinkability.
Encounter information has the digital evidence of encounter on the following
assumptions.


Hashed Message Authentication Code (HMAC) – hash function
Advanced Encryption Standard (AES) – symmetric-key encryption
Assumptions :
 Each user holds his/her own terminal.
 Each node does not communicate with others via another node.
Estimation Process of Encounter Location and Time

We design it under the following conditions about low power sensors :


Without a GPS device
Without an accurate timer.
2015/9/30
ICDF2008
10
Higashino Lab.
Unlinkability
Encrypted Sending Data
Private Key
Data
Random Value
Gwgqase
2571051
`P?{`>}+?
No one can recognize whether the senders of these data are the same or not.

To achieve unlinkability,


Other users only recognize the sending data as a random bit sequence.
In our technique,

Each node encrypts its sending data with a random value.


Encryption of a random value creates a random bit sequence.
The random value is created by a pseudo-random number generator.
2015/9/30
ICDF2008
11
Higashino Lab.
Digital Evidence of Encounter
Alice
Encrypted Data using HMAC
MAC1 (beacon)
Private Key
Δt
Data
Received MAC value
Δt
Random Value

MAC (Alice)
MAC2 (Bob)
To achieve the digital evidence of encounter

Encounter information have to be created



Bob
only by encounter nodes.
only when they encounter.
In our technique

Each node encrypts its sending data with the received MAC value using HMAC.


HMAC achieves authentication and detection of falsification.
Each node sends and receives the data in the fixed time interval (Δt).
 Encounter
2015/9/30
information are always
created within 2*Δt since sending a beacon. 12
ICDF2008
Higashino Lab.
Estimation of Encounter Region
P2
S1
Encounter Region
P1
A
Vmax：maximum speed of pedestrians
120 * Vmax
B
150 * Vmax
7:00 P1 encountered a landmark at A
7:02 P1 moved with P2 from around B

If an user terminal does not have a GPS device:


The elapsed time from when the encounter information is obtained from
the latest landmark is provided.
The encounter region can be estimated based on movable
distance of users within the elapsed time.
2015/9/30
ICDF2008
13
Determination of
Time Sequence of Encounter
Ek1
Ek2
k1
H[Ek1]
H[Ek2]
H[Ek1]

Ekn-1
・・・
H[Ekn-2]
H[Ek2]
H[Ekn-1]
H[Ekn-2]
kn-1
Ekn
kn
H[Ekn-1]
hash-chain can be used to determine the time sequence of encounter.


k2
Higashino Lab.
The user needs to encounter with node k1 in order to calculate a hash value of
encounter information Ek1 (H[Ek1]) since a hash function is an one-way
operation.
The n-th encounter information Ekn includes (n-1)-th hash value
(H[Ekn-1]), which denotes the hash value of the latest encountered
node
((n-1)-th node).
2015/9/30
ICDF2008
14
Higashino Lab.
Another Application :
Construction Inspection History System
•Construction inspection is important for our safety life.
•However, there are the problems that the inspectors might forget
and/or not take enough time to check inspection points because they
have to inspect many places in large buildings.
Sensors are deployed at the places to be inspected.
（ + Each person has a wireless tag.）
ID=104
•Where did inspectors check?
• How long did they stay there?
2015/9/30
ICDF2008
15
Higashino Lab.
Evaluation

Landmark Deployment Cost

Evaluated



the number of landmarks for an example scenario.
It assumes a city around Tokyo.
Energy/Memory Consumption


Assume low power sensors ‘MOTE’ as user terminals.
Evaluated


The lifetime of the battery.
The time when encounter information
can be accumulated.
MICAz MOTE
A Sensor with Wireless Module (ZigBee)
2015/9/30
ICDF2008
16
Evaluation :
Landmark Deployment Cost

Service Model (left figure)



Children form a small group and go
to their school together
We assume a typical district in a city
around Tokyo.
If landmarks are deployed

At each of the two intersections,


School district



Size : 2.07km2
 1.44 km * 1.44 km
Road length : 91 m
# of Intersection : 256
2015/9/30

landmark
We need 64 landmarks.
Only on the recommended school
routes,


Higashino Lab.
We need less landmarks.
Therefore, this service can be
provided using a small number of
landmarks.
ICDF2008
17
Evaluation :
Energy/Memory Consumption
Energy Consumption of Various Algorithms


The energy consumption of SHA-1 is similar to that of AES.
The energy consumption of SHA-1 (192 bytes input) is 1/270 times as much as
that of RSA.
When a user terminal receives one encounter information per 10
seconds,



Energy Consumption on MOTE
We have evaluated typical SHA-1 hash algorithm.


Higashino Lab.
The lifetime of the battery is 12 days without charging.
Encounter information can be accumulated for 6 hours on only its memory.
Therefore, the energy/memory consumption of our technique are
2015/9/30
ICDF2008
small.
18
Higashino Lab.
Conclusion

Summary

We have proposed a secure technique for gathering encounter
information with friends.



We have evaluated our technique from two aspects :



Unlinkability.
the digital evidence of encounter.
Cost for landmark deployment.
Energy and Memory Consumption.
Future Work

We are planning to improve reliability of Certification Authority.


2015/9/30
To improve digital evidence of encounter information.
To use encounter information for alibi.
ICDF2008
19
Higashino Lab.
Thank You
2015/9/30
ICDF2008
20
Higashino Lab.
2015/9/30
ICDF2008
21

Download Report