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

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

Zhigang Chen, Xinxia Song

Published Jan 1, 2015• 1 citation
OpenAlex

Abstract

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.

Related papers

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

A fully homomorphic encryption scheme with better key size

Zhigang Chen, Jian Wang, Zengnian Zhang +1 more

Fully homomorphic encryption is faced with two problems now. One is candidate fully homomorphic encryption schemes are few. Another is that the efficiency of fully homomorphic encryption is a big question. In this paper, we propose a fully homomorphic encryption scheme based on LWE, which has better key size. Our main contributions are: (1) According to the binary-LWE recently, we choose secret key from binary set and modify the basic encryption scheme proposed in Linder and Peikert in 2010. We propose a fully homomorphic encryption scheme based on the new basic encryption scheme. We analyze the correctness and give the proof of the security of our scheme. The public key, evaluation keys and tensored ciphertext have better size in our scheme. (2) Estimating parameters for fully homomorphic encryption scheme is an important work. We estimate the concert parameters for our scheme. We compare these parameters between our scheme and Bra12 scheme. Our scheme have public key and private key that smaller by a factor of about logq than in Bra12 scheme. Tensored ciphertext in our scheme is smaller by a factor of about log2q than in Bra12 scheme. Key switching matrix in our scheme is smaller by a factor of about log3q than in Bra12 scheme.

China Communications•Sep 1, 2014•25 citations

Efficient fully homomorphic encryption with circularly secure key switching process

Tanping Zhou, Xiaoyuan Yang, Wei Zhang +1 more

Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations are inefficient. In this paper, the 'special b' variant of the learning with errors problem (bLWE) is presented, and helps us construct the first circularly secure key switching process which can replace the key switching process and similar re-linearisation process used by the existing FHE schemes. Then, we present an efficient FHE. Compared with Brakerski's scheme, our scheme reduces L secret keys to one and is more efficient. Finally, we prove the chosen-plaintext attack (CPA) security of the fully homomorphic scheme and the circular security of key switching process in standard model under the learning with errors problem (LWE) assumption.

International Journal of High Performance Computing and Networking•Jan 1, 2016•8 citations

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

Efficient Dynamic Multi-key FHE Scheme from LWE for Untrusted Cloud Environments

Shuchang Zeng, Ching-Fang Hsu, Jianqun Cui +2 more

Fully Homomorphic Encryption (FHE) provides a good solution to directly operate on the ciphertext, and the decryption result is equivalent to the corresponding operation on the plaintext. As a technique suitable for distributed environments, multi-key Fully Homomorphic Encryption (MKFHE) scheme is the most common variant of the FHE scheme since it allows encrypted data to be computed under different keys. Unfortunately, the existing dynamic MKFHE schemes based on learning with errors (LWE) still suffer from the inefficiency of long public keys, which typically grow cube in size along the lattice dimension. Moreover, there current constructions fail to provide reliable and fast algorithms to simultaneously expand ciphertexts with multiple additional keys. In order to solve the above problems, a new faster dynamic MKFHE scheme with shorter public key in asymmetric key setting from LWE is proposed in this paper, in which the size of the public key is further reduced from $\tilde O\left( {{n^3}{{(K + L)}^2}} \right)$ to $\tilde O\left( {{n^2}{{(K + L)}^2}} \right)$. In addition, our scheme cleverly adopts the dual-user cooperation method in distributed system to realize the ciphertext expansion locally, thereby reducing the computing overhead of the cloud server. More interestingly, we design a flexible parallel ciphertext expansion algorithm for the first time based on the basic algorithm. This algorithm realizes the ciphertext expansion when multiple keys are added at the same time, thus significantly improving the computational efficiency of ciphertext expansion in the dynamic MKFHE scheme. Finally, the CPA-secure of our scheme based on standard LWE assumptions is proven.

IEEE International Conference on Parallel and Distributed Systems (ICPADS)•Dec 17, 2023•1 citation

Dual LWE-Based Fully Homomorphic Encryption with Errorless Key Switching

Zengpeng Li, Chunguang Ma, Gang Du +1 more

Cloud computing raises new challenges for how to protect user privacy. Fully homomorphic encryption is one way to solve the problem. In this paper, we show a useful property of Dual-LWE assumption to construct Key-Switching procedure compared with LWE assumption without extra error term. Hence, we propose to construct "Errorless Key Switching" fully homomorphic encryption (FHE) scheme based on dual learning with errors (Dual-LWE) assumption. Specifically, we compile the Dual-LWE problem proposed by Gentry et.al. at STOC2008 and First-is-errorless LWE (Ferr.LWE) problem proposed by Brakerski et al. at STOC2013 into Dual-First-is-errorless LWE (Dual-Ferr.LWE) problem. Then, utilizing Dual-Ferr.LWE assumption to construct a various GPV(vGPV) scheme, and we use vGPV scheme as the fundamental building block to construct FHE with errorless key switching scheme. Lastly, under the assumption of decisional learning with errors(DLWE), we prove that our scheme is CPA secure.

