Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Ambient Intelligence and Humanized Computing

How to build a faster private information retrieval protocol?

Wei Zhang, Shuguang Liu, Weidong Zhong, Xiaoyuan Yang

Published Jun 4, 2014• 3 citations
Publisher

Abstract

A CPA secure multi-bit somewhat homomorphic encryption scheme based on Learning With Errors over Rings assumption is presented. We use canonical embedding to transform ring elements into vectors over Z q , and thus decrease encryption and decryption cost. Comparing with GHV scheme appeared in 2010, to encrypt n bits, this scheme can reduce encryption cost from O(n 3/2) into O(nlog n). Finally, an efficient private information retrieval protocol that employs this scheme is presented.

DOI
10.1007/s12652-014-0239-6

Related papers

RLWE-Based Homomorphic Encryption and Private Information Retrieval

Wei Zhang, Shuguang Liu, Xiaoyuan Yang

A multi-bit somewhat homomorphic encryption scheme based on Learning With Errors over Rings (RLWE) assumption is provided, which use canonical embedding to transform elements over a ring into vectors, thus the operation of polynomial multiplication can be performed within O(nlog n) scalar operations, and cipher text size is reduced as well. CPA security of this scheme can be reduced into RLWE assumption. Moreover, an efficient private information retrieval protocol that employs this scheme is presented.

International Conference on Intelligent Networking and Collaborative Systems (INCoS)•Sep 1, 2013•7 citations

Efficient Fully homomorphic encryption scheme using Ring-LWE

Dan Xin, Jingzhou Ji, Jing Feng +2 more

Abstract Data can be stored and processed in an encrypted format using fully homomorphic encryption, which makes cloud computing provider can process data well without even knowing data information. However, most existing homomorphic encryption schemes based on ring learning with errors, focus on the special classes of rings, such as power-of-two cyclotomic rings, which significantly limits its application efficiency in cloud computing. Therefore, in this letter, to solve this problem above, an efficient fully homomorphic encryption scheme is proposed based on ring learning with errors in arbitrary cyclotomic rings. Particularly, a “somewhat homomorphic encryption” scheme is firstly proposed based on ring learning with errors. A novel fully homomorphic encryption scheme is further presented using key-switching. With theoretical and experimental verification, the proposed scheme has advantage of high efficiency of encryption and decryption. The security of our scheme strictly reduces to hardness of decision ring learning with errors problem in the random oracle model.

Journal of Physics Conference Series•Jan 1, 2021•4 citations

A Multi-Bit Fully Homomorphic Encryption with Shorter Public Key from LWE

Zhigang Chen, Xinxia Song

The efficiency of fully homomorphic encryption is a big question at present. To improve efficiency of fully homomorphic encryption, we use the technique of packed ciphertext to construct a multi-bit fully homomorphic encryption based on Learning with Errors problem. Our scheme has a short public key. Since our fully homomorphic encryption scheme builds on the basic encryption scheme that choose Learning with Errors samples from Gaussian distribution and add Gaussian error to it, which result in that the number of Learning with Errors samples decrease from 2nlogq to n+1. We prove that our fully homomorphic encryption scheme is feasible and its security relies on the hardness of Learning with Errors problem. In addition we adapt the optimization for the process of key switching from GHS13 and formal this new process of key switching for multi-bit fully homomorphic encryption. At last, we analyze the concert parameters and compare these parameters between our scheme and GHS13 scheme. The data show that our scheme has public key smaller by a factor of about logq than it in GHS13 scheme.

•Jan 1, 2015•1 citation

Towards an efficient LWE‐based fully homomorphic encryption scheme

Uddipana Dowerah, Srinivasan Krishnaswamy

