Lattice attacks against Multilinear Maps [CLT13]

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?

• Dragos, in case you want a full answer to this question: I recommend emailing one (or all) of the CLT13 authors with this type of question. (Otherwise, the answer will be incomplete.) They are likely to be responsive. – Daniel Apon Apr 16 '17 at 17:45
• (Proposition: Everyone except those three people will only be able to give you partial information, including me.) – Daniel Apon Apr 16 '17 at 17:46

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.

• Ah, I see now! I don't know why I said Gaussian Elimination for point 1), one has to use LLL. As for point 2) it makes sense, probably what confused me is that the authors applied the attack for level 0 encodings, the reduction step from any level was not that straightforward to me... – Dragos Apr 2 '19 at 20:07
• @Dragos in fact, I agree that it is not clear. In my opinion, the authors should have put at least a little sentence addressing the fact that the lattice is the same regardless the level of the encodings... – Hilder Vitor Lima Pereira Apr 2 '19 at 21:17