TY - GEN
T1 - LEAF
T2 - 27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020
AU - Wen, Rui
AU - Yu, Yu
AU - Xie, Xiang
AU - Zhang, Yang
N1 - Publisher Copyright:
© 2020 ACM.
PY - 2020/10/30
Y1 - 2020/10/30
N2 - Secure search looks for and retrieves records from a (possibly cloud-hosted) 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 O(n2) to O(n log2 n), and then to O(n log n), where n is the size of the database. In this paper, we present the first secure search protocol - LEAF and its variant LEAF+ - which only requires $O(n)$ 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.
AB - Secure search looks for and retrieves records from a (possibly cloud-hosted) 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 O(n2) to O(n log2 n), and then to O(n log n), where n is the size of the database. In this paper, we present the first secure search protocol - LEAF and its variant LEAF+ - which only requires $O(n)$ 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.
KW - (leveled) fully homomorphic encryption
KW - secure search
UR - https://www.scopus.com/pages/publications/85096170810
U2 - 10.1145/3372297.3417237
DO - 10.1145/3372297.3417237
M3 - 会议稿件
AN - SCOPUS:85096170810
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 1219
EP - 1232
BT - CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
Y2 - 9 November 2020 through 13 November 2020
ER -