4th International ICST Conference on Security and Privacy in Communication Networks

Research Article

Scalable and Efficient Provable Data Possession

  • @INPROCEEDINGS{10.1145/1460877.1460889,
        author={Giuseppe Ateniese and Roberto Di Pietro and Luigi V. Mancini and Gene Tsudik},
        title={Scalable and Efficient Provable Data Possession},
        proceedings={4th International ICST Conference on Security and Privacy in Communication Networks},
        keywords={Provable data possession probabilistic algorithm archival storage storage update storage security.},
  • Giuseppe Ateniese
    Roberto Di Pietro
    Luigi V. Mancini
    Gene Tsudik
    Year: 2008
    Scalable and Efficient Provable Data Possession
    DOI: 10.1145/1460877.1460889
Giuseppe Ateniese1,*, Roberto Di Pietro2,*, Luigi V. Mancini3,*, Gene Tsudik4,*
  • 1: The Johns Hopkins University Department of Computer Science
  • 2: UNESCO Chair in Data Privacy Universitat Rovira i Virgili
  • 3: Universita di Roma ”La Sapienza” Dipartimento di Informatica
  • 4: University of California Irvine Department of Computer Science
*Contact email: ateniese@cs.jhu.edu, roberto.dipietro@urv.cat, mancini@di.uniroma1.it, gts@ics.uci.edu


Storage outsourcing is a rising trend which prompts a number of interesting security issues, many of which have been extensively investigated in the past. However, Provable Data Possession (PDP) is a topic that has only recently appeared in the research literature. The main issue is how to frequently, efficiently and securely verify that a storage server is faithfully storing its client’s (potentially very large) outsourced data. The storage server is assumed to be untrusted in terms of both security and reliability. (In other words, it might maliciously or accidentally erase hosted data; it might also relegate it to slow or off-line storage.) The problem is exacerbated by the client being a small computing device with limited resources. Prior work has addressed this problem using either public key cryptography or requiring the client to outsource its data in encrypted form. In this paper, we construct a highly efficient and provably secure PDP technique based entirely on symmetric key cryptography, while not requiring any bulk encryption. Also, in contrast with its predecessors, our PDP technique allows outsourcing of dynamic data, i.e, it efficiently supports operations, such as block modification, deletion and append.