Suppose two parties, at most one of them being semi-honest, attempt to compute a function interactively and securely. The communication incurred during such a computation, while done unconditionally, depends on the circuit-size of the function being computed. However, it is possible to break this 'circuit-size barrier' if we have the LWE (learning with errors) assumption, since we know how to get fully homomorphic encryption (FHE) from LWE and then using FHE with this simple protocol - the first party encrypts its input and sends them to the second party and then the second party applies the function locally under the FHE and outputs the function value.
In a 2016 CRYPTO paper, Boyle, Gilboa and Ishai constructed a primitive known as Homomorphic Secret Sharing, which also breaks the circuit-size barrier for certain circuits, but without heavy assumptions like LWE. In fact the only assumption they used was DDH (decisional Diffie-Hellman). In this talk, we will see this construction.
paper link - https://eprint.iacr.org/2016/585.pdf
