## 3 Preliminaries
### The Asymmetric Scalar-Product Preserving Encryption (ASPE)  
[PERSON] et al. [26] developed an asymmetric scalar-product preserving encryption (ASPE), which has been widely applied to the outsourced range matching in the ciphertext [30; 31]. Hence, this encryption algorithm can also applied to the outsourced spatial range query in the ciphertext. * Key generation (\(Gen(d)\)). Given a security parameter \(d\), two \(d\times d\) invertible matrices \(M_{1}\) and \(M_{2}\), and a \(d\)-dimensional binary vector \(S\) are chosen as the private key, denoted as \(sk=(S,M_{1},M_{2})\). Note that the binary vector \(S\) is a splitting indicator to split the plaintext vector into two random vectors, where \(S[i]\) is the \(i\)-th bit in \(S\). * Tuple encryption function \(E_{T}(\cdot)\). Consider a \(d\)-dimensional vector \(P\) in a database. Firstly, split \(P\) into two \(d\)-dimensional vectors \((P_{a},P_{b})\) based on the splitting indicator \(S\). Specifically, if \(S[i]=0\)\((i=1,2,\ldots,d)\), \(P_{a}[i]=P_{b}[i]=P[i]\); if \(S[i]=1\)\((i=1,2,\ldots,d)\), the value of \(P[i]\) will be randomly split into \(P_{a}[i]\) and \(P_{b}[i]\) such that \(P[i]=P_{a}[i]+P_{b}[i]\). Then, the encrypted value of \(P\) can be calculated as \[E_{T}(P,sk)=(P_{a}M_{1},P_{b}M_{2}).\] (1)
* Query encryption function \(E_{Q}(\cdot)\). Consider a \(d\)-dimensional vector \(Q\), split it into two \(d\)-dimensional vectors \((Q_{a},Q_{b})\): if \(S[i]=0\)\((i=1,2,\ldots,d)\), the value of \(Q[i]\) can be randomly split into \(Q_{a}[i]\) and \(Q_{b}[i]\) with \(Q[i]=Q_{a}[i]+Q_{b}[i]\); if \(S[i]=1\)\((i=1,2,\ldots,d)\), \(Q_{a}[i]=Q_{b}[i]=Q[i]\). The encrypted value of \(Q\) can be generated as \[E_{Q}(Q,sk)=(M_{1}^{-1}Q_{a}^{\mathsf{T}},M_{2}^{-1}Q_{b}^{\mathsf{T}}),\] (2) where \(Q_{a}^{\mathsf{T}}\) and \(Q_{b}^{\mathsf{T}}\) denote the transpose of \(Q_{a}\) and \(Q_{b}\), respectively. * Outsourced scalar-product calculation. With two ciphertexts \(E_{T}(P,sk)\) and \(E_{Q}(Q,sk)\), the outsourced scalar-product can be calculated as \[E_{T}(P,sk)\cdot E_{Q}(Q,sk) = (P_{a}M_{1},P_{b}M_{2})\cdot(M_{1}^{-1}Q_{a}^{\mathsf{T}},M_{2}^{ -1}Q_{b}^{\mathsf{T}})\] \[= P_{a}M_{1}\cdot M_{1}^{-1}Q_{a}^{\mathsf{T}}+P_{b}M_{2}\cdot M_{ 2}^{-1}Q_{b}^{\mathsf{T}}\] \[= P_{a}\cdot Q_{a}^{\mathsf{T}}+P_{b}\cdot Q_{b}^{\mathsf{T}}\] \[= P\cdot Q.\] The correctness of the scalar-product calculation can be referred to [26]. * Decryption Function \(D(\cdot)\). Consider an encrypted value \((P_{a}M_{1},P_{b}M_{2})\). Firstly, compute the inverse matrices \(M_{1}^{-1}\) and \(M_{2}^{-1}\), and then extract two vectors \(P_{a}\) and \(P_{b}\), i.e., \(P_{a}=P_{a}M_{1}\cdot M_{1}^{-1}\), \(P_{b}=P_{b}M_{2}\cdot M_{2}^{-1}\). Finally, recover the original \(d\)-dimensional vector \(P\) with the splitting indicator \(S\): \[P[i]=\left\{ \begin{array}{ccc}P_{a}[i]=P_{b}[i],&if&S[i]=0,\\ P_{a}[i]+P_{b}[i],&if&S[i]=1.\end{array} \right.\] _The Properties of ASPE Algorithm_: For any encrypted tuple \(E_{T}(P_{i},sk)\) and an encrypted query \(E_{Q}(Q,sk)\), the ASPE algorithm satisfies the following two properties:  
* For any \(P_{i}\) encrypted by \(E_{T}(\cdot)\) and any query \(Q\) encrypted by \(E_{Q}(\cdot)\): \[P_{i}\cdot Q=E_{T}(P_{i},sk)\cdot E_{Q}(Q,sk).\] (3)
* For any \(P_{i}\) and \(P_{j}\) encrypted by \(E_{T}(\cdot)\): \[P_{i}\cdot P_{j}\
eq E_{T}(P_{i},sk)\cdot E_{T}(P_{j},sk).\] (4)Note that the actual dimension \(d\) may be too small to resist the brute-force attack. Therefore, it is better to improve the system security by making \(d\) larger, which can be achieved by adding _artificial_ dimensions to the data vector. In particular, extend a \(d\)-dimensional vector to a \(d^{\prime}\)-dimensional (\(d\leq d^{\prime}\)) by padding artificial data such that the scalar-product over the added data is \(0\). In addition, \(d^{\prime}\geq 80\) is large enough to make the system security. The details can be referred to [26].