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

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.