Speedy Privacy-Preserving Skyline Queries on Outsourced Data

Abstract

Supporting efficient and secure skyline query services on outsourced data remains an ongoing challenge, given the fact that existing solutions either incur significant overhead due to the underlying algorithm traversing the entire dataset or raise privacy issues when specific data structures are introduced. Motivated by addressing these limitations, this work proposes the Speedy and Privacy-Preserving Skyline Query scheme (SPSQ) to support efficient skyline queries that preserve the privacy requirements of datasets, skylines, queries, and indirect privacy with low online computational costs. SPSQ is an optimized distributed skyline diagram constructed by a novel privacy-preserving set intersection with the deduplication algorithm. Moreover, it converts the skyline queries into a lightweight polynomial-based private information retrieval for diagrams to reduce user-perceived latency. The quadrant skyline is extracted directly while the retrieval scale of the dynamic skyline is rapidly reduced by around 100$\times$. We also carefully analyze its security and conduct experimental evaluations on different datasets. The results show that our SPSQ is more efficient than current works, and it is at least an order of magnitude faster in computational complexity than the state-of-the-art with the same security level.

This work was supported in part by the National Natural Science Foundation of China (Grant No. 62102430, No. 62122092, No. 62032005, No. 62072466), Science Research Plan Program by NUDT (Grant No. ZK22-50), and Education Ministry-China Mobile Research Funding under Grant No. MCM20170404.

Appendices

Appendix

Appendix A     Security Analysis with Simulation

We construct a polynomial-time simulator $\mathcal {S}$ with the ideal process for $\mathcal {F}_{\textbf {SDG}}$ such that for any probability polynomial time (PPT) adversary $\mathcal {A}$, no environment $\mathcal {Z}$ can tell with non-negligible probability whether it is interacting with $\mathcal {A}$ and the real protocol or with $\mathcal {S}$ in the ideal process for $\mathcal {F}_{\textbf {SDG}}$. We describe the real view ${\textbf {Real}}_{\mathcal {A}}$ and the simulated view ${\textbf {Ideal}}_{\mathcal {A},\mathcal {S}}$ as follows.

In the ${\textbf {Real}}_{\mathcal {A}}$, given the inputs $\texttt{P}_{j_1+1,j_2+1}$ and $\texttt{I}_{j_1+1,j_2+1}$, CS and ES calculate the index vector $\texttt{IV}_{j_1,j_2}$ with three generated skylines $\texttt{S}_{j_1+1,j_2}$, $\texttt{S}_{j_1,j_2+1}$ and $\texttt{S}_{j_1+1,j_2+1}$ by ${\textbf {SSE}}$ and ${\textbf {SSC}}$, and exchanges the obfuscated skyline shares $\texttt{S}_T^{\prime \prime \prime }$ with some pseudorandom numbers $\pi$ and r by ${\textbf {SSM}}$ and ${\textbf {SSH}}$. CS and ES select the final set intersection and compute the skyline $\texttt{S}_{j_1,j_2}$ with inputs $\texttt{P}_{j_1+1,j_2+1}$, $\texttt{I}_{j_1+1,j_2+1}$ and ${\textbf {0}}$ by ${\textbf {SSH}}$. Finally, they hold the shared skyline $\left\langle \texttt{S}_{j_1,j_2}\right\rangle$.

In the ${\textbf {Ideal}}_{\mathcal {A},\mathcal {S}}$, recall that $\mathcal {S}$ interacts with the ideal functionality $\mathcal {F}_{\textbf {SDG}}$ and with the environment $\mathcal {Z}$. Simulator $\mathcal {S}$ starts by invoking a copy of $\mathcal {A}$ and running a simulated interaction of $\mathcal {A}$ with $\mathcal {Z}$ and parties running the protocol [3].

• 1. Simulating the communication with $\mathcal {Z}$: Every input value that $\mathcal {S}$ receives from $\mathcal {Z}$ is written on $\mathcal {A}$’s input tape (as if coming from $\mathcal {A}$’s environment). Likewise, each output written by $\mathcal {A}$ on its output tape is copied to $\mathcal {S}$’s output tape (to be read by $\mathcal {S}$’s environment $\mathcal {Z}$).

