Databases Reference
In-Depth Information
same probability of being the real issuer. This is the situation described in
Example 2, in which the three users Alice, Bob, and Carl are the candidate
issuers identified from the generalized request
r
. In this case, for each gener-
alized request
r
, we call
anonymity set in context C
, denoted
Anon
C
(
r
), the
set of candidate issuers of
r
obtained exploiting context
C
.
Once the anonymity set is specified, it is possible to derive the correspond-
ing
uniform attack
:
2
I
,
we say that UAtt
C
is the
uniform attack based on anonymity set
Anon
C
if,
for each generalized request r
∈
Definition 3.
Given a context C and the complete function Anon
C
:
R
→
R and for each i
∈
I:
UAtt
C
(
r
,i
)=
0
Anon
C
(
r
)
if
i
∈
1
|Anon
C
(
r
)
|
otherwise
The above definition formalizes the idea that each user in the candidate
set
Anon
C
(
r
) has the same probability to be the actual issuer. The question
is when such an attack actually breaches the privacy of the issuer. We formally
define this in Definition 4.
The idea of Definition 4 is that a generalized request is safe if the (nor-
malization of the) attack associates it to the correct issuer with a likelihood
smaller than a threshold value
h
. Formally,
Definition 4.
Let Att
C
b
e an attack, h avaluein
[0
,
1)
and r
a generalized
request. Moreover, let Att be the function
Att
C
(
r
,i
)=
1
|I|
i
∈
I
:
Att
C
(
r
,i
)=0
if
∀
Att
C
(
r
,i
)
i
∈I
Att
C
(
r
,i
)
otherwise
We say tha
t r
is a
safe request against
Att
C
with threshold
h if, given i
=
issuer
(
r
)
, Att
C
(
r
,i
)
h.
If a request is not safe, we say that it is
unsafe
.
≤
For the uniform attack, the above safety definition is equivalent to asking
if
UAtt
C
(
r
,i
)
h
. Therefore, if
h
=1
/
3, then the request
r
in Example 2
is safe for Alice, while request
r
in the same example is not.
The task of the LTS is to avoid to forward to a SP a unsafe request. We
call
defense function
a generalization function that generates only requests
that are safe against a given attack.
≤
Definition 5.
Let Att
C
be an attack and h avaluein
[0
,
1)
. A generalization
function g
:
R
R is a
defense function against
Att
C
with threshold
h if
for each original request r
→
R such that g
(
r
)
is defined, g
(
r
)
is a safe request
against Att
C
with threshold h.
∈
For the context
C
st
in Example 2, a generalization function is a defense
function against
UAtt
C
st
with threshold 1
/
3 if the generalized request
r
pro-
duced by the generalization function always has its area containing at least