IEEE International Conference on Parallel and Distributed Systems (ICPADS)•Dec 1, 2016•4 citations
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.
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.
Fully homomorphic encryption is faced with two problems now. One is candidate fully homomorphic encryption schemes are few. Another is that the efficiency of fully homomorphic encryption is a big question. In this paper, we propose a fully homomorphic encryption scheme based on LWE, which has better key size. Our main contributions are: (1) According to the binary-LWE recently, we choose secret key from binary set and modify the basic encryption scheme proposed in Linder and Peikert in 2010. We propose a fully homomorphic encryption scheme based on the new basic encryption scheme. We analyze the correctness and give the proof of the security of our scheme. The public key, evaluation keys and tensored ciphertext have better size in our scheme. (2) Estimating parameters for fully homomorphic encryption scheme is an important work. We estimate the concert parameters for our scheme. We compare these parameters between our scheme and Bra12 scheme. Our scheme have public key and private key that smaller by a factor of about logq than in Bra12 scheme. Tensored ciphertext in our scheme is smaller by a factor of about log2q than in Bra12 scheme. Key switching matrix in our scheme is smaller by a factor of about log3q than in Bra12 scheme.
Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations are inefficient. In this paper, the 'special b' variant of the learning with errors problem (bLWE) is presented, and helps us construct the first circularly secure key switching process which can replace the key switching process and similar re-linearisation process used by the existing FHE schemes. Then, we present an efficient FHE. Compared with Brakerski's scheme, our scheme reduces L secret keys to one and is more efficient. Finally, we prove the chosen-plaintext attack (CPA) security of the fully homomorphic scheme and the circular security of key switching process in standard model under the learning with errors problem (LWE) assumption.
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).
Fully Homomorphic Encryption (FHE) provides a good solution to directly operate on the ciphertext, and the decryption result is equivalent to the corresponding operation on the plaintext. As a technique suitable for distributed environments, multi-key Fully Homomorphic Encryption (MKFHE) scheme is the most common variant of the FHE scheme since it allows encrypted data to be computed under different keys. Unfortunately, the existing dynamic MKFHE schemes based on learning with errors (LWE) still suffer from the inefficiency of long public keys, which typically grow cube in size along the lattice dimension. Moreover, there current constructions fail to provide reliable and fast algorithms to simultaneously expand ciphertexts with multiple additional keys. In order to solve the above problems, a new faster dynamic MKFHE scheme with shorter public key in asymmetric key setting from LWE is proposed in this paper, in which the size of the public key is further reduced from O~(n3(K+L)2)\tilde O\left( {{n^3}{{(K + L)}^2}} \right)O~(n3(K+L)2) to O~(n2(K+L)2)\tilde O\left( {{n^2}{{(K + L)}^2}} \right)O~(n2(K+L)2). In addition, our scheme cleverly adopts the dual-user cooperation method in distributed system to realize the ciphertext expansion locally, thereby reducing the computing overhead of the cloud server. More interestingly, we design a flexible parallel ciphertext expansion algorithm for the first time based on the basic algorithm. This algorithm realizes the ciphertext expansion when multiple keys are added at the same time, thus significantly improving the computational efficiency of ciphertext expansion in the dynamic MKFHE scheme. Finally, the CPA-secure of our scheme based on standard LWE assumptions is proven.
Cloud computing raises new challenges for how to protect user privacy. Fully homomorphic encryption is one way to solve the problem. In this paper, we show a useful property of Dual-LWE assumption to construct Key-Switching procedure compared with LWE assumption without extra error term. Hence, we propose to construct "Errorless Key Switching" fully homomorphic encryption (FHE) scheme based on dual learning with errors (Dual-LWE) assumption. Specifically, we compile the Dual-LWE problem proposed by Gentry et.al. at STOC2008 and First-is-errorless LWE (Ferr.LWE) problem proposed by Brakerski et al. at STOC2013 into Dual-First-is-errorless LWE (Dual-Ferr.LWE) problem. Then, utilizing Dual-Ferr.LWE assumption to construct a various GPV(vGPV) scheme, and we use vGPV scheme as the fundamental building block to construct FHE with errorless key switching scheme. Lastly, under the assumption of decisional learning with errors(DLWE), we prove that our scheme is CPA secure.