Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

Paper 2014/706

The Feasibility of Outsourced Database Search in the Plain Model

Carmit Hazay and Hila Zarosim

Abstract

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. We study whether a trusted setup or a random oracle are necessary for protocols with minimal interaction that meet the optimal communication and computation bounds in the query phase. We answer this question positively and demonstrate a lower bound on the communication or the computational overhead in this phase.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. SCN 2016
Keywords
Outsourced ComputationDatabase Search FunctionalitiesLower BoundMinimal Interaction
Contact author(s)
carmit hazay @ biu ac il
History
2016-06-29: last of 5 revisions
2014-09-09: received
See all versions
Short URL
https://ia.cr/2014/706
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/706,
      author = {Carmit Hazay and Hila Zarosim},
      title = {The Feasibility of Outsourced Database Search in the Plain Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/706},
      year = {2014},
      url = {https://eprint.iacr.org/2014/706}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.