On the (M)iNTRU Assumption in the Integer Case

Abstract

In AsiaCrypt 2019, Genise, Gentry, Halevi, Li and Micciancio put forth two novel and intriguing computational hardness hypotheses: The inhomogeneous NTRU ($\mathsf {iNTRU}$) assumption and its matrix version $\mathsf {MiNTRU}$. In this work, we break the integer case of the $\mathsf {iNTRU}$ assumption through elementary lattice reduction, and we describe how the attack might be generalized to polynomial rings and to the low dimensional $\mathsf {MiNTRU}$ assumption with small noise.

A Proof of Lemma 1

We observe that by the properties of the Euclidean and the infinity norm, we have

$$\mathbb {P}\left( \left( \left\| [r\mathbf {y}\mod q^2]\right\| _2\le Bq \right) \cap (r\in S)\right) \le \mathbb {P}\left( \left( \max \big \{ \left| [r\mathbf {y}\mod q^2]\right| \big \}\le Bq\right) \cap (r\in S) \right) $$

where the maximum is taken over all the modulo reduced entries of $r\mathbf {y}$. The right expression is equal to

$$\mathbb {P}\left( \left( \bigcap _{i=0}^{\ell -1} \underbrace{\big (\left| [ry_iq \mod q^2]\right| \le Bq\big )}_{:=C_i}\right) \cap \underbrace{\big (\left| [r \mod q^2]\right| \le Bq \big )}_{:=C_{\ell }}\cap (r\in S) \right) .$$

Each event $C_0,\dots ,C_{\ell -1}$ in the probability statement can be written as a union of events $C_i=\bigcup _{\beta _i=-Bq}^{Bq} ([ry_iq\mod q^2]=\beta _i)$. As this event can only take place whenever $\beta _i$ is a multiple of q (otherwise, the equality cannot be satisfied), we need only to consider the restricted union of events $\bigcup _{\beta _i=-B}^{B} ([ry_iq\mod q^2]=\beta _i q)=\bigcup _{\beta _i=-B}^{B} ([ry_i\mod q]=\beta _i)$. Furthermore, $C_{\ell }=\bigcup _{\beta _{\ell }=-Bq}^{Bq} ([r\mod q^2]=\beta _{\ell })=\bigcup _{\beta _{\ell }=-Bq}^{Bq} (r=\beta _{\ell })$ which is restricted to $\beta _{\ell }\in S$ by the last condition. Thus, our overall probability is equal to

$$\mathbb {P}\left( \left( \bigcap _{i=0}^{\ell -1} \bigcup _{\beta _i=-B}^{B} ([ry_i\mod q]=\beta _i) \right) \; \cap \; \left( \bigcup _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq} (r=\beta _{\ell }) \right) \right) .$$

Reordering the events gives

$$\mathbb {P}\left( \bigcup _{\beta _0=-B}^{B} \dots \bigcup _{\beta _{\ell -1}=-B}^{B} \bigcup _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq} \left( \bigcap _{i=0}^{\ell -1} ([ry_{i} \mod q]=\beta _i) \cap (r=\beta _{\ell }) \right) \right) .$$

As the events are mutually exclusive, this probability is equal to

$$\sum _{\beta _0=-B}^B \dots \sum _{\beta _{\ell -1}=-B}^B\sum _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq}\mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([ry_{i} \mod q]=\beta _i) \cap (r=\beta _{\ell }) \right) .$$

Using Bayes’ conditional probability rule followed by Euler’s rule of interchanging finite sums, this quantity can be rewritten as:

$$\begin{aligned}&\sum _{\beta _0=-B}^B \dots \sum _{\beta _{\ell -1}=-B}^B\sum _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq}\mathbb {P}\left( r=\beta _{\ell }\right) \mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([ry_{i} \mod q]=\beta _i) \;\Big |\; (r=\beta _{\ell }) \right) \\ =&\sum _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq} \mathbb {P}\left( r=\beta _{\ell } \right) \sum _{\beta _0=-B}^B \dots \sum _{\beta _{\ell -1}=-B}^B\mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([ry_{i} \mod q]=\beta _i) \;\Big |\; (r=\beta _{\ell }) \right) \end{aligned}$$

