Achieving Efficient, Privacy-Preserving and Secure Verifiable Outsourced Database
Abstract
A verifiable database (VDB) is a key technology, enabling query users of an outsourced database to verify the correctness and integrity of query results. Although various VDB solutions exist, most fail to achieve data security and query privacy, and are rendered impractical due to low query efficiency. This paper introduces the Merkle-vector matrix commitment (MVMC), which integrates Merkle hash trees with vector commitments to significantly improve verification performance. Building on this, we propose PSVDB, an efficient, privacy-preserving and secure verifiable outsourced database. Specifically, the data owner encrypts the database, generates MVMC-based commitments and proofs, and outsources them to the server, while creating proxy re-encryption keys for query users. During the query, the user sends a homomorphically encrypted query index, and the server performs homomorphic operations on the encrypted database and row Merkle tree to produce encrypted query results and verification proofs. The user then uses the homomorphic key to recover the proof and the encrypted query results, verifies the correctness and integrity of the query results, and decrypts the data via proxy re-encryption. Security analysis demonstrates that PSVDB guarantees both data security and query privacy while enabling verifiable query results. Performance evaluation shows that PSVDB outperforms existing schemes, achieving an online query time of 10.20 s for a <inline-formula><tex-math notation="LaTeX">$2^{20}$</tex-math><alternatives><mml:math><mml:msup><mml:mn>2</mml:mn><mml:mn>20</mml:mn></mml:msup></mml:math><inline-graphic xlink:href="li-ieq1-3726971.gif"/></alternatives></inline-formula>-entry database and improving query efficiency by <inline-formula><tex-math notation="LaTeX">$61 \, \times$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>61</mml:mn><mml:mspace width="0.166667em"/><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq2-3726971.gif"/></alternatives></inline-formula> (618.50s), <inline-formula><tex-math notation="LaTeX">$124 \, \times$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>124</mml:mn><mml:mspace width="0.166667em"/><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq3-3726971.gif"/></alternatives></inline-formula> (1271.37s) and <inline-formula><tex-math notation="LaTeX">$24889 \, \times$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>24889</mml:mn><mml:mspace width="0.166667em"/><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq4-3726971.gif"/></alternatives></inline-formula> (253871.49 s), respectively.