Efficient, Dynamic Method to Prove Data Integrity in Remote Servers/Clouds (Case 1927)

Principal Investigator:  


Roberto Tamassia, PhD, Professor

Department of Computer Science

Brown University

Providence, RI


Brief Description:


Increasingly, companies and individuals require and/or prefer online data storage-outsourcing services, outsourced database services, peer-to-peer (P2P) storage, and network file systems. Data/files are stored at third party, untrusted remote servers for subsequent access, downloading and uploading from often multiple locations by several users.  In these common scenarios, it is important to verify if one’s data has been tampered with or deleted.  To validate data, often a user must download the data.  If the outsourced data is very large files or entire file systems, such downloading to determine data integrity may become prohibitive in terms of increased cost of bandwidth and time, especially if frequent data checks are necessary.  Therefore, in this case, authenticated data structures solutions cannot be directly applied. 


Currently, a conventional model, called provable data possession (PDP), allows a client to bypass the need to download actual data for validation.  In the PDP model, preprocessed data and subsequent meta-data are used for verification purposes.  A preprocessed data file is sent to the untrusted third party server/entity for storage, while a small amount of meta-data is kept with the client.  Later, the client can test random stored data subsets via various schemes to determine if data integrity has been compromised.  The PDP model and related schemes apply primarily to static (append-only), archival storage, i.e., outsourced files that never change such as libraries or scientific data sets.  However, if one needs to insert, delete or modify stored data files, a dynamic PDP or DPDP scheme is essential in practical cloud computing systems for file storage, database services, and P2P storage.  Indeed, as dynamic storage-outsourcing services and resource-sharing networks continue to expand in popularity, the problem of efficiently proving stored data integrity at untrusted servers needs to be addressed.


The invention is a formal framework for DPDP that extends the PDP model to support dynamic provable updates to/on stored data and is related to data integrity, access, security, and updates for data stored by an untrusted agent, e.g., an untrusted remote server.  Most simply, the physical embodiment is an apparatus (memory and processor), with method and a computer program – instructions.  Novel advantages of this new, practical DPDP system/scheme include: 1) first efficient, fully dynamic PDP construction/solution for outsourced storage that provides file system and versioning semantics along with proof-of-possession; 2) added flexibility for multi-user environments and verification at different levels, e.g., every user can verify his/her own home directory without having to download the whole dataset; 3) unlimited updates for more natural use in distributed applications; 4) improved detection probability; and 5) can be extended to authenticated storage systems consisting of multiple files within a directory hierarch.


The markets are commercial computer software for data storage and access, and scientific R&D tools.  Applications are with outsourced file systems, databases, remote servers, cloud computing environments, and version control systems, e.g., CVS, with variable block size support, as well as in computer science R&D concerned with data storage, access, and security.




US patent 8,978,155 is issued (03/10/2015).

Canada patent 2,731,954 is issued.

Patent Information:
Research Tools
For Information, Contact:
Margaret Shabashevich,
Manager of Operations
Technology Ventures Office
Brown University
401-863-7499 TVO_Patents@brown.edu
Roberto Tamassia
Alptekin Kupcu
Charalampos Papamanthou
Chris Erway
© 2017. All Rights Reserved. Powered by Inteum