2
$\begingroup$

NTRU has some homomorphic properties modulo q, supporting both addition and multiplication. Due to its nature, it cannot support many of them. My main focus currently is in the addition, so the question is how many additions could it support to consider the result reliable? I believe that a naive bound would be $q/2$ but is there anything better?

$\endgroup$
  • $\begingroup$ Maybe that's covered in this paper: López-Alt et al. "On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption" (2012) $\endgroup$ – cygnusv Mar 27 '15 at 10:01
  • $\begingroup$ It would be better if you specify first which version of NTRU are you talking about. Is it the "regular" NTRU or the provably-secure version from Stehlé and Steinfeld? $\endgroup$ – cygnusv Mar 27 '15 at 10:13
  • $\begingroup$ Thanks, I will have a look at the proposed paper. You are right about your comment, as there are many flavors. I had in mind the LWE variant of Stehlé and Steinfeld, but any other would work as well. $\endgroup$ – absinthe_minded Mar 27 '15 at 12:25
  • $\begingroup$ In that case, then it would depend ultimately in the choice of parameters $(n, \alpha, \sigma,$ etc). $\endgroup$ – cygnusv Mar 27 '15 at 12:38
  • 1
    $\begingroup$ You have the correctness condition wrong. It should be $||f\cdot \Sigma c_i||_{\infty} < q/2$. $\endgroup$ – cygnusv Mar 27 '15 at 13:37
1
$\begingroup$

Since you referring to the LWE variant of Stehlé and Steinfeld, I will try to give you an answer to your question in that context. Note that these results are a mere extension of the correctness condition in Lemma 3.7 from the revised version of the paper [SS13]. As I said in the comments, at the end it all depends on the choice of parameters ($n, \alpha, q$, etc), and additionally, on the number of additions you want to support.

In this scheme, ciphertexts are of the form $c = h s + p e + m$, where $h$ is the public key, $s$ and $e$ are sampled from a Gaussian distribution, $p$ is a public parameter, and $m$ is the message. Public keys are of the form $h = p g f^{-1}$, where $f$ is the secret key, and $g$ a random polynomial.

The correctness condition for one ciphertext is $||f \cdot c_i ||_{\infty} \leq q/2$. We want to check the conditions for decrypting correctly a sum of $k$ ciphertexts:

$c_{sum} = \sum\limits^k_{i=1} c_i = \sum\limits^k_{i=1}(h s_i + p e_i + m_i)$

Since $f h = f (p g f^{-1}) = p g$, then $f \cdot c_i = f h s_i + p f e + f M = p g s_i + p f e + f M$

Hence, we want to check whether $||f \cdot c_{sum} ||_{\infty} \leq q/2$, where:

$f \cdot c_{sum} = \sum\limits^k_{i=1}(p g s_i + p f e_i + f m_i) = \sum\limits^k_{i=1}p g s_i + \sum\limits^k_{i=1}p f e_i + \sum\limits^k_{i=1}f m_i$

Lemma 3.7 provides the following bounds:

$||pgs_i||_{\infty}, ||pfe_i||_{\infty} \leq 8 \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma$

$||fM||_{\infty} \leq 4n||p||^2 \sigma$

Therefore, $||f \cdot c_{sum}||_{\infty} \leq 2k\cdot(8 \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma) + 4n||p||^2 \sigma$.

Next, assuming that $n^{0.75} \leq \alpha q$, as in Lemma 3.7, we have that:

$||f \cdot c_{sum}||_{\infty} \leq 16 k \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma + 4n^{0.25}\alpha q||p||^2 \sigma$

After some simplifications, we obtain the following bound:

$||f \cdot c_{sum}||_{\infty} \leq (16 k + 4) n^{0.25}\alpha q\omega(\log n)||p||^2 \sigma$

Note that when $k=1$, it produces precisely the same result than Lemma 3.7. Finally, similarly to Lemma 3.7, we have to initially assume that $ \omega( n^{0.25}\log n)\alpha q k ||p||^2 \sigma < 1$, so the correctness condition for the sum of $k$ ciphertexts holds.

A final note: these results, as the one from Lemma 3.7, are not tight, and depend heavily on the choice of parameters. My guess is that you can sum (much) more than $k$ ciphertexts, and still decrypt correctly.

References

[SS13] Stehlé, D., & Steinfeld, R. (2013). Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices. IACR Cryptology ePrint Archive, 2013, 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.