In this paper, we propose the
network-based anonymization
and processing
(NAP) framework, the first system for
K
-
anonymous query processing in road networks. NAP relies
on a global user ordering and bucketization that satisfies
reciprocity and guarantees
K
-anonymity. We identify the
ordering characteristics that affect subsequent processing, and
qualitatively compare alternatives. Then, we propose query
evaluation techniques that exploit these characteristics. In
addition to user privacy, NAP achieves low computational and
communication costs, and quick responses overall. It is readily
deployable, requiring only basic network operations.
In the traditional spatial anonymity model, the data owner
(e.g., a location-based service) makes its data available using a
location server. It may, however, be the case that the owner is
outsourcing its database to a third-party (and, thus, untrusted)
location server. A challenge here is how to encrypt the owner’s
data so that they are hidden from the location server, while
it can still process anonymous queries. Another interesting
question is how (anonymous) users could verify that the
location server did not tamper with the original owner data.