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

Zhigang Chen, Xinxia Song

Published Jan 1, 2015• 1 citation

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 AccessJan 1, 20199 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 CommunicationsSep 1, 201426 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 NetworkingJan 1, 20169 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 SecurityApr 28, 202215 citations

Efficient fully homomorphic encryption with circularly secure key switching process

Xiaoyuan Yang, Wei Zhang, Liqiang Wu +1 more

International Journal of High Performance Computing and NetworkingJan 1, 20160 citations

Fully Homomorphic Encryption from Ring-LWE：Identity-Based，Arbitrary Cyclotomic，Tighter Parameters.

Chunxiang Gu, Dan Xin, Yonghui Zheng +1 more

1 (State Key Laboratory of Mathematical Engineering and Advanced Computing , Zhengzhou 450001) Abstract: Fully homomorphic is an encryption scheme that allows for data to be stored and processed in an encrypted format, which gives the cloud provider a solution to host and process data without even knowing what the message is. In previous identity-based homomorphic encryption scheme, computing efficiency is complicated and expensive. In this work, based on Regev’s work, we propose a sampling trapdoor one-way function in arbitrary cyclotomic rings [ ] ( ) / 1 n R X x = + Z . Then construct a leveled identity-based homomorphic encryption scheme from ring learning with errors, which has advantage in computational efficiency and key management, by using user’s identity as the unique public key. This scheme is proved IND-CPA secure in the random oracle model, relied to hardness of decision ring learning with errors problem.

Jan 1, 20150 citations