Seen here, at the bottom of page 5, $\operatorname{Flatten}(\vec{a})$ is defined as:


For an n-dimensional vector $\vec{a} = (a_{1,0},\ldots,a_{1,l}, \ldots, a_{k,0},\ldots,a_{k,l-1})$. Where $a_{i,j}$ is the $j$-th bit in $a_i$'s bit representation.

But if we're computing the function through its own inverse, would this not just result in the original vector a?


1 Answer 1


When all the entries of $a$ are binaries, then yes, $Flatten(a) = a$, because $BitDecomp^{-1}(a)$ will give a $k$-dimensional vector whose entries are decomposed back to $\ell$ consecutive entries of $a$ (by $BitDecomp$).

However, when $a$ has non-binaries entries, this is not the case.

For instance, for $\ell = 3$ and $k = 2$, we would have $N = 6$. Then, consider $a = (0, 3, 0, 0, 0, 1)$.

Then, $BitDecomp^{-1}(a) = (3\cdot 2, 1\cdot 4) = (6, 4)$, and $BitDecomp(6, 4) = (0, 1, 1, 0, 0, 1)$.

Notice that for the last block of $a$ (last $\ell$ entries), $Flatten$ worked as the identity, because this block was binary.

  • $\begingroup$ Thank you for your response. Would this still hold, when the entries are non-binary, if $\sum a_{1,j}> 7$, therefore couldn't be represented in $l$-bits? For example, if $a=(5,3,1,0,0,1)$ and the values of $l,k$ remain, would $Flatten(a)$ still be valid? $\endgroup$
    – Stilton
    Apr 3, 2019 at 14:56
  • $\begingroup$ @Stilton yes, it would work modulo $q$. Actually, you perform the operations modulo $q$ and $\ell = \lceil \log q \rceil$, thus, all the produced values can be represented with $\ell$ bits. $\endgroup$ Feb 7, 2020 at 7:34
  • $\begingroup$ For clarity, you might note that bits ordered least significant to most significant. $\endgroup$
    – kelalaka
    Feb 7, 2020 at 7:57

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.