(2020) LEAF: A Faster Secure Search Algorithm via Localization, Extraction, and Reconstruction.
|
Text
CCS20-LEAF.pdf Download (745kB) | Preview |
Abstract
Secure search looks for and retrieves records from a (possibly cloudhosted) encrypted database while ensuring the confidentiality of the queries. Researchers are paying increasing attention to secure search in recent years due to the growing concerns about database privacy. However, the low efficiency of (especially multiplicative) homomorphic operations in secure search has hindered its deployment in practice. To address this issue, Akavia et al. [CCS 2018, PETS 2019] proposed new protocols that bring down the number of multiplications in the search algorithm from ????(???? 2 ) to ????(???? log2 ????), and then to ????(???? log????), where ???? is the size of the database. In this paper, we present the first secure search protocol – LEAF and its variant LEAF+– which only requires ????(????) multiplications. Specifically, at the core of LEAF are three novel methods we propose, referred to as Localization, Extraction, and Reconstruction. In addition, LEAF enjoys low communication complexity and only requires the client to perform decryption, which adds its advantage in deployment on weak-power devices such as mobile phones.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Yang Zhang (YZ) |
| Conference: | CCS ACM Conference on Computer and Communications Security |
| Depositing User: | Yang Zhang |
| Date Deposited: | 08 Jun 2020 15:41 |
| Last Modified: | 11 May 2021 10:31 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3105 |
Actions
Actions (login required)
 |
View Item |