For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Packing Messages and Optimizing Bootstrapping in GSW-FHE
Ryo HIROMASA Masayuki ABE Tatsuaki OKAMOTO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/01/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
lattice-based cryptography, fully homomorphic encryption, bootstrapping, SIMD operations,
Full Text: PDF(860.3KB)>>
We construct the first fully homomorphic encryption (FHE) scheme that encrypts matrices and supports homomorphic matrix addition and multiplication. This is a natural extension of packed FHE and thus supports more complicated homomorphic operations. We optimize the bootstrapping procedure of Alperin-Sheriff and Peikert (CRYPTO 2014) by applying our scheme. Our optimization decreases the lattice approximation factor from Õ(n3) to Õ(n2.5). By taking a lattice dimension as a larger polynomial in a security parameter, we can also obtain the same approximation factor as the best known one of standard lattice-based public-key encryption without successive dimension-modulus reduction, which was essential for achieving the best factor in prior works on bootstrapping of standard lattice-based FHE.