SecPQ: Secure Prediction Queries on Encrypted Outsourced Databases

Prediction queries have revolutionized data search by integrating machine learning models and traditional data processing operations for advanced analytics. However, existing prediction query frameworks for outsourced databases face a critical security vulnerability: data flows are processed in plaintext on semi-honest servers, making them susceptible to data breaches. The main challenge in achieving secure prediction queries is that machine learning inference and data processing operations are distinct functionalities, while most current cryptographic frameworks support only a single type of operation on specific encrypted data. To bridge this crucial gap, we propose <inline-formula><tex-math notation="LaTeX">$\mathsf {SecPQ}$</tex-math></inline-formula>, the first framework tailored for secure prediction queries. Our approach unifies decision tree pipelines and data processing operations, such as selection, projection, and equality-joining, through equality matching on encrypted outsourced data. This enables the design of secure prediction queries with decision tree pipelines operating on encrypted data. We provide formal security definitions and proofs for <inline-formula><tex-math notation="LaTeX">$\mathsf {SecPQ}$</tex-math></inline-formula>. To further optimize the efficiency of secure prediction queries, we leverage order-preserving encryption to construct <inline-formula><tex-math notation="LaTeX">$\mathsf {SecPQ}_{{{ope}}}$</tex-math></inline-formula>, which offers improved query efficiency at the expense of weaker security properties compared with <inline-formula><tex-math notation="LaTeX">$\mathsf {SecPQ}$</tex-math></inline-formula>. Extensive experimental evaluations on billions of records demonstrate the feasibility and effectiveness of both <inline-formula><tex-math notation="LaTeX">$\mathsf {SecPQ}$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\mathsf {SecPQ}_{{{ope}}}$</tex-math></inline-formula>.