6
$\begingroup$

An NTRU public key is generated essentially by multiplying the inverse of a polynomial $f$ by a polynomial $g$. The polynomial $f$ is the private key; $g$ is discarded.

My question is: Is it insecure to hand out multiple public keys for the same private key, i.e. using the same $f$ but different $g$'s?

$\endgroup$
  • $\begingroup$ Great question! Never thought about that... $\endgroup$ – cygnusv Nov 28 '15 at 18:20
7
$\begingroup$

According to current knowledge, handing out multiple public keys (with independent numerators) for the same private key $f$ is not insecure, as long as the parameters are instantiated appropriately. There is some small loss in concrete security, but nothing like an efficient attack is known.

The standard NTRU lattice for just one public key $h$ is \begin{equation} L_h = \{ (u,v) : u \cdot h = v \pmod{q} \}, \end{equation} and $(f,g) \in L_h$ is a lattice vector that is "unusually short" relative to what the Gaussian heuristic predicts for a "random" $2n$-dimensional lattice having the same determinant $q^n$ as $L_h$. Essentially, this gap controls how hard it is to find the secret key using lattice reduction (smaller gap means harder to break).

With multiple public keys $h_i = g_i \cdot f^{-1} \pmod{q}$ that share a private key $f$, we can define a similar lattice \begin{equation} L = \{ (u, v_1, \ldots, v_t) : u \cdot h_i = v_i \pmod{q} \}. \end{equation} This $(t+1)n$-dimensional lattice has determinant $q^{tn}$, so the Gaussian heuristic predicts a minimum distance of $\approx q^{t/(t+1)}$, yet $(f,g_1, g_2, \ldots, g_t)$ is an "unusually short" lattice vector in $L$. The gap is typically larger than in the single-key case, making it concretely somewhat easier to find the secret key. But as long as the gap is not huge (e.g., polynomial in $n$) and the dimension is large enough, algorithms like LLL/BKZ won't be able to find the secret key in any feasible amount of time.

Another reason is that, informally, from one public key $h$ we can generate many public keys $h_i$ having the same secret key, by multiplying $h$ by random small $g_i$. The resulting public keys won't be distributed like "true" keys, nor will they be independent, but this at least give some intuition why it's hard to find the secret key from many public keys.

It's worth remarking that there's a close similarity here to LWE, where one can get an unbounded number of noisy random inner products with a secret vectors, and the number of such samples does not have a major effect on hardness (though it does have some).

$\endgroup$
-1
$\begingroup$

According to this paper, two public keys are insecure if the corresponding private keys, $f$ and $f'$ are too close to each other*. It follows that public keys are insecure if $f=f'$ regardless of the $g$ values.

* $\|f-f'\| < min(\|f\|, \|f'\|)$

$\endgroup$
  • $\begingroup$ This paper requires that $||g-g'|| < \min(||g||, ||g'||)$, which, as the paper notes, is highly unlikely to occur for typical distributions of keys. So, we cannot conclude from this paper that reusing $f$ is insecure. Indeed, I don't believe that there's any inherent problem with doing so. $\endgroup$ – Chris Peikert Dec 2 '15 at 20:18
  • $\begingroup$ I think only one of the two conditions needs to hold because it says: "it is possible to find the private key $(f, g)$ when $\|g-g'\| < min(\|g\|, \|g'\|)$. We have shown that the same techniques apply when $h'$ is invertible modulo $q$ and $\|f-f'\| < min(\|f\|, \|f'\|)$. $\endgroup$ – devin.omalley Dec 3 '15 at 18:49
  • $\begingroup$ Ok, I see that now, but this paper has serious flaws and shouldn't be relied upon. For one, when $g=g'$ the attack becomes vacuous, because it searches for the all-0s vector. Second, the paper doesn't prove or demonstrate that LLL actually succeeds in finding the secret key. It only shows that in the lattice under consideration, the desired vector is somewhat shorter than the secret-key vector in the standard NTRU lattice. In large enough dimension, LLL won't be able to exploit this, because it doesn't find short enough vectors. $\endgroup$ – Chris Peikert Dec 3 '15 at 20:03
  • $\begingroup$ Makes sense. If you post an answer, I'll accept it. $\endgroup$ – devin.omalley Dec 4 '15 at 16:48

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.