How to homomorphically and "efficiently" evaluate $$(a_1 + b_1) \cdot c_1 + (a_2 + b_2) \cdot c_2 + \ldots + (a_n + b_n) \cdot c_n$$ Can i evaluate a formula $(a_i + b_i) \cdot c_i$ if i have the encryption of $a_i,b_i,c_i$ respectively using a homomorphic encryption scheme that supports multiplications and additions, supposing that each value is a small integer? I am aware of BGN scheme that evaluates 2-DNF formulas but in my scheme i want the other way around. Instead of $a_1 \cdot b_1 + a_2 \cdot b_2 + \ldots +a_n \cdot b_n$ i want to evaluate $(a_1 + b_1) \cdot c_1 + (a_2 + b_2) \cdot c_2 + \ldots + (a_n + b_n) \cdot c_n$
The original question seems to assume that the BGN scheme is the state-of-the-art for problems like this (correct me if I'm wrong :)), so for what it's worth:

The BGN scheme scheme is a prototypical version of a somewhat homomorphic encryption scheme -- the bilinear map gives you a single multiplication on any ciphertext still in the source group $\mathbb{G}$, and (of course) unbounded additions.

It's worth noting that the additively homomorphic property (ie, the unbounded additions) comes from the algebraic representation of the ciphertexts. For similar reasons, El Gamal has multiplicatively homomorphic ciphertexts (unbounded multiplications, no additions), and Paillier has additively homomorphic ciphertexts (no multiplications, unbounded additions).

I think around a year after BGN, Craig Gentry came out with the first fully homomorphic encryption scheme (unbounded multiplications, unbounded additions).

The current state-of-the-art for FHE schemes is some combination of:

((Below are PDF links to ePrint.))


Fully Homomorphic Encryption without Modulus Switching
from Classical GapSVP
Fully Homomorphic Encryption with Polylog Overhead
Somewhat Practical Fully Homomorphic
Encryption


Another Thought:

In case the word "efficiently" in the title was intended to be interpreted as "not FHE," here's an independent observation of mine that might be useful for situations like you ran into just now -- i.e. "I think I need more multiplications than the bilinear map in BGN allows, but I don't want to take the huge hit of FHE..."

If you implement a BGN-like scheme, but substitute a multilinear map for the bilinear map..

See: Candidate Multilinear Maps from Ideal Lattices

..then you should be allowed up to $\kappa$ multiplications, for multilinearity parameter $\kappa$.

The complexity of the GGH multilinear map depends on $\kappa$, but so long as $\kappa=O(1)$, I have a feeling there wouldn't be much difference between the resulting scheme and the BGN scheme in terms of concrete efficiency. (In fact, it's an interesting question on its own!)

In any case, suppose you ran into a situation where you needed.... THREE multiplications per plaintext... Think about using a multilinear map.



A few more details for intuition about what multilinear maps are, if they're new to you:

BGN uses groups $(\mathbb{G}, \mathbb{G}_T)$ and a map $e: \mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_T$.

IIRC, the GGH multilinear map with, say, $\kappa = 2$ can be seen as reducing (in the simplest case) to groups $(\mathbb{G}_0, \mathbb{G}_1, \mathbb{G}_2)$ and a set of bilinear maps, written generally as $e = \{e_i\}_{i\in [0,...,\kappa-1]}$ where for all $i$, $e_i : \mathbb{G}_i\times\mathbb{G}_i\rightarrow\mathbb{G}_{i+1}$.