[Busec] a new homomorphic encryption scheme from gentry...

Sharon Goldberg goldbe at cs.bu.edu
Tue May 3 15:06:35 EDT 2011

Hi All,

Just saw this - apparently Craig's gotten rid of the squashing
assumption in fully homomorphic encryption!


---------- Forwarded message ----------
From: Rosario Gennaro <rosario at us.ibm.com>
Date: Tue, May 3, 2011 at 3:01 PM
Subject: CRYPTOGRAPHY SEMINAR - Thursday 5/5 2:30pm
To: SeminarCrypto%IBMUS at us.ibm.com


Thursday May 5, 2:30pm, Hawthorne GN-K30
[Notice different time]

               Fully Homomorphic Encryption without Squashing Using Depth-3
Arithmetic Circuits
                               (or, Chimeric Fully Homomorphic Encryption)

                                               Craig Gentry
                                               IBM Research


 All currently known fully homomorphic encryption (FHE) schemes use
 the same blueprint from [Gentry 2009]: First construct a somewhat
 homomorphic encryption (SWHE) scheme, next "squash" the decryption
 circuit until it is simple enough to be handled within the
 homomorphic capacity of the SWHE scheme, and finally "bootstrap" to
 get a FHE scheme. In all existing schemes, the squashing technique
 induces an additional assumption: that the sparse subset sum problem
 (SSSP) is hard.

 We describe a \emph{new approach} that constructs FHE as a hybrid of
 a SWHE scheme and a multiplicatively homomorphic encryption (MHE)
 scheme, such as Elgamal. Our construction eliminates the need for
 the squashing step, and thereby also removes the need to assume the
 SSSP is hard. We describe a few concrete instantiations of the new
 method, obtaining the following results:

 1. A "simple" FHE scheme where we replace SSSP with Decision
 2. The first FHE scheme based entirely on worst-case hardness:
 Specifically, we describe a "leveled" FHE scheme whose security can
 be quantumly reduced to the approximate shortest independent vector
 problem over ideal lattices (ideal-SIVP).
 3. Some efficiency improvements for FHE: While at present our new
 method does not improve computational efficiency, we do provide an
 optimization that reduces the ciphertext length. For example, at one
 point, the entire FHE ciphertext may consist of a single Elgamal

 Our new method does not eliminate the bootstrapping step. Whether
 this can be done remains an intriguing open problem. As in the
 previous blueprint, we can get "pure" (non-leveled) FHE by assuming
 circular security.

 Our main technique is to express the decryption function of SWHE
 schemes as a depth-3 arithmetic circuit of a particular form. When
 evaluating this circuit homomorphically, as needed for
 bootstrapping, we temporarily switch to a MHE scheme, such as
 Elgamal, to handle the product part of the circuit. We then
 translate the result back to the SWHE scheme by homomorphically
 evaluating the decryption function of the MHE scheme. (Due to the
 special form of the circuit, switching to the MHE scheme can be done
 without having to evaluate anything homomorphically.) Using our
 method, the SWHE scheme only needs to be capable of evaluating the
 MHE scheme's decryption function, not its own decryption function.
 We thereby avoid the circularity that necessitated squashing in the
 original blueprint.

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list