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);
}