In the YASHE (Yet Another Somewhat Homomorphic Encryption) algorithm, the beggining of the key generation step specifies:

Sample $\ f',g ← χ_{key}$ and let $\ f = [tf' + 1]_q$.

If $\ f$ is not invertible modulo $q$, choose a new $\ f'$.

Compute the inverse $\ f^{−1} ∈ R$ of $\ f$ modulo $q$ and set $h = [t\ g\ f^{−1}]_q$.

The previous section of the algorithm descibres what each of these parameters are

Given the security parameter $λ$, fix a positive integer $d$ that determines $R$, moduli $q$ and $t$ with $1 < t < q$, distributions $χ_{key}$, $χ_{err}$ on $R$, and an integer base $w > 1$.

How can you tell if:

  1. $f$ is invertible?

and if so

  1. what $\ f^{-1}$ is?
  • $\begingroup$ This might be more suited for math stack exchange, the context is crypto but the question itself is pure math i.e. how can I tell if a polynomial has an inverse in a field, and if it does how do I compute it. These answers may help. $\endgroup$ – puzzlepalace Jul 1 '16 at 23:11

To invert a polynomial in the quotient ring $F_q[X]/(\phi(X))$ there are two cases:

-> Either $\phi$ is irreducible modulo $q$, in which case every polynomial is inversible

-> Either $\phi$ is not irreducible, and one reasons with the Chinese remainder theorem.

In the first case, to find the inverse, just use Extended Euclides to find two polynomials $U,V$ such that


(I'll let you deduce why $gcd(\phi,f)=1$) and therefore $Uf=1 \in R$.

For the YASHE parameters, $\phi$ is not irreducible, and therefore a quick answer to your question is

$\mbox{ if } gcd(f,\phi)\neq 1$ then $\phi$ is not invertible, if $gcd(f,\phi)= 1$ use Euclides as before.


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.