IEICE TRANSACTIONS on Fundamentals
Packing Messages and Optimizing Bootstrapping in GSW-FHE
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.1 pp.73-82
- Publication Date
- 2016/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.73
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Ryo HIROMASA
Kyoto University
Masayuki ABE
NTT Corporation
Tatsuaki OKAMOTO
NTT Corporation
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ryo HIROMASA, Masayuki ABE, Tatsuaki OKAMOTO, "Packing Messages and Optimizing Bootstrapping in GSW-FHE" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 1, pp. 73-82, January 2016, doi: 10.1587/transfun.E99.A.73.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.73/_p
Copy
@ARTICLE{e99-a_1_73,
author={Ryo HIROMASA, Masayuki ABE, Tatsuaki OKAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Packing Messages and Optimizing Bootstrapping in GSW-FHE},
year={2016},
volume={E99-A},
number={1},
pages={73-82},
abstract={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.},
keywords={},
doi={10.1587/transfun.E99.A.73},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Packing Messages and Optimizing Bootstrapping in GSW-FHE
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 73
EP - 82
AU - Ryo HIROMASA
AU - Masayuki ABE
AU - Tatsuaki OKAMOTO
PY - 2016
DO - 10.1587/transfun.E99.A.73
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2016
AB - 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.
ER -
English