Naturally $\mathbb {P}\left( r=\beta _{\ell } \right) =\frac{1}{q^2}$ for any $\beta _{\ell }$. It remains to investigate the value of the rightmost probability. To do so, we rewrite $\beta _{\ell }=g_{\ell }\beta '_{\ell }$ where $g_{\ell }=\gcd (\beta _{\ell },q)$. Then, for fixed $\beta _0,\dots ,\beta _{\ell -1},\beta _{\ell }$:

$$\begin{aligned}&\mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([ry_{i} \mod q]=\beta _i) \;\Big |\; (r=\beta _{\ell }) \right) \\ =\,&\mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([\beta _{\ell } y_{i} \mod q]=\beta _i) \right) \\ =\,&\mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([g_{\ell }\beta '_{\ell } y_{i} \mod q]=\beta _i) \right) \end{aligned}$$

The events in this probability will only be satisfiable if $\beta _i$ is a multiple of $g_{\ell }$, say $\beta _i=\beta '_ig_{\ell }$. Thus, our cumulative probability rewrites as

$$\begin{aligned}&\sum _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq} \frac{1}{q^2} \sum _{\beta '_0=-\lfloor B/g_{\ell }\rfloor }^{\lfloor B/g_{\ell }\rfloor } \dots \sum _{\beta '_{\ell -1}=-\lfloor B/g_{\ell }\rfloor }^{\lfloor B/g_{\ell }\rfloor } \mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([g_{\ell }\beta '_{\ell } y_{i} \mod q]=\beta '_ig_{\ell }) \right) \\ =&\sum _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq} \frac{1}{q^2} \sum _{\beta '_0=-\lfloor B/g_{\ell }\rfloor }^{\lfloor B/g_{\ell }\rfloor } \dots \sum _{\beta '_{\ell -1}=-\lfloor B/g_{\ell }\rfloor }^{\lfloor B/g_{\ell }\rfloor } \mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([\beta '_{\ell } y_{i} \mod \frac{q}{g_{\ell }}]=\beta '_i) \right) \\ =&\sum _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq} \frac{1}{q^2} \sum _{\beta '_0=-\lfloor B/g_{\ell }\rfloor }^{\lfloor B/g_{\ell }\rfloor } \dots \sum _{\beta '_{\ell -1}=-\lfloor B/g_{\ell }\rfloor }^{\lfloor B/g_{\ell }\rfloor } \mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([ y_{i} \mod \frac{q}{g_{\ell }}]=[\beta '_i\beta '^{-1}_{\ell }\mod \frac{q}{g_{\ell }}]) \right) \end{aligned}$$

where we used the fact that $g_{\ell }=\gcd (\beta _{\ell },q)$ which implies that $\beta '_{\ell }$ is invertible modulo $\frac{q}{g_{\ell }}$. It is now clear that the remaining events are independent as they only depend on $y_i$. Thus

$$\begin{aligned}&\mathbb {P}\left( \bigcap _{i=0}^{\ell -1} ([ y_{i} \mod \frac{q}{g_{\ell }}] =[\beta '_i\beta '^{-1}_{\ell }\mod \frac{q}{g_{\ell }}]) \right) \\ =&\prod _{i=0}^{\ell -1} \mathbb {P}\left( [ y_{i} \mod \frac{q}{g_{\ell }}]=[\beta '_i\beta '^{-1}_{\ell }\mod \frac{q}{g_{\ell }}] \right) \\ =&\left( \frac{1}{\frac{q}{g_{\ell }}}\right) ^{\ell }\\ =&\left( \frac{g_{\ell }}{q}\right) ^{\ell }. \end{aligned}$$

Thereby, the cumulative probability is given by

$$ \sum _{\underset{\beta _{\ell }\in S}{\beta _{\ell }=-Bq}}^{Bq} \frac{\ell (2\lfloor B/g_{\ell }\rfloor +1)}{q^2} \left( \frac{g_{\ell }}{q}\right) ^{\ell }. $$

   $\square$