Packing Messages and Optimizing Bootstrapping in GSW-FHE

Ryo HIROMASA  Masayuki ABE  Tatsuaki OKAMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A    No.1    pp.73-82
Publication Date: 2016/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.73
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)>>
Buy this Article

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.