• 2. Simulating the case where CS only is corrupted: $\mathcal {S}$ begins by activating $\mathcal {A}$ and internally sending it the message that $\mathcal {A}$ (controlling CS) expects to receive from ES in a real execution. Simulator $\mathcal {S}$ externally sends CS’s input (i, j) and $(\left\langle \texttt{S}_{j_1+1,j_2}\right\rangle ^{\text {C}},\left\langle \texttt{S}_{j_1,j_2+1}\right\rangle ^{\text {C}},\left\langle \texttt{S}_{j_1+1,j_2+1}\right\rangle ^{\text {C}})$ to $\mathcal {F}_{\textbf {SDG}}$ and receives back the output $(i,j,\xi _1,\xi _2)$. Then, $\mathcal {S}$ simulates $\left\langle \texttt{S}_1\right\rangle ^{\text {E}}\in _R\mathbb {Z}_N^{\xi _1},\left\langle \texttt{S}_2\right\rangle ^{\text {E}}\in _R\mathbb {Z}_N^{\xi _2}$ and simulates ES interacting with CS in the internal interactions to receive $\left\langle \texttt{IV}\right\rangle ^{\text {E}}$. Next, when $\mathcal {A}$ sends the message $\left\langle \pi _{c}\right\rangle ^{\text {E}}$ from CS to ES, $\mathcal {S}$ simulates $\left\langle \pi _{e}\right\rangle \in _R\mathbb {Z}_N^{\xi \times \xi }$ and sends $\left\langle \pi _{e}\right\rangle ^{\text {C}}$ to CS. $\mathcal {S}$ simulates $\left\langle r\right\rangle ^{\text {E}}\in _R\mathbb {Z}_N^{\xi }$ and simulates ES interacting with CS in the internal interactions to receive $\left\langle \texttt{S}_T^{\prime \prime \prime }\right\rangle ^{\text {E}}$ for computing the final set intersection. Finally, $\mathcal {S}$ simulates $\left\langle \texttt{P}_{j_1+1,j_2+1}\right\rangle ^{\text {E}}\in _R\mathbb {Z}_N$ and $\left\langle \texttt{I}_{j_1+1,j_2+1}\right\rangle ^{\text {E}}\in _R\mathbb {Z}_N$, and simulates ES interacting with CS to construct $\left\langle {\textbf {0}}\right\rangle$ to output the final skyline $\left\langle \texttt{S}_{j_1,j_2}\right\rangle$.

• 3. Simulating the case where ES only is corrupted: $\mathcal {S}$ begins by activating $\mathcal {A}$ and internally sending it the message that $\mathcal {A}$ (controlling ES) expects to receive from CS in a real execution. Simulator $\mathcal {S}$ externally sends ES’s input (i, j) and $(\left\langle \texttt{S}_{j_1+1,j_2}\right\rangle ^{\text {E}},\left\langle \texttt{S}_{j_1,j_2+1}\right\rangle ^{\text {E}},\left\langle \texttt{S}_{j_1+1,j_2+1}\right\rangle ^{\text {E}})$ to $\mathcal {F}_{\textbf {SDG}}$ and receives back the output $(i,j,\xi _1,\xi _2)$. Then, $\mathcal {S}$ simulates $\left\langle \texttt{S}_1\right\rangle ^{\text {C}}\in _R\mathbb {Z}_N^{\xi _1},\left\langle \texttt{S}_2\right\rangle ^{\text {C}}\in _R\mathbb {Z}_N^{\xi _2}$ and simulates CS interacting with ES in the internal interactions to receive $\left\langle \texttt{IV}\right\rangle ^{\text {C}}$. Next, when $\mathcal {A}$ sends the message $\left\langle \pi _{e}\right\rangle ^{\text {C}}$ from ES to CS, $\mathcal {S}$ simulates $\left\langle \pi _{c}\right\rangle \in _R\mathbb {Z}_N^{\xi \times \xi }$ and sends $\left\langle \pi _{c}\right\rangle ^{\text {E}}$ to ES. $\mathcal {S}$ simulates $\left\langle r\right\rangle ^{\text {C}}\in _R\mathbb {Z}_N^{\xi }$ and simulates CS interacting with ES in the internal interactions to receive $\left\langle \texttt{S}_T^{\prime \prime \prime }\right\rangle ^{\text {C}}$ for computing the final set intersection. Finally, $\mathcal {S}$ simulates $\left\langle \texttt{P}_{j_1+1,j_2+1}\right\rangle ^{\text {C}}\in _R\mathbb {Z}_N$ and $\left\langle \texttt{I}_{j_1+1,j_2+1}\right\rangle ^{\text {C}}\in _R\mathbb {Z}_N$, and simulates CS interacting with ES to construct $\left\langle {\textbf {0}}\right\rangle$ to output the final skyline $\left\langle \texttt{S}_{j_1,j_2}\right\rangle$.

