IACR News item: 12 June 2013
Jacob Alperin-Sheriff, Chris Peikert
ePrint Reporthomomorphic encryption (FHE) scheme from a ``somewhat homomorphic\'\'
one that is powerful enough to evaluate its own decryption function.
To date, it remains the only known way of obtaining unbounded FHE.
Unfortunately, bootstrapping is computationally very expensive,
despite the great deal of effort that has been spent on improving its
efficiency. The current state of the art, due to Gentry, Halevi, and
Smart (PKC 2012), is able to bootstrap ``packed\'\' ciphertexts (which
encrypt up to a linear number of bits) in time only \\emph{quasilinear}
$\\Otil(\\lambda) = \\lambda \\cdot \\log^{O(1)} \\lambda$ in the security
parameter. While this performance is \\emph{asymptotically} optimal up
to logarithmic factors, the practical import is less clear: the
procedure composes multiple layers of expensive and complex
operations, to the point where it appears very difficult to implement,
and its concrete runtime appears worse than those of prior methods
(all of which have quadratic or larger asymptotic runtimes).
In this work we give \\emph{simple}, \\emph{practical}, and entirely
\\emph{algebraic} algorithms for bootstrapping in quasilinear time, for
both ``packed\'\' and ``non-packed\'\' ciphertexts. Our methods are easy
to implement (especially in the non-packed case), and we believe that
they will be substantially more efficient in practice than all prior
realizations of bootstrapping. One of our main techniques is a
substantial enhancement of the ``ring-switching\'\' procedure of Gentry
et al.~(SCN 2012), which we extend to support switching between two
rings where neither is a subring of the other. Using this procedure,
we give a natural method for homomorphically evaluating a broad class
of structured linear transformations, including one that lets us
evaluate the decryption function efficiently.
Additional news items may be found on the IACR news page.