Abstract The security of most early fully homomorphic encryption schemes was based on the hardness of the Learning with Errors (LWE) problem. These schemes were inefficient in terms of per gate computations and public‐key size. More efficient schemes were later developed based on the hardness of the Ring‐LWE (RLWE) problem. While the hardness of the LWE problem is based on the hardness of the approximate shortest vector problem (GapSVP γ ) over regular lattices, the hardness of the RLWE problem is based on the hardness of the approximate shortest vector problem over ideal lattices. As of now, it has not been proved that the (GapSVP γ ) problem over ideal lattices is as difficult as the corresponding problem over regular lattices. In this work, the authors propose a multi‐bit levelled fully homomorphic encryption scheme using multivariate polynomial evaluations whose security depends on the hardness of the LWE problem. In terms of per gate computation cost, this scheme is more efficient than existing LWE‐based schemes. Further, for an appropriate choice of parameters, the per computation cost for homomorphic multiplication can be made asymptotically comparable to RLWE‐based schemes in a parallel computing environment. For homomorphic multiplication, the scheme uses a polynomial‐based technique that does not require relinearization (and key switching).

IET Information Security•Apr 28, 2022•16 citations

A Multi-Bit Fully Homomorphic Encryption With Shorter Public Key From LWE

Xinxia Song, Zhigang Chen, Liang Chen

There has been a great deal of work on improving the efficiency of fully homomorphic encryption (FHE) scheme. Our approach, in this regard, is to use the idea of packed ciphertexts to construct a multi-bit FHE with a short public key on the basis of the learning with errors (LWE) problem. More specifically, our FHE scheme builds on a basic encryption scheme that chooses LWE samples from the Gaussian distribution and adds Gaussian error to it. This results in decreasing the number of LWE samples from 2nlogq to n + 1. We prove that our FHE scheme is pragmatically feasible and its security relies on the hardness of the LWE problem. In addition, we form a new process of key switching for multi-bit FHE based on the ideas adopted by Brakerski et al. for optimizing the process of key switching. Finally, we analyze and compare the concrete parameters between our FHE scheme and BGH13 scheme. The result shows that compared with the BGH13 scheme, our scheme has a smaller public key by a factor about logq.

IEEE Access•Jan 1, 2019•11 citations

One Improved RLWE-based FHE and Fast Private Information Retrieval

Weitao Song, Bin Hu and Xiu-Feng Zhao

With the rapid development of cloud computing, it raises real questions on privacy protection, which greatly limits the use of cloud computing.However, fully homomorphic encryption (FHE) can make cloud computing consistent with privacy.In this paper, we propose a simpler FHE scheme based on ring LWE problem, with a smaller size of ciphertext and a lower noise-expansion factor for homomorphic multiplication.Then based on our optimized RLWE-based FHE scheme, we propose a fast single-database private information retrieval protocol, combining with batching and number theoretic transform technology.

