Verifiable Computation over Large Database with Incremental Updates
Authors:
- 25 December 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 65 (10) , 3184-3195
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.Keywords
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
This publication has 43 references indexed in Scilit:
- Verifiable Computation over Large Database with Incremental Updates2014
- Comparing the Pairing Efficiency over Composite-Order and Prime-Order Elliptic Curves2013
- New Algorithms for Secure Outsourcing of Modular Exponentiations2012
- Fair Payments for Outsourced Computations2010
- Fully homomorphic encryption using ideal lattices2009
- Delegating computation2008
- Conditional Payments for Computing Markets2008
- Wallet Databases with Observers2001
- Uncheatable Distributed Computations2001
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989