## 4 ROLQ-TEE Scheme
### Detailed Construction
Theorem 5.2: _The ROLQ-TEE scheme maintains revocable security if the discrete logarithm problem and the collision resistance of hash functions are hard._

Proof: The optimal location query process of the ROLQ-TEE scheme is carried out in the TEE (Intel SGX), and its correctness relies on the guarantee of hardware security. For a more detailed proof process, please refer to references [29; 33]. Therefore, our scheme only needs to ensure that the ciphertext data in other stages cannot be decrypted by the adversary or revoked by users. We will meet this design goal in Stage 1, Stage 2, and Stage 3. Stage 1: In the ciphertext upload stage, the following processes occur: (1) \(\mathcal{DO}\) generates the master secret key \(msk\) locally and transmits it to TEE through a secure channel generated by TEE remote attestation. The security of the transmission depends on the ECDH protocol [33]. Since \(\mathcal{DO}\) and TEE are trusted and the transmission process is secure, it is impossible for an adversary \(\mathcal{A}\) to obtain the master secret key through monitoring or tampering. (2) These keys used for data encrypted by the \(\mathcal{DU}_{\mu}\) are derived keys, which are derived by TEE through \(msk\) and securely distributed by TEE. The adversary \(\mathcal{A}\) cannot forge the \(sk_{\mu}\) and \(sk_{\mathcal{DO}}\) in probabilistic polynomial time without knowing \(msk\), because the adversary \(\mathcal{A}\) cannot solve the discrete logarithm problem and the collision resistance of the hash function. In summary, the ROLQ-TEE scheme is secure during the ciphertext upload phase. Stage 2: During the token upload phase, each \(\mathcal{DU}_{\mu}\) generates a query token \(\mathcal{Q}\) using a unique identity \(rid_{\mu}\) and the public parameters \(mpk\). If the adversary \(\mathcal{A}\) can decrypt the encrypted token in polynomial time, then the adversary \(\mathcal{A}\) must solve the discrete logarithm problem and the collision resistance of the hash function in polynomial time in order to forge the analysis key \(sk_{\mu}\). This contradicts the difficulty of solving discrete logarithms and the anti-collision property of the \(H_{1}\) and \(H_{2}\) hash functions. Therefore, it is computationally infeasible for the adversary \(\mathcal{A}\) to break the token with a non-negligible advantage. Stage 3: During the key refresh phase, the TEE recalculates the parameters \(sk_{\mu,t+1,0}\) and \(sk_{\mu,t+1,1}\) for each non-revoked request user, utilizing the updated timestamp \(T_{t+1}\) and updated random number \(r_{\mu,t+1}\) to generate the refreshed query key \(sk^{\prime}_{\mu}\). Thus, when \(\mathcal{DU}_{\mu}\) initiates a query again using the new query key \(sk^{\prime}_{\mu}\), the messages \(\mathcal{F}_{\mu}\) and \(U_{\mu}\) are randomized with \(r^{\prime}_{\mu}\) and \(r^{\prime}_{\mu,j}\), respectively, instead of with \(r_{\mu}\) and \(r_{\mu,j}\). Thus, the adversary \(\mathcal{A}\) cannot decrypt the encrypted tokens \(\mathcal{CF}^{\prime}_{\mu}\) and \(\mathcal{C}_{\mu,j}\). However, the adversary \(\mathcal{A}\) can try to recover the query key \(sk^{\prime}_{\mu}\). Since the query key \(sk^{\prime}_{\mu}\) is randomized by a random number \(r_{\mu,t+1}\), and the discrete logarithm problem (DLP) and the collision resistance of the hash function, it is computationally infeasible for the adversary \(\mathcal{A}\). Thus, the adversary \(\mathcal{A}\) can not break the query key \(sk^{\prime}_{\mu}\) of the \(\mathcal{DU}_{\mu}\) within probabilistic polynomial time. **Theorem 3**: _The ROLQ-TEE scheme maintains data anonymity if the pseudo-random function and the advanced encryption standard galois/counter mode (AES-GCM) algorithm are secure._

During the query phase, the \(\mathcal{DU}_{\mu}\) sends a query token \(\mathcal{Q}_{\mu}\) to the cloud server, which contains the encrypted set \(\mathcal{CF}_{\mu}\) of candidate facilities and the encrypted customer list \(\mathcal{CL}_{\mu}\).