Percival: A Searchable Secret Split Datastore

Appeared in 31st International Conference on Massive Storage Systems and Technologies (MSST2015).

Abstract

Maintaining information privacy is challenging when sharing data across a distributed long-term datastore. In such applications, secret splitting the data across independent sites has been shown to be a superior alternative to fixed-key encryption; it improves reliability, reduces the risk of insider threat, and removes the issues surrounding key management. However, the inherent security of such a datastore normally precludes it from being directly searched without reassembling the data; this, however, is neither computationally feasible nor without risk since reassembly introduces a single point of compromise. As a result, the secret-split data must be pre-indexed in some way in order to facilitate searching. Previously, fixed-key encryption has also been used to securely pre-index the data, but in addition to key management issues, it is not well suited for long term applications.

To meet these needs, we have developed Percival: a novel system that enables searching a secret-split datastore while maintaining information privacy. We leverage salted hashing, performed within hardware security modules, to access pre-recorded queries that have been secret split and stored in a distributed environment; this keeps the bulk of the work on each client, and the data custodians blinded to both the contents of a query as well as its results. Furthermore, Percival does not rely on the datastore’s exact implementation. The result is a flexible design that can be applied to both new and existing secret-split datastores. When testing Percival on a corpus of approximately one million files, it was found that the average search operation completed in less than one second.

Publication date:
June 2015

Authors:
Joel Frank
Shayna Frank
Lincoln Thurlow
Thomas Kroeger
Ethan L. Miller
Darrell D. E. Long

Projects:
Archival Storage
Secure File and Storage Systems

Available media

Full paper text: PDF

Bibtex entry

@inproceedings{frank-msst15,
  author       = {Joel Frank and Shayna Frank and Lincoln Thurlow and Thomas Kroeger and Ethan L. Miller and Darrell D. E. Long},
  title        = {Percival: A Searchable Secret Split Datastore},
  booktitle    = {31st International Conference on Massive Storage Systems and Technologies (MSST2015)},
  month        = jun,
  year         = {2015},
}