• 4. Simulating the case that neither party is corrupted: In this case, $\mathcal {S}$ receives a message $\left\langle \texttt{S}_{j_1,j_2}\right\rangle$ signaling it that CS and ES concluded an ideal execution with $\mathcal {F}_{\textbf {SDG}}$. $\mathcal {S}$ then generates a simulated transcript of messages between the real parties. That is, $\mathcal {S}$ obtains the length of inputs L. In each cell, $\mathcal {S}$ simulates the input $\texttt{P}_{j_1+1,j_2+1}^*\in _R\mathbb {Z}_N$ and $\texttt{I}_{j_1+1,j_2+1}^*\in _R\mathbb {Z}_N$ of length 1, simulates the dummy points ${\textbf {0}}$ of length $L-1$, and extracts the simulated history $\texttt{S}_{j_1+1,j_2}^*$, $\texttt{S}_{j_1,j_2+1}^*$ and $\texttt{S}_{j_1+1,j_2+1}^*$ of corresponding length. After that, $\mathcal {S}$ forms the simulated input $\texttt{P}_{j_1+1,j_2+1}^*$ and $\texttt{I}_{j_1+1,j_2+1}^*$, and runs $\mathcal {F}_{\textbf {SDG}}$ to output the result $\texttt{S}_{j_1,j_2}^*$ by the experiment.

The shared inputs and outputs are indistinguishable from uniformly chosen random numbers. Based on the simulator $\mathcal {S}$, no PPT adversary can distinguish the output of ${\textbf {Ideal}}_{\mathcal {A},\mathcal {S}}$ from that of ${\textbf {Real}}_{\mathcal {A}}$. That is, ${\textbf {Ideal}}_{\mathcal {A}, \mathcal {S}, \mathcal {Z}} {\mathop {\approx }\limits ^{\textrm{c}}} {\textbf {Real}}_{\mathcal {A}, \mathcal {Z}}$.

In $\mathcal {F}_{\textbf {SDG}}$, the adversary only knows the final size of each cell since adding some dummy points to the intermediate result, and then there is some leakage about the distribution of points in the dataset. However, the adversary cannot derive values from the data distribution because the skylines are invisible.

The adversary knows nothing in $\mathcal {F}_{\textbf {SPE}}$ since we add dummy points to all the cells to make the size the same. Opening $\texttt{m}$ does not make more information leakage occur in $\eta$ due to the random coefficients. Therefore, The leakage of $\mathcal {F}_{\textbf {SPE}}$ is only related to the degree t of the polynomial, but $t=2$ ensures safety when the skylines in the cell are not identical and visible.

Appendix B    Details for Skyline Diagram

Table 3 illustrates examples of averages, $\bar{n}$ is at least two orders of magnitude smaller than n, thus effectively reducing the retrieval size. Concretely, when $n=9000$, ours 22491 secure operations are ($22\times$) less than SecSkyline’s 495000 in CORR, ($15\times$) in INDE and ($22\times$) in ANTI. When $n=9000$, ($9.6\times$) in CORR, ($7.6\times$) in INDE and ($9.4\times$) in ANTI, ($5\times$) and ($10.7\times$) in REAL, respectively.

Table 3. Size of diagram $(n_1, n_2)$ with $[\bar{n},\theta ]$ when $d=2$