Learning with error based searchable encryption scheme

Yang Yang, Maode Ma

Abstract. When data is outsourced to a remote storage server, search-able encryption plays an important role to protect data privacy while allowing users to retrieve data in the massive ciphertext. As far as we know, most of the existing searchable encryption schemes work based on the bilinear map. These schemes may not be secure in the quantum age. Both discrete logarithms and factorization can be solved by quantum computer in a polynomial time. There is very few searchable encryption scheme that can be proved secure in post quantum age. In this paper, in order to construct a post-quantum secure scheme for future cloud stor-age, we suggest a public key encryption with semantic keyword search using the lattice based mechanism. The suggested scheme is proved se-cure against indistinguishable chosen-keyword attacks (IND-CKA) based on learning with errors (LWE) problem. This scheme is believed to be secure in quantum-era due to the quantum intractability of the LWE problem.

Jingnan He, Bao Li, Xianhui Lu +3 more

Prabhanjan Ananth, Alexander Poremba, Vinod Vaikuntanathan

Lei Xu, Xingliang Yuan, Ron Steinfeld +2 more

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.

Er-Shuo Zhuang, Chun‐I Fan

To protect the privacy of cloud data, encryption before uploading provides a solution. However, searching for target data in ciphertext takes effort. Therefore, searchable encryption has become an important research topic. On the other hand, since the advancement of quantum computers will lead to the crisis of cracking traditional encryption algorithms, it is necessary to design encryption schemes that can resist quantum attacks. Therefore, we propose a multi-keyword searchable identity-based proxy re-encryption scheme from lattices. In addition to resisting quantum attacks, the proposed scheme uses several cryptographic techniques to improve encryption efficiency. First, identity-based encryption is used to reduce the computation and transmission costs caused by certificates. Second, the proposed scheme uses proxy re-encryption to achieve the purpose of outsourced computing, allowing the proxy server to reduce the computation and transmission costs of the users. Third, the proposed multi-keyword searchable encryption can provide AND and OR operators to increase the flexibility of searchability. Moreover, the access structure of the proposed scheme is not based on a linear secret sharing scheme (LSSS), avoiding the errors caused by an LSSS-based structure in decryption or search results. Finally, we also give formal security proof of the proposed scheme under the decisional learning with errors assumption.

Danilo Francati, Daniele Friolo, Giulio Malavolta +1 more