<p>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:</p>

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

<p>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).</p>

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

<p>The current state-of-the-art for FHE schemes is some combination of:</p>

<p>((Below are PDF links to ePrint.))</p>

<ol>
<li><a href="http://eprint.iacr.org/2012/078.pdf" rel="nofollow">Fully Homomorphic Encryption without Modulus Switching
from Classical GapSVP</a></li>
<li><a href="http://eprint.iacr.org/2011/566.pdf" rel="nofollow">Fully Homomorphic Encryption with Polylog Overhead</a></li>
<li><a href="http://eprint.iacr.org/2012/144.pdf" rel="nofollow">Somewhat Practical Fully Homomorphic
Encryption</a></li>
</ol>

<p><strong>Another Thought:</strong></p>

<p>In case the word <em>"efficiently"</em> 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..."</p>

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

<p>See: <a href="http://eprint.iacr.org/2012/610.pdf" rel="nofollow">Candidate Multilinear Maps from Ideal Lattices</a></p>

<p>..then you should be allowed up to $\kappa$ multiplications, for <em>multilinearity parameter</em> $\kappa$.</p>

<p>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!)</p>

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

<hr>

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

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

<p>IIRC, the GGH multilinear map with, say, $\kappa = 2$ can be seen as reducing (<em>in the simplest case</em>) to groups $(\mathbb{G}_0, \mathbb{G}_1, \mathbb{G}_2)$ and a <em>set of bilinear maps,</em> 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}$.</p>

CC BY-SA 3.0
2013-04-16T07:39:24.960Z
What about $e_0$ in the multilinear map in your explanation? Thanks for your concrete answer.
curious
CC BY-SA 3.0
2013-04-16T20:25:30.213Z
I've edited the notation to hopefully make it more clear what I meant: that you can think of a simple case of the multilinear map as a kind of chain of bilinear maps through a series of ordered groups.

The GGH multilinear maps (paper linked above) is much more general than this, and describing it in the way I did kind of slaughters the essence of their construction. In any case, the point is that I think (with appr. tuning) using the GGH map place of the bilinear map in BGN would give an efficient homomorphic encoding scheme with unbounded additions, and $O(1)$ multiplications (vs just 1).
Daniel Apon
CC BY-SA 3.0
2013-04-16T20:30:25.500Z
And now, speculating: You might even be able to eek out an $\epsilon\log n$-length chain of multiplications ($\epsilon < 1$) for evaluating circuits on $n$ inputs, since the noise in encodings at higher levels of the GGH map functions a lot of like the noise in ciphertexts deep in a circuit of a somewhat homomorphic encryption scheme.
Daniel Apon
CC BY-SA 3.0
2013-04-16T02:35:34.470Z
2013-04-16T20:21:52.887Z
2013-04-16T20:21:52.887Z
Daniel Apon
<p>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 <a href="http://crypto.stanford.edu/~dabo/pubs/papers/2dnf.pdf" rel="nofollow">BGN</a> 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$</p>

CC BY-SA 3.0
2013-03-22T18:12:45.107Z
Isn't $(a+b)\cdot c$ equal to $a\cdot c + b\cdot c$?
Jeffε
CC BY-SA 3.0
2013-03-22T18:14:54.703Z
Why am i so stupid? you are right.
curious
CC BY-SA 3.0
2013-03-22T19:03:07.203Z
Maybe this should be closed ?
Suresh Venkat
<cr.crypto-security><homomorphic-encryption>
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$$
curious
# 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$$

(Asked by: username_0 on 2013-03-22)

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](http://crypto.stanford.edu/~dabo/pubs/papers/2dnf.pdf) 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$

**Tags:** cr.crypto-security, homomorphic-encryption

> **Comments:**
> **username_1**: Isn't $(a+b)\cdot c$ equal to $a\cdot c + b\cdot c$?  
> **username_0**: Why am i so stupid? you are right.  
> **username_2**: Maybe this should be closed ?  

---

## 1 answers

### Answer by username_3 on 2013-04-16. Score: 3 | Accepted answer

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.))

1. [Fully Homomorphic Encryption without Modulus Switching
   from Classical GapSVP](http://eprint.iacr.org/2012/078.pdf)
2. [Fully Homomorphic Encryption with Polylog Overhead](http://eprint.iacr.org/2011/566.pdf)
3. [Somewhat Practical Fully Homomorphic
   Encryption](http://eprint.iacr.org/2012/144.pdf)

**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](http://eprint.iacr.org/2012/610.pdf)

..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}$.

> **Comments:**
> **username_0**: What about $e_0$ in the multilinear map in your explanation? Thanks for your concrete answer.  
> **username_3**: I've edited the notation to hopefully make it more clear what I meant: that you can think of a simple case of the multilinear map as a kind of chain of bilinear maps through a series of ordered groups.  The GGH multilinear maps (paper linked above) is much more general than this, and describing it in the way I did kind of slaughters the essence of their construction. In any case, the point is that I think (with appr. tuning) using the GGH map place of the bilinear map in BGN would give an efficient homomorphic encoding scheme with unbounded additions, and $O(1)$ multiplications (vs just 1).  
> **username_3**: And now, speculating: You might even be able to eek out an $\epsilon\log n$-length chain of multiplications ($\epsilon < 1$) for evaluating circuits on $n$ inputs, since the noise in encodings at higher levels of the GGH map functions a lot of like the noise in ciphertexts deep in a circuit of a somewhat homomorphic encryption scheme.  

---