KSII Transactions on Internet and Information Systems•Dec 31, 2019•1 citation
A CPA secure multi-bit somewhat homomorphic encryption scheme based on Learning With Errors over Rings assumption is presented. We use canonical embedding to transform ring elements into vectors over Z q , and thus decrease encryption and decryption cost. Comparing with GHV scheme appeared in 2010, to encrypt n bits, this scheme can reduce encryption cost from O(n 3/2) into O(nlog n). Finally, an efficient private information retrieval protocol that employs this scheme is presented.
A multi-bit somewhat homomorphic encryption scheme based on Learning With Errors over Rings (RLWE) assumption is provided, which use canonical embedding to transform elements over a ring into vectors, thus the operation of polynomial multiplication can be performed within O(nlog n) scalar operations, and cipher text size is reduced as well. CPA security of this scheme can be reduced into RLWE assumption. Moreover, an efficient private information retrieval protocol that employs this scheme is presented.
Abstract Data can be stored and processed in an encrypted format using fully homomorphic encryption, which makes cloud computing provider can process data well without even knowing data information. However, most existing homomorphic encryption schemes based on ring learning with errors, focus on the special classes of rings, such as power-of-two cyclotomic rings, which significantly limits its application efficiency in cloud computing. Therefore, in this letter, to solve this problem above, an efficient fully homomorphic encryption scheme is proposed based on ring learning with errors in arbitrary cyclotomic rings. Particularly, a “somewhat homomorphic encryption” scheme is firstly proposed based on ring learning with errors. A novel fully homomorphic encryption scheme is further presented using key-switching. With theoretical and experimental verification, the proposed scheme has advantage of high efficiency of encryption and decryption. The security of our scheme strictly reduces to hardness of decision ring learning with errors problem in the random oracle model.
The efficiency of fully homomorphic encryption is a big question at present. To improve efficiency of fully homomorphic encryption, we use the technique of packed ciphertext to construct a multi-bit fully homomorphic encryption based on Learning with Errors problem. Our scheme has a short public key. Since our fully homomorphic encryption scheme builds on the basic encryption scheme that choose Learning with Errors samples from Gaussian distribution and add Gaussian error to it, which result in that the number of Learning with Errors samples decrease from 2nlogq to n+1. We prove that our fully homomorphic encryption scheme is feasible and its security relies on the hardness of Learning with Errors problem. In addition we adapt the optimization for the process of key switching from GHS13 and formal this new process of key switching for multi-bit fully homomorphic encryption. At last, we analyze the concert parameters and compare these parameters between our scheme and GHS13 scheme. The data show that our scheme has public key smaller by a factor of about logq than it in GHS13 scheme.
Abstract The security of most early fully homomorphic encryption schemes was based on the hardness of the Learning with Errors (LWE) problem. These schemes were inefficient in terms of per gate computations and public‐key size. More efficient schemes were later developed based on the hardness of the Ring‐LWE (RLWE) problem. While the hardness of the LWE problem is based on the hardness of the approximate shortest vector problem (GapSVP γ ) over regular lattices, the hardness of the RLWE problem is based on the hardness of the approximate shortest vector problem over ideal lattices. As of now, it has not been proved that the (GapSVP γ ) problem over ideal lattices is as difficult as the corresponding problem over regular lattices. In this work, the authors propose a multi‐bit levelled fully homomorphic encryption scheme using multivariate polynomial evaluations whose security depends on the hardness of the LWE problem. In terms of per gate computation cost, this scheme is more efficient than existing LWE‐based schemes. Further, for an appropriate choice of parameters, the per computation cost for homomorphic multiplication can be made asymptotically comparable to RLWE‐based schemes in a parallel computing environment. For homomorphic multiplication, the scheme uses a polynomial‐based technique that does not require relinearization (and key switching).
There has been a great deal of work on improving the efficiency of fully homomorphic encryption (FHE) scheme. Our approach, in this regard, is to use the idea of packed ciphertexts to construct a multi-bit FHE with a short public key on the basis of the learning with errors (LWE) problem. More specifically, our FHE scheme builds on a basic encryption scheme that chooses LWE samples from the Gaussian distribution and adds Gaussian error to it. This results in decreasing the number of LWE samples from 2nlogq to n + 1. We prove that our FHE scheme is pragmatically feasible and its security relies on the hardness of the LWE problem. In addition, we form a new process of key switching for multi-bit FHE based on the ideas adopted by Brakerski et al. for optimizing the process of key switching. Finally, we analyze and compare the concrete parameters between our FHE scheme and BGH13 scheme. The result shows that compared with the BGH13 scheme, our scheme has a smaller public key by a factor about logq.
With the rapid development of cloud computing, it raises real questions on privacy protection, which greatly limits the use of cloud computing.However, fully homomorphic encryption (FHE) can make cloud computing consistent with privacy.In this paper, we propose a simpler FHE scheme based on ring LWE problem, with a smaller size of ciphertext and a lower noise-expansion factor for homomorphic multiplication.Then based on our optimized RLWE-based FHE scheme, we propose a fast single-database private information retrieval protocol, combining with batching and number theoretic transform technology.