Privacy-Preserving Two-Party Skyline Queries Over Horizontally Partitioned Data
Skyline queries are an important type of multi-criteria analysis with diverse applications in practice (e.g., personalized services and intelligent transport systems). In this paper, we study how to answer skyline queries efficiently and in a privacy-pres
- PDF / 272,524 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 23 Downloads / 182 Views
Department of Computer Science, North Carolina State University, Raleigh, USA {lchen10,rychirko}@ncsu.edu 2 Qatar Computing Research Institute, Hamad Bin Khalifa University, Doha, Qatar [email protected]
Abstract. Skyline queries are an important type of multi-criteria analysis with diverse applications in practice (e.g., personalized services and intelligent transport systems). In this paper, we study how to answer skyline queries efficiently and in a privacy-preserving way when the data are sensitive and distributedly owned by multiple parties. We adopt the classical honest-but-curious attack model, and design a suite of efficient protocols for skyline queries over horizontally partitioned data. We analyze in detail the efficiency of each of the proposed protocols as well as their privacy guarantees.
1
Introduction
Given a set of multi-dimensional vectors, a skyline query [8] is to find all the vectors that are not dominated by any other vector. Skyline queries are widely used in multi-criteria decision making applications, for example, personalized services, intelligent transport systems, location-based services and urban planning. In this paper, we study how to answer skyline queries over sensitive data distributedly owned by multiple parties who do not fully trust each other. Similar to many past efforts on other data analysis tasks [1,25,28,29], by adopting a secure multi-party computation setting, our goal is to design efficient and privacy-preserving distributed protocols to enable multiple data owners to collaboratively compute skyline queries without revealing their private inputs. Due to space limit, we focus on horizontally partitioned data where similar information about different individuals is collected in different organizations. Our approach for privacy-preserving skyline queries over horizontally partitioned data utilizes some existing secure protocols for basic operations, such as secure comparison protocols [10,30], secure vector dominance protocols [3,19,20], secure permutation protocols [12], secure equality-testing protocols [13,26], and secure multi-to-sum protocols [26,27]. To securely compute skyline queries, the secure protocol needs to address two problems: (1) how to securely determine c IFIP International Federation for Information Processing 2016 Published by Springer International Publishing Switzerland 2016. All Rights Reserved S. Foresti and J. Lopez (Eds.): WISTP 2016, LNCS 9895, pp. 187–203, 2016. DOI: 10.1007/978-3-319-45931-8 12
188
L. Chen et al.
whether a vector in one party dominates a vector in the other party? (2) how to securely apply the protocol of (1) to the set of vector pairs formed by pairing a vector V1 in one party A with each vector in the other party B, with the goal of determining whether V1 is dominated by any vector in party B or not. To address these two problems, straightforward compositions of such basic building blocks would not offer viable solutions. For example, existing techniques propose secure protocols to perform vector dominance checking, but they cannot
Data Loading...
