Securing a B+tree for Use with Secret-Shared Databases

Information revelations from databases may result not only from intrusions by external attackers but also from malicious actions by employees and even database administrators. A promising new approach to solving this problem is the use of secret-shared databases. In this approach, information is divided into unreadable snippets, and the snippets are stored in separate subdatabases, thereby making it difficult for external and internal attackers to steal the original information. A secret-shared database is secure unless

k

or more database administrators collude, where

k

is a predefined threshold. Any query that is executable for a conventional database is executable for the corresponding secret-shared database. However, retrieval (i.e., selection) of a record from a secret-shared database has a time complexity of O(

m

), where

m

is the number of records stored in the database. We used a B+tree, which is a standard data structure for efficiently retrieving data from conventional databases, to develop a secret-shared B+tree that enables data retrieval from secret-shared databases with O(log

m

) time complexity while maintaining the security provided by secret sharing.