Paper 2011/114
Fully Homomorphic Encryption, Approximate Lattice Problem and LWE
Gu Chunsheng
Abstract
In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1)We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2)We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3)The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Fully Homomorphic EncryptionApproximate Lattice ProblemApproximate Principal Ideal Lattice ProblemLWEApproximate GCDInteger Factoring
- Contact author(s)
- guchunsheng @ gmail com
- History
- 2011-07-04: last of 10 revisions
- 2011-03-07: received
- See all versions
- Short URL
- https://ia.cr/2011/114
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2011/114,
author = {Gu Chunsheng},
title = {Fully Homomorphic Encryption, Approximate Lattice Problem and {LWE}},
howpublished = {Cryptology {ePrint} Archive, Paper 2011/114},
year = {2011},
url = {https://eprint.iacr.org/2011/114}
}
