Visible to the public Multi-Writer Searchable Encryption: An LWE-Based Realization and Implementation

TitleMulti-Writer Searchable Encryption: An LWE-Based Realization and Implementation
Publication TypeConference Paper
Year of Publication2019
AuthorsXu, Lei, Yuan, Xingliang, Steinfeld, Ron, Wang, Cong, Xu, Chungen
Conference NameProceedings of the 2019 ACM Asia Conference on Computer and Communications Security
Date Publishedjul
PublisherAssociation for Computing Machinery
Conference LocationAuckland, New Zealand
ISBN Number978-1-4503-6752-3
Keywordscloud computing security, compositionality, encryption audits, Metrics, multi-writer searchable encryption, practical post-quantum security, pubcrawl, resilience, Resiliency
AbstractMulti-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.
Citation Keyxu_multi-writer_2019