Restricted queries over an encrypted index with applications to regulatory compliance

Compliance storage is an increasingly important area for businesses faced with a myriad of new document retention regulations. Today, businesses have turned to Write-One Read Many (WORM) storage technology to achieve compliance. But WORM answers only a part of the compliance puzzle; in addition to guaranteed document retention, businesses also need secure indexing, to ensure auditors can find required documents in a large database, secure deletion to expire documents (and their index entries) from storage once they are past their expiry period, and support for litigation holds, which require that certain documents are retained pending the resolution of active litigation. We build upon previous work in compliance storage and attribute-based encryption to design a system that satisfies all three of these requirements. In particular, we design a new encrypted index, which allows the owner of a database of documents to grant access to only those documents that match a particular query. This enables litigation holds for expired documents, and at the same time restricts auditor access for unexpired documents, greatly limiting the potential for auditor abuse as compared to previous work. We show by way of formal security proofs that our construction is secure and that it prevents reconstruction attacks wherein the index is used to recover the contents of the document. Our experiments show that our scheme can be practical for large databases and moderate sizes of queries.