基于PIR的私密位置查询：无需第三方匿名
下载需积分: 9 | PDF格式 | 492KB |
更新于2025-01-08
| 130 浏览量 | 举报
在现代移动设备日益普及的背景下，位置定位服务（Location-Based Services, LBS）已经成为日常生活中的常见工具。然而，随着位置数据的收集和使用，用户的隐私保护问题愈发突出。传统的解决方案通常依赖于一个可信的匿名器，即用户与LBS之间的中介，以隐藏用户的真实位置信息。这种架构存在明显的局限性：
首先，所有用户必须信任第三方匿名器，这意味着如果这个中心节点被攻击或滥用，用户的隐私就可能暴露。这构成了一个单点故障的风险，一旦匿名器被破坏，所有用户的隐私保护都会失效。
其次，大量的用户需要相互合作并信任彼此，才能确保隐私安全。这种协作机制在现实应用中难以实现，尤其是在大规模用户群体中，管理和维护这样的信任关系复杂且不可靠。
再者，现有的方法只能提供用户位置的临时保护，无法抵御针对用户历史行为的关联攻击。例如，攻击者可以通过分析用户的位置记录来推断出他们的日常活动模式，从而侵犯隐私。
为了解决这些问题，本文提出了一种基于私有信息检索（Private Information Retrieval, PIR）理论的新框架，用于支持私有位置依赖查询。PIR是一种密码学技术，它允许用户从多个数据源中检索信息，而无需泄露查询的具体信息。在该架构中，用户无需信任任何第三方，也不需要依赖其他用户的合作，就能安全地向LBS发送位置相关的查询。
新框架的优势在于它的安全性、效率和易用性。它消除了对单点的信任依赖，降低了隐私泄露的风险。同时，由于PIR的特性，即使攻击者获取了部分交互信息，也无法推断出用户的具体位置。此外，由于该方法不需要用户之间的合作，私有查询可以在任何数量的用户之间进行，增加了系统的灵活性。
然而，实现这样的私有查询框架需要克服一些技术挑战，包括提高查询效率，尤其是在大量数据和实时性要求较高的场景下。同时，密码技术的应用可能增加计算复杂性和能耗。但总体而言，这种基于PIR的私有查询方案为LBS的隐私保护提供了一个新颖且有前景的方向，有助于平衡位置服务的便利性和用户隐私的需求。
2. We develop algorithms for approximate and exact pri-
vate nearest neighbor search. We utilize data mining
techniques to optimize query execution.
3. We show experimentally that the cost is reasonable;
hence our methods are applicable in practice.
2. RELATED WORK
Most existing approaches for private location-dependent
queries follow the user-anonymizer-LBS framework of Fig-
ure 1. The anonymizer sends to the LBS a Cloaking Region
(CR) instead of the actual user location; this procedure is
called cloaking. Ref. [11] combines spatial with temporal
cloaking. Each query q specifies a temporal interval δt that
the corresponding user u is willing to wait. If within δt,
K − 1 other clients in the vicinity of u also issue queries,
all these queries are combined in a single CR; otherwise, q
is rejected. In Casper [20], the anonymizer maintains the
locations of the clients using a pyramid data structure, sim-
ilar to a Quad-tree. Assume u asks a query and let c be the
lowest-level cell of the Quad-tree where u lies. If c contains
enough users (i.e., |c| ≥ K), c becomes the CR. Otherwise,
the horizontal c
h
and vertical c
v
neighbors of c are retrieved.
If |c ∪ c
h
| ≥ K or |c ∪ c
v
| ≥ K, the corresponding union of
cells becomes the CR; otherwise, the anonymizer retrieves
the parent of c and repeats this process recursively. In-
terval Cloak [14] is similar to Casper in terms of both the
data structure used by the anonymizer (a Quad-tree), and
the cloaking algorithm. The main difference is that Interval
Cloak does not consider neighboring cells at the same level
when determining the CR, but ascends directly to the an-
cestor level. Casper and Interval Cloak guarantee privacy
only for uniform distribution of user locations.
Hilbert Cloak [17] uses the Hilbert space filling curve to
map the 2-D space into 1-D values. These values are then
indexed by an annotated B
+
-tree. The algorithm partitions
the 1-D sorted list into groups of K users (the last group
may have up to 2K − 1 users). For querying user u the
algorithm finds the group to which u belongs, and returns
the minimum bounding rectangle of the group as the CR.
The same CR is returned for any user in a given group.
Hilbert Cloak guarantees privacy for any distribution of user
locations.
The previous approaches assume a static snapshot of user
locations and do not consider correlation attacks (e.g., his-
tory of user movement). In [5], correlation attacks are han-
dled as follows: At the initial timestamp t
0
, cloaking region
CR
0
is generated, which encloses a set AS of at least K
users. At a subsequent timestamp t
i
, the algorithm com-
putes a new anonymizing region CR
i
that encloses the same
users in AS, but contains their locations at timestamp t
i
.
There are two drawbacks: (i) As users move, the resulting
CR may grow very large, leading to prohibitive query cost.
(ii) If a user in AS disconnects from the service, the query
must be dropped. Furthermore, in [5] it is assumed that
there are no malicious users.
Privacy in LBS has also been studied in the context of
related problems. In [3], the CR is a closed region around
the query point, which is independent of the number of users
inside. Given CR, the LBS returns the probability that each
candidate result satisfies the query based on its location with
respect to the CR. Ref. [6], on the other hand, eliminates
the anonymizer by organizing users in a Peer-to-Peer sys-
tem. The querying user u searches his neighborhood until
he finds K − 1 other peers, which are used to construct the
CR. However, u tends to be close to the center of the CR;
therefore an attacker can identify u with high probability.
Ref. [12] also uses a Peer-to-Peer system to support dis-
tributed anonymization; although a centralized anonymizer
is not required, all users must trust each other. More rele-
vant to our work is the approach of [18]: In a preprocessing
phase, a trusted third party transforms (using 2-D to 1-D
mapping) and encrypts the database. The database is then
uploaded to the LBS, which does not know the decryption
key. All users possess tamper-resistant devices which store
the decryption key, but they do not know the key them-
selves. Users send encrypted queries to the LBS and decrypt
the answers to extract the results. The method assumes that
none of the tamper-resistant devices is compromised. If this
condition is violated, the privacy of all users is threatened.
Our work builds on the theoretical results of Private In-
formation Retrieval (PIR), which is defined as follows: a
server S holds a database with n bits, X = (X
1
. . . X
n
). A
user u has a particular index i and wishes to retrieve the
value of X
i
, without disclosing to S the value of i. The PIR
concept was introduced in [4] in an information theoretic
setting, requiring that even if S had infinite computational
power, it could not find i. It is proven in [4] that in any solu-
tion with a single server, u must receive the entire database
(i.e., Θ(n) cost). Nevertheless, in practice, it is sufficient
to ensure that S cannot find i with polynomial-time com-
putations; this problem is known as Computational PIR.
[19] showed that the communication cost for a single server
is Θ(n
ε
), where ε is an arbitrarily small positive constant.
Our work employs Computational PIR.
Several approaches employ cryptographic techniques to
privately answer NN queries over relational data. Most of
them are based on some version of the secure multiparty
computation problem [13]. Let two parties A and B hold ob-
jects a and b, respectively. They want to compute a function
f(a, b) without A learning anything about b and vice versa.
They encrypt their objects using random keys and follow a
protocol, which results into two “shares” S
A
and S
B
given to
A and B, respectively. By combining their shares, they com-
pute the value of f. In contrast to our problem (which hides
the querying user from the LBS), existing NN techniques as-
sume that the query is public, whereas the database is parti-
tioned into several servers, neither of which wants to reveal
their data to the others. Ref. [25] assumes vertically parti-
tioned data and uses secure multiparty computation to im-
plement a private version of Fagin’s [8] algorithm. Ref. [23]
follows a similar approach, but data is horizontally parti-
tioned among the servers. The computation cost is O(n
2
)
and may be prohibitive in practice. Ref. [1] also assumes
horizontally partitioned data, but focuses on top-k queries.
More relevant to our problem is the work of [16] which
uses PIR to compute the NN of a query point. The server
does not learn the query point and the user does not learn
anything more than the NN. To achieve this, the method
computes private approximations of the Euclidean distance
by adapting an algorithm [9] that approximates the Ham-
ming distance in {0, 1}
d
space (d is the dimensionality). The
cost of [16] is
˜
O(n
2
) for the exact NN and
˜
O(
√
n) for an ap-
proximation through sampling. The paper is mostly of the-
oretical interest, since the
˜
O notation hides polylogarithmic
factors that may affect the cost; the authors do not provide
any experimental evaluation of the algorithms.
剩余11页未读，继续阅读
相关推荐
santiago0450
- 粉丝: 1
- 资源: 7
我的内容管理
展开
最新资源
- eclipse中文教程
- excelvba设计教程
- 网络协议分类大全 图解
- 存储--基础知识（090202）(1)
- AutoCAD快捷键大全.txt
- 悟透javascript
- 西门子通用型变频器工程师手册
- CC++bianchengguifan.pdf
- PHP与MySQL WEB开发(第四版)(En).pdf
- oracle帮助文档
- 企业员工通讯录管理系统
- Struts_in_Action中文版
- Cambridge.Press.Security.and.Quality.of.Service.in.Ad.Hoc.Wireless.Networks.
- Oracle10g安装、升级、卸载和使用
- mysql-4th-edition-developers-library
- 企业人事管理系统的设计与实现
