Percival: A Searchable Secret Split Datastore

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. To meet these needs, we developed Percival: a novel system that enables searching a secret-split datastore while maintaining information privacy. The system leverages salted hashing, performed within hardware security modules, to access prerecorded queries that have been secret split and stored in a distributed environment. When testing Percival on a corpus of approximately one million files, we found that the average search operation completed in less than one second.