Lattice attacks against Multilinear Maps [CLT13]

Question

I am currently studying an article on a construction of Multilinear maps. There are some attacks on the scheme presented by the authors and I got stuck at the one in section 5.1.

I will try to summarize the ideas presented there and ask the questions in the end:

Consider the product of $n$ secret distinct primes $p_i$, publish $x_0 = \prod_{i=1}^n{p_i}$. Given a set of $\tau$ integers $x_j \in Z_{x_0}$ such that $x_j \text{ mod } p_i = r_{i, j}g_i$ the goal is to recover (some of) the values $\textbf{r}_{i} := (r_{i, j}g_i)_{1\le j \le t}$

The attack works as follows: Compute the orthogonal lattice $L$ spanned by some subset $\textbf{x} = (x_j)_{1 \leq j \leq t}$ with $n \lt t \leq \tau$ and apply LLL algorithm on $L$. This results in a reduced basis $(u_1, \dots, u_t)$.

Now, because all vectors $\textbf{u} \in L$ are perpendicular to $\textbf{x}$, namely $\textbf{u} \cdot \textbf{x} = 0 \text{ mod } x_0$, reducing the expression modulo $p_i$ gives that $\textbf{u} \cdot \textbf{r}_i = 0 \text{ mod } p_i$. Assuming that the product of norms of vectors $||\textbf u||$ $||\textbf r_i||$ is smaller than $||p_i||$ then that equation can be solved in $\mathbb{Z}$.

What I don't understand is:

1. The conclusion of authors that the vectors $(\textbf u_1, \dots, \textbf u_{t - n})$ resulted by LLL reduction on $L$ are perpendicular to $\textbf r_i$. If this is true, then computing $\textbf r_i$ can be done by Gaussian Elimination in $\mathbb{Z}$.
2. How does one get such samples $x_j$, namely encodings of zero on the level zero?

Answer 1

1. Why can't we find the vectors $\mathbf{r}_i$ by Gaussian Elimination?

The problem here is that $\mathbf{r}_i$ are small. You can use Gaussian Elimination to recover vectors orthogonal to $(\mathbf{u}_1, ..., \mathbf{u}_{t-n})$, but the vectors found will not be short vectors.

2. How to get encodings in level-zero?

Actually, one does not get encodings in level-zero. All the encodings are in level-one, i.e. multiplied by $z^{-1}$ (inverse modulo $x_0$).

However, this is irrelevant for the attack because the definition of the orthogonal lattice is:

$$L=\{ \mathbf{u} \in \mathbb{Z}_{x_0}^t : \mathbf{u} \cdot \mathbf{x} = 0 \mod x_0 \}$$

Thus, considering encodings at level-one means that we have $\mathbf{x} \cdot z^{-1}$ instead of $\mathbf{x}$. Therefore, we are actually constructing the following lattice:

$$L'=\{ \mathbf{u} \in \mathbb{Z}_{x_0}^t : \mathbf{u} \cdot \mathbf{x} \cdot z^{-1} = 0 \mod x_0 \}$$

But since $\mathbf{u} \cdot \mathbf{x} \cdot z^{-1} = 0 \mod x_0 \Leftrightarrow \mathbf{u} \cdot \mathbf{x} = 0 \mod x_0$, it holds that $L = L'$.

Hence, having $t$ encodings at level-zero or $t$ encodings at level-one is equivalent in this attack.