# How does Flatten really make the coefficients of a vector matrix small in LWE

In Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based, Gentry et. al defined Flattening as follows;

Let $$\vec{a},\vec{b}$$ be vectors of some dimention $$k$$ over $$\mathbb{Z}_q$$. Let $$\ell = \lfloor \log_2q \rfloor +1$$ and $$N = k \cdot \ell$$

Define $$\operatorname{BitDecomp}(\vec{a})$$ be the $$N$$-dimentional vector $$= (a_{1,0},\ldots,a_{1,\ell-1} \ldots,a_{k,0},\ldots,a_{k,\ell-1})$$, where $$a_{i,j}$$ is the $$j$$-th bit in the $$a_i$$'s binary representation, bit ordered least significant to most significant.

For $$\vec{a}' = (a_{1,0},\ldots,a_{1,\ell-1}, \ldots,a_{k,0},\ldots,a_{k,\ell-1})$$, let $$\operatorname{BitDecomp}^{-1}(\vec{a}) = (\sum 2^j\cdot a_{1,j}, \ldots, \sum 2^j\cdot a_{k,j})$$ be the inverse of $$\operatorname{BitDecomp}$$, but well defined when the input is not a $$0/1$$ vector.

This is nothing but usual decomposition into bits and the data has already stored in the decomposed way.

For $$N$$-dimensional vector $$\vec{a}'$$, let $$\operatorname{Flatten}(\vec{a}') = \operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1} (\vec{a}'))$$.

When $$A$$ is a matrix, let $$\operatorname{BitDecomp}(A), \operatorname{BitDecomp}^-1(A)$$, or $$\operatorname{Flatten}(A)$$ be matrix formed by applying the operation to each row of $$A$$ seperately.

An interesting feature of $$\operatorname{Flatten}$$ is that it makes the coefficients of a vector matrix $$small$$ without affecting its product with $$\operatorname{Powersof2}(\vec{b})$$, and without knowing of $$\vec{b}'$$

It is not clear for me how the $$\operatorname{Flatten}$$ makes the coefficients of a vector matrix $$\boldsymbol{small}$$. What I see that the two operations, $$\operatorname{BitDecomp}$$ and $$\operatorname{BitDecomp}$$, are just the inverse of each other. Could someone elaborate on what I'm missing here?

## 1 Answer

The important part you missed is the last sentence of the first block:

$$BitDecdomp^{-1}$$ is still well-defined, if it doesn't get a $$N$$-dimensional bit vector (all entries from $$\{0,1\}$$).

In the second quote, $$Flatten$$ is defined as first using $$BitDecdomp^{-1}$$, and then use $$BitDecomp$$. So the output of $$Flatten$$ will be a bit-vector. This will be the same as the input only if that input was also a vector from $$\{0,1\}$$ - but it is defined for any vector over $$\mathbb{Z}_q$$.

The basic idea here is to use a continuation from a smaller domain to a larger one.

• could you elaborate on the last part? as far as, I can see, the dimensions are still the same. – kelalaka Feb 7 '20 at 8:37
• @kelalaka The dimensions are not different. The difference in the domain / range is on one hand $\mathbb{Z}_q^d$ and on the other hand $\mathbb{Z}_2^d$. – tylo Feb 7 '20 at 10:12