# How do I check if the secret key polynomial of the ATV-FHE (NTRU based) scheme is invertible?

I want to implement the ATV-FHE scheme as described here https://eprint.iacr.org/2014/039.pdf. To generate the secret key polynomial I compute f = 2*u + 1 , with scheme parameters chosen such that this polynomial is invertible with high probability.

If I want to compute the public key I should compute it as indicated in section 2 :

$h(i) = 2g(i)*[ ( f(i) )^{(-1)} ]$

or should I sample the public key as indicated in section 3 Parameter selection in NTRU_FHE :

Recall that for the NTRU-FHE scheme, the public key is of the form $h = 2gf^{(-1)}$ where $g$; $f$ chosen from a Gaussian distribution $D$ where $f$ is kept secret. The DSPR problem is to distinguish polynomials of the form $h = 2gf^{(-1)}$ from samples $h_0$ picked uniformly at random from the ring $Rq$. If the DSPR problem is hard, we can replace $h = 2gf^{(-1)}$ by some uniformly sampled $h_0$.

The bad part for the second option (described in section 3) is that parameter selection is very difficult to be made as noted here

The impact of the new parameter settings to the security level is largely unknown and requires careful research. However, even if we assume that the DSPR problem is hard for typical NTRU-FHE parameter selection, concrete parameters are still hard to chose. The RLWE problem is still relatively new and lacks thorough security analysis.$h_0$.

I have found an alternative so far: to generate a random polynomial and to verify if this polynomial is the invers of the secret key polynomial. Here is an example : https://github.com/tlepoint/homomorphic-simon/blob/master/YASHE/YASHEKey.cpp, in constructor YASHEKey::YASHEKey there is a portion of code

if(sigmakey == 1)
{
// Sample g, f1 with coefficients in {-1,0,1}
fmpz_mod_polyxx g(q);

fmpz_mod_polyxx f1(q);

binaryGen(g, ell-1);

do
{
binaryGen(f1, ell-1);
*f = t*f1+one;
finv = (*f).invmod(*phi);
}
while (((*f)*finv)%(*phi) != one);

*h = (t*g*finv)%(*phi);
}

• This is a nontrivial question for any cryptosystem like NTRU, unfortunately. It involves lots of pretty complex math. Here's a technical report on the subject that may help you: securityinnovation.com/uploads/Crypto/NTRUTech009.pdf – pg1989 Nov 11 '15 at 23:56
• Your 2nd "option" to select the secret key is not an option at all. It is part of the security proof, in which one assumption "$h=2gf^{(-1)}$ with $f, g$ Gaussian and $f$ secret" is replace by another assumption "$h'$ is uniformly sampled". Distinguishing $h$ from $h'$ is the DSPR-problem, and it's assumed to be hard. – j.p. Nov 12 '15 at 13:39