Abstract
A verifiable outsourced database is a crucial technology for ensuring the integrity of query results in a cloud-based outsourced database. However, existing schemes struggle to balance efficient query execution with strong data security and query privacy, limiting practical deployment. To address this challenge, we propose ChamVerDB, a Chameleon Hash-based secure and efficient verifiable outsourced database. ChamVerDB restructures the database into a matrix and encrypts each record into three ciphertext segments using a modified BG encryption. For each row, it generates row parity, computes a corresponding Chameleon Hash Value and proof, while also generating individual parities for each record. The ciphertexts and parities are packaged into an encrypted database and outsourced to the server. During querying, the user utilizes a one-hot query vector to retrieve the target ciphertext row and a column vector to extract the desired ciphertext locally. Subsequently, the user and server collaboratively perform proxy re-encryption on one ciphertext segment and recover the plaintext using the remaining segments. The user then verifies the result using row parity, individual parity, proof, and the public hash value. Security analysis confirms that ChamVerDB ensures data security, query privacy, and result verifiability. Experimental evaluation on a $2^{20}$-record database demonstrates that ChamVerDB achieves $42\times$ and $32\times$ faster offline processing than two encrypted outsourcing baselines. In online phase, ChamVerDB completes a query in just 1.21s, outperforming three representative baselines by $511\times$ (618.5s), $1039\times$ (1258.14s), and $209810\times$ (253871.49s), illustrating its practical usability.
Funding Information
  • National Natural Science Foundation of China (U25A20429)
  • Natural Science Foundation of Sichuan Province (2025ZNSFSC0497)
  • Intelligent Systems Security Laboratory (Q25008*2)
  • Fundamental Research Funds for Chinese Central Universities (ZYGX2025TS010)
  • Natural Science Foundation of Shandong Province (ZR2022ZD03)
  • Colleges and Universities 20 Terms Foundation of Jinan City (202228093)