Percival: Blinded Searching of a Secret Split Archive

Appeared in FAST14. Notification: Dec 8th 2013, Publication: Feb 17th 2014

Abstract

Secret splitting across independent sites has been proposed for data storage in archival systems as an approach that removes the issues surrounding key management resulting from fixed key encryption. However, the inherent security of such an archive precludes it from being directly searched; as a result, applications for secret split archives have been limited in the general environment. In this paper, we present a novel method to perform blinded search across a secret-split archive, which we call Percival. We leverage pre-indexing, keyed hashing and Bloom filters to enable blinded searching, blinding the archive from knowing what terms are being queried. The addition of chaff during ingestion and search operations not only keeps an attacker blind to the data in the archive, but also precludes correlating search results that could potentially reveal which shares are needed for reconstruction. While chaff increases the number of false positives at the archive site, the client can quickly filter most of them. This makes reconstruction of results by the client relatively efficient, keeping the bulk of the computational burden on the repositories.

Publication date:
November 2013

Authors:
Joel Frank
Ian Adams
Thomas Kroeger
Ethan L. Miller

Projects:
Archival Storage
Secure File and Storage Systems

Available media

Full paper text: PDF

Bibtex entry

@inproceedings{frank-fast14,
  author       = {Joel Frank and Ian Adams and Thomas Kroeger and Ethan L. Miller},
  title        = {Percival: Blinded Searching of a Secret Split Archive},
  booktitle    = {FAST14},
  month        = nov,
  year         = {2013},
}