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 1


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.

  • $\begingroup$ could you elaborate on the last part? as far as, I can see, the dimensions are still the same. $\endgroup$
    – kelalaka
    Feb 7, 2020 at 8:37
  • $\begingroup$ @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$. $\endgroup$
    – tylo
    Feb 7, 2020 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.