Cryptology ePrint Archive: Report 2014/963

Malicious-Client Security in Blind Seer: A Scalable Private DBMS

Ben Fisch, Binh Vo, Fernando Krell, Abishek Kumarasubramanian, Vladimir Kolesnikov, Tal Malkin, Steven M. Bellovin

Abstract: The Blind Seer system (Oakland 2014) is an efficient and scalable DBMS that affords both client query privacy and server data protection. It also provides the ability to enforce authorization policies on the system, restricting client’s queries while maintaining the privacy of both query and policy. Blind Seer supports a rich query set, including arbitrary boolean formulas, and is provably secure with respect to a controlled amount of search pattern leakage. No other system to date achieves this tradeoff of performance, generality, and provable privacy. A major shortcoming of Blind Seer is its reliance on semi-honest security, particularly for access control and data protection. A malicious client could easily cheat the query authorization policy and obtain any database records satisfying any query of its choice, thus violating basic security features of any standard DBMS. In sum, Blind Seer offers additional privacy to a client, but sacrifices a basic security tenet of DBMS. In the present work, we completely resolve the issue of a malicious client. We show how to achieve robust access control and data protection in Blind Seer with virtually no added cost to performance or privacy. Our approach also involves a novel technique for a semi-private function secure function evaluation (SPF-SFE) that may have independent applications. We fully implement our solution and report on its performance.

Category / Keywords: applications / secure computation, implementation, private database, searchable encryption, data sharing

Date: received 24 Nov 2014

Contact author: benafisch at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20141125:204540 (All versions of this report)

Short URL: ia.cr/2014/963

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]