International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 09 September 2014

Carmit Hazay, Hila Zarosim
ePrint Report ePrint Report
The problem of securely outsourcing computation to an untrusted server gained momentum with the recent penetration of cloud computing services. The ultimate goal in this setting is to design efficient protocols that minimize the computational overhead of the clients and instead rely on the extended resources of the server. In this paper, we focus on the outsourced database search problem which is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases, that may contain confidential data. This functionality is described in two phases: (1) setup phase and (2) query phase. The main goal is to minimize the parties workload in the query phase so that it is proportional to the query size and its corresponding response.

Our starting point is the semi-honest protocol from FaustHV13 (ICALP 2013) that offers a simulation based secure protocol for outsourced pattern matching in the random oracle setting with optimal workload. In this work we study whether the random oracle is necessary for protocols with minimal interaction that meet the optimal communication/computation bounds in the query phase. We answer this question negatively and demonstrate a lower bound on the communication or the computational overhead in this phase. We further abstract the security properties of the underlying cryptographic primitive that enables to obtain private outsourced database search with minimal interaction. For a large class of search functionalities the communication complexity of our protocol meets the above lower bound.

Expand

Additional news items may be found on the IACR news page.