2019 · 36 citations · 24 references
ComputingComputer ScienceComputer SystemsAlgorithmsCryptographyQuantum ComputingCryptographic AlgorithmsCryptographic ComplexityData EncryptionLattice-based CryptographyPublic-key CryptographyComputational SecurityHardnessKey GenerationKey ManagementLearning With ErrorsLearning With Errors ProblemPublic-key EncryptionSearchable Encryption
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.
24
Algorithms for quantum computation: discrete logarithms and factoring
Peter W. Shor · 2002 · 8.5K citations
Computing, Computer Science, Physics +12
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · Journal of the ACM · 2009 · 2.2K citations
On Ideal Lattices and Learning with Errors over Rings
Vadim Lyubashevsky, Chris Peikert, Oded Regev · Journal of the ACM · 2013 · 823 citations
On the concrete hardness of Learning with Errors
M. Albrecht, Rachel Player, Sam Scott · Journal of Mathematical Cryptology · 2015 · 789 citations · Full text