3
$\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$
7
  • $\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, 2015 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, 2015 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$ Mar 27, 2015 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, 2015 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, 2015 at 13:37

1 Answer 1

2
$\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 and acknowledge you have read our privacy policy.

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