1 Emerging Security Challenges for Ubiquitous Devices
15
In the second case the same pair of long term keys does not necessarily
correspond to the same epoch key during the next epoch. So an adversary that
may follow A and B in one phase cannot automatically continue to do so in the
next epoch.
1.3.3 Overloading Identifiers
The idea is to follow the approach used in human society: in everyday life we
do not use unique identifiers (like personal identification numbers), but ambiguous
identifiers such as first names (in Europe), family names (in China), etc. Despite the
fact that the same identifier is used by a large number of people, there is almost
no confusion in social interactions. For ubiquitous systems, we can mimic this
approach. Namely, we assume that:
• The number of devices is large, say N, however in each local environment the
number of devices is at most m, where m N,
• Apart from its main unique identifier, each device holds k identifiers from a pool
of size M, where M N and k is a small constant,
Now, the concept is that in a local environment each device occurs under one of
its short IDs [147]. The process of joining such an environment involves using
one of its short identities not yet in use there so far. The chances of having such
an identifier available might be surprisingly high due to the famous power-of-twochoices phenomenon [46]. The crucial point in this approach is to determine how
many short identifiers are needed globally, as minimizing their number provides
better privacy protection. One can show that this process proceeds successfully for
m participants (i.e., they always have the ability to choose an unused identifier) with
probability at least p if the number of short identifiers N is approximately
−
m k+1
(k+1) ln(1−p)
1/k
.
1.3.4 Pairwise Keys Evolution
If a device has no asymmetric cryptography implemented, then establishing a
bilateral key with another device is a problem. In small scale systems, we can deploy
such keys in a secure environment during the manufacturing phase. Unfortunately,
this is no longer possible in most large-scale application scenarios. So, the common
solution is to pair two devices in a private environment and hope that electronic
communication has not been tapped there. Only in a limited number of cases the
key (or some auxiliary information) can be carried by the user and inserted into
both devices. Indeed, a device may have no appropriate interface for such direct
15
In the second case the same pair of long term keys does not necessarily
correspond to the same epoch key during the next epoch. So an adversary that
may follow A and B in one phase cannot automatically continue to do so in the
next epoch.
1.3.3 Overloading Identifiers
The idea is to follow the approach used in human society: in everyday life we
do not use unique identifiers (like personal identification numbers), but ambiguous
identifiers such as first names (in Europe), family names (in China), etc. Despite the
fact that the same identifier is used by a large number of people, there is almost
no confusion in social interactions. For ubiquitous systems, we can mimic this
approach. Namely, we assume that:
• The number of devices is large, say N, however in each local environment the
number of devices is at most m, where m N,
• Apart from its main unique identifier, each device holds k identifiers from a pool
of size M, where M N and k is a small constant,
Now, the concept is that in a local environment each device occurs under one of
its short IDs [147]. The process of joining such an environment involves using
one of its short identities not yet in use there so far. The chances of having such
an identifier available might be surprisingly high due to the famous power-of-twochoices phenomenon [46]. The crucial point in this approach is to determine how
many short identifiers are needed globally, as minimizing their number provides
better privacy protection. One can show that this process proceeds successfully for
m participants (i.e., they always have the ability to choose an unused identifier) with
probability at least p if the number of short identifiers N is approximately
−
m k+1
(k+1) ln(1−p)
1/k
.
1.3.4 Pairwise Keys Evolution
If a device has no asymmetric cryptography implemented, then establishing a
bilateral key with another device is a problem. In small scale systems, we can deploy
such keys in a secure environment during the manufacturing phase. Unfortunately,
this is no longer possible in most large-scale application scenarios. So, the common
solution is to pair two devices in a private environment and hope that electronic
communication has not been tapped there. Only in a limited number of cases the
key (or some auxiliary information) can be carried by the user and inserted into
both devices. Indeed, a device may have no appropriate interface for such direct