FEASE: Fast and Expressive Asymmetric Searchable Encryption

Long Meng; Liqun Chen; Yangguang Tian; Mark Manulis; Suhui Liu

Paper 2024/054

FEASE: Fast and Expressive Asymmetric Searchable Encryption

Long Meng

, University of Surrey

Liqun Chen, University of Surrey

Yangguang Tian, University of Surrey

Mark Manulis, Universität der Bundeswehr München

Suhui Liu, Southeast University

Abstract

Asymmetric Searchable Encryption (ASE) is a promising cryptographic mechanism that enables a semi-trusted cloud server to perform keyword searches over encrypted data for users. To be useful, an ASE scheme must support expressive search queries, which are expressed as conjunction, disjunction, or any Boolean formulas. In this paper, we propose a fast and expressive ASE scheme that is adaptively secure, called FEASE. It requires only 3 pairing operations for searching any conjunctive set of keywords independent of the set size and has linear complexity for encryption and trapdoor algorithms in the number of keywords. FEASE is based on a new fast Anonymous Key-Policy Attribute-Based Encryption (A-KP-ABE) scheme as our first proposal, which is of independent interest. To address optional protection against keyword guessing attacks, we extend FEASE into the first expressive Public-Key Authenticated Encryption with Keyword Search (PAEKS) scheme. We provide implementations and evaluate the performance of all three schemes, while also comparing them with the state of the art. We observe that FEASE outperforms all existing expressive ASE constructions and that our A-KP-ABE scheme offers anonymity with efficiency comparable to the currently fastest yet non-anonymous KP-ABE schemes FAME (ACM CCS 2017) and FABEO (ACM CCS 2022).

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. USENIX Security Symposium 2024
Keywords: Asymmetric Searchable Encryption Attribute-Based Encryption
Contact author(s): long meng @ surrey ac uk
liqun chen @ surrey ac uk
yangguang tian @ surrey ac uk
mark @ manulis eu
230219091 @ seu edu cn
History: 2024-01-19: last of 3 revisions; 2024-01-14: received; See all versions
Short URL: https://ia.cr/2024/054
License: CC BY

BibTeX

@misc{cryptoeprint:2024/054,
      author = {Long Meng and Liqun Chen and Yangguang Tian and Mark Manulis and Suhui Liu},
      title = {FEASE: Fast and Expressive Asymmetric Searchable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2024/054},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/054}},
      url = {https://eprint.iacr.org/2024/054}
}