I have the polynomial ring $R = \mathbb{Z}[X]/(X^N - 1)$ with $N = 11$ and $h \in R$ with \begin{equation*} h = 7 -11X - 7X^2 -12X^3 + 8X^4 - 11X^5 + -8X^6 + 11X^7 - 4X^8 + 2X^9 + 3X^{10} \end{equation*} Now I want to find the polynomial $u$ such that \begin{equation*} u\cdot h + v\cdot (X^N - 1) \equiv X - 1 \ (\textrm{mod} \ 32) \end{equation*} where we assume $\gcd(h, X^N - 1) = X - 1$ reducing coefficients $\textrm{mod} \ 32$. If we also let $*$ denote the multiplication in $R$, I can easily find $u$ such that $u*h \equiv X - 1 \ (\textrm{mod} \ 2)$ using the extended Euclidean algorithm, and it's $u = 1+X+X^{4}+X^{5}+X^{9}$, but I'm having issues using this to construct the solution such that $u' * h \equiv X - 1 \ (\textrm{mod} \ 32)$. Can someone outline an algorithm or link me some reading material on how to do this?
2
-
$\begingroup$ Maybe this question should be moved to math SE, there is no crypto related question in here $\endgroup$– tyloNov 22, 2020 at 16:58
-
$\begingroup$ Thank you. The reason I asked in crypto SE is because this is a part of an attack on the NTRU cryptosystem where an unpadded message block $m$ has been encrypted with different randomly generated $\phi_i \in L(3, 3)$, that is $\phi_i \in R$ where three of its coefficients are 1, and three of its coefficients are -1 with the rest being 0. The first step in this attack is to find the $u$ in my original question. $\endgroup$– LightsOutTorusNov 23, 2020 at 1:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
One way to raise solutions to higher powers of the modulus is Hensel's Lemma.
- First, you need to express your element as a root of a function: $g(u)= hu - (X-1)$
- Find the solution modulo 2, which you already did.
- Use the Lemma to raise this solution to higher powers of 2. Maybe it is useful to do this in several steps. Find the solutions mod 4,8,16 and then 32.
