2
$\begingroup$

The NTRU key generation involves polynomials and their arithmetic in polynomial rings, which is a bit different from arithmetic in modular integers. In the NTRU cryptosystem, the public key $h$ is computed as:

$h=g⋅F_q \bmod  q \tag{1}\label{r1}$

where $g$ is a chosen polynomial, $F_q$​ is the modular inverse of $f$ modulo $q$ in the ring of polynomials, and $q$ is a modulus, i.e.:

$f^{-1} = F_q \bmod q \tag{2}\label{r2}$

So, $F_q​$ is not simply the multiplicative inverse of $f$ in modular arithmetic but the modular inverse in the ring of polynomials modulo $q$. So, while

$F_q ⋅ f \equiv 1 \bmod  q \tag{3}$

in the polynomial ring, deriving $F_q$​ from $f$ is not straightforward and involves polynomial arithmetic, not integer arithmetic. At least with NTRUEncrypt it works so that the $F_q$ factor in $h$ cancels out with $f$.

Regarding my question about deriving $g$ from $h$ and $f$, from (\ref{r1}) follows:

$g \equiv h ⋅ F_q^{−1} \bmod  q \tag{4}$

And with (\ref{r2}), in theory, we could compute $g$ as

$g \equiv h ⋅ f \bmod  q \tag{5}\label{r5}$

My initial question now boils down to the clarification if this $g$ (\ref{r5}) can actually be expected to be identical to the $g$ (\ref{r1}) initially used in the key-pair generation - or could it also be "somehow equivalent" or even "one of many solutions"?

$\endgroup$

1 Answer 1

2
$\begingroup$

Clearly, equation (5) in your question determines $g$ uniquely up to the possible addition of a multiple of $q$. But $g$ also has the property of having small coefficients (much smaller than $q/2$ in absolute value; depending on the version of NTRU you're looking at, possibly at most $1$ in absolute value). Both conditions together uniquely determine $g$: each coefficient is going to be equal to the unique integer of absolute value $<q/2$ congruent mod $q$ to the corresponding coefficient of $h\cdot f$.

$\endgroup$
5
  • $\begingroup$ Thank you for clarification! :) so it depends on version/implementation of NTRU, but most likely yes. $\endgroup$
    – Tobsec
    Oct 14, 2023 at 5:52
  • 1
    $\begingroup$ To clarify further: the size of the coefficients of $g$ depends on the specific version of NTRU, but the fact that they are small compared to $q/2$ is always satisfied, so the answer is always yes. $\endgroup$ Oct 14, 2023 at 13:59
  • $\begingroup$ alright, I see, thank you! can you recommend any repo/lib/modules with which I can play around i.e. which do output g, f and h and allow me to compute f*h? I already searched my way through github and googled, found some e.g. python code, but couldn't spot something that supports all of this (especially f*h). $\endgroup$
    – Tobsec
    Oct 14, 2023 at 20:28
  • $\begingroup$ I would recommend working in SageMath. You can easily find NTRU code for it, and it natively supports the required algebraic structures, so multiplication should be directly available. $\endgroup$ Oct 15, 2023 at 5:06
  • $\begingroup$ thanks for your hint to SageMath. I'll try it. in the meanwhile, I could test the Wikipedia example with Wolfram Mathematia: ``` f = -1 + x + x^2 - x^4 + x^6 +x^9 - x^10; g = -1 + x^2 +x^3 + x^5 -x^8 - x^10; h = 8 - 7x - 10x^2 - 12x^3 + 12x^4 - 8x^5 + 15x^6 - 13x^7 + 12x^8 - 13x^9 + 16x^10; fh = Expand[f*h]; fhModN = PolynomialMod[fh, {x^11-1}]; fhMod4 = PolynomialMod[fhModN, 4]; fhMod4CL = CoefficientList[fhMod4, x]; g2CL = Reverse[If[# != 0, # - 2, #] & /@ fhMod4CL]; g2 = Expand[FromDigits[g2CL, x]]; Print[Equivalent[ g2, g]]; ``` -> True NumPy worked, too, btw. $\endgroup$
    – Tobsec
    Oct 15, 2023 at 23:05

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.