We show that the bootstrapping scheme FHEW of Ducas and Micciancio (Eurocrypt 2015) can be expressed only in terms of this external product. As a result, we obtain a speed up from less than 1 second to less than 0.1 seconds. We also reduce the 1GB bootstrapping key size to 24MB, preserving the same security levels, and we improve the noise propagation overhead by replacing exact decomposition algorithms with approximate ones.
Moreover, our external product allows to explain the unique asymmetry in the noise propagation of GSW samples and makes it possible to evaluate deterministic automata homomorphically as in (ePrint 2014/283) in an efficient way with a noise overhead only linear in the length of the tested word.
Finally, we provide an alternative practical analysis of LWE based scheme, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key.Category / Keywords: foundations / Fully Homomorphic Encryption, Bootstrapping, Lattices, LWE, GSW Original Publication (in the same form): IACR-ASIACRYPT-2016 Date: received 6 Sep 2016, last revised 20 Feb 2017 Contact author: ilaria chillotti at uvsq fr Available format(s): PDF | BibTeX Citation Note: Minor corrections and updated citations Version: 20170220:145842 (All versions of this report) Short URL: ia.cr/2016/870 Discussion forum: Show discussion | Start new discussion