Verifiable Computation over Large Database with Incremental Updates

Authors:

Abstract
The notion of verifiable database (VDB) enables a resource-constrained client to securely outsource a very large database to an untrusted server so that it could later retrieve a database record and update a record by assigning a new value. Also, any attempt by the server to tamper with the data will be detected by the client. When the database undergoes frequent while small modifications, the client must re-compute and update the encrypted version (ciphertext) on the server at all times. For very large data, it is extremely expensive for the resources-constrained client to perform both operations from scratch. In this paper, we formalize the notion of verifiable database with incremental updates (Inc-VDB). Besides, we propose a general Inc-VDB framework by incorporating the primitive of vector commitment and the encrypt-then-incremental MAC mode of encryption. We also present a concrete Inc-VDB scheme based on the computational Diffie-Hellman (CDH) assumption. Furthermore, we prove that our construction can achieve the desired security properties.
Funding Information
  • National Natural Science Foundation of China (61272455, 61572382)
  • Ministry of Education of China (20130203110004)
  • Program for New Century Excellent Talents in University (NCET-13-0946)
  • Fundamental Research Funds for the Central Universities (BDY151402)
  • National High Technology Research and Development Program (863 Program) of China (2015AA016007)
  • China 111 Project (B16037)
  • US National Science Foundation (CNS-1217889)
  • 19th European Symposium on Research in Computer Security