Multi-Writer Searchable Encryption: an LWE-based realization and implementation

Lei Xu, Xingliang Yuan, Ron Steinfeld, Cong Wang, Chungen Xu

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (Scopus)


Multi-Writer Searchable Encryption, also known as public-key encryption with keyword search(PEKS), serves a wide spectrum of data sharing applications. It allows users to search over encrypted data encrypted via different keys. However, most of the existing PEKS schemes are built on classic security assumptions, which are proven to be untenable to overcome the threats of quantum computers. To address the above problem, in this paper, we propose a lattice-based searchable encryption scheme from the learning with errors (LWE) hardness assumption. Specifically, we observe that the keys of each user in a basic scheme are composed of large-sized matrices and basis of the lattice. To reduce the complexity of key management, our scheme is designed to enable users to directly use their identity for data encryption. We present several optimization techniques for implementation to make our design nearly practical. For completeness, we conduct rigorous security, complexity, and parameter analysis on our scheme, and perform comprehensive evaluations at a commodity machine. With a scenario of 100 users, the cost of key generation for each user is 125s, and the cost of searching a document with 1000 keywords is 13.4ms.

Original languageEnglish
Title of host publicationProceedings of the 2019 ACM Asia Conference on Computer and Communications Security
EditorsDieter Gollmann, Engin Kirda , Zhenkai Liang
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages12
ISBN (Electronic)9781450367523
Publication statusPublished - 2019
EventACM Symposium on Information, Computer and Communications Security 2019 - Auckland, New Zealand
Duration: 7 Jul 201912 Jul 2019
Conference number: 14th


ConferenceACM Symposium on Information, Computer and Communications Security 2019
Abbreviated titleAsiaCCS 2019
CountryNew Zealand
Internet address


  • Cloud computing security
  • Multi-writer searchable encryption
  • Practical post-quantum security

Cite this