FOCS 2011
TechTalks from event: FOCS 2011
We will be uploading the videos for FOCS 2011 during the week of Nov 28th 2011. If you find any discrepancy, please let us know by clicking on report error link on talk page. If you did not permit the video to be published and by mistake we have published your talk, please notify us immediately at support AT weyond.com
2A

Efficient Fully Homomorphic Encryption from (Standard) LWEWe present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worstcase hardness of short vector problems on arbitrary lattices. As icing on the cake, our scheme is quit e efficient, and has very short ciphertexts. Our construction improves upon previous works in two aspects: 1. We show that ``somewhat homomorphic'' encryption can be based on LWE, using a new {\em relinearization} technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. 2. More importantly, we deviate from the ``squashing paradigm'' used in all previous works. We introduce a new {\em dimension reduction} technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, without introducing additional assumptions. In contrast, all previous works required an additional, very strong assumption (namely, the sparse subset sum assumption). Since our scheme has very short ciphertexts, we use it to construct an asymptoticallyefficient LWEbased singleserver private information retrieval (PIR) protocol. The communication complexity of our protocol (in the publickey model) is $k \cdot \polylog\,k+\log DB$ bits per singlebit query, which is better than any known scheme. Previously, it was not known how to achieve a communication complexity of even $\poly(k, \logDB)$ based on LWE.

Fully Homomorphic Encryption without Squashing Using Depth3 Arithmetic CircuitsAll 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 DiffieHellman. 2. The first FHE scheme based entirely on worstcase hardness: Specifically, we describe a "leveled" FHE scheme whose security can be quantumly reduced to the approximate shortest independent vector problem over ideal lattices (idealSIVP). 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 ciphertext! 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" (nonleveled) FHE by assuming circular security. Our main technique is to express the decryption function of SWHE schemes as a depth3 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.

Coin Flipping with Constant Bias Implies OneWay FunctionsIt is well known (\cf Impagliazzo and Luby [FOCS '89]) that the existence of almost all ``interesting" cryptographic applications, \ie ones that cannot hold information theoretically, implies oneway functions. An important exception where the above implication is not known, however, is the case of coinflipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. While Impagliazzo and Luby proved that coinflipping protocols that are safe against negligible bias do imply oneway functions, and, very recently, Maji, Prabhakaran, Sahai and Schreiber [FOCS '10] proved the same for constantround protocols (with any nontrivial bias). For the general case, however, no such implication was known. We make a significant step towards answering the above fundamental question, showing that coinflipping protocols safe against a constant bias (concretely, $\frac{\sqrt{2} 1}{2}$) imply oneway functions.

How to Garble Arithmetic CircuitsYao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$ into a ``garbled circuit'' $\hC$ along with $n$ pairs of $k$bit keys, one for each input bit, such that $\hC$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constantround secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit $C : \Z^n\to\Z^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\hC$ along with $n$ affine functions $L_i : \Z\to \Z^k$ such that $\hC$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the decisional variant of the learning with errors (LWE) problem.