Question Regarding Idenitities of Gentry's Homomorphic Encryption on LWE

Question

In the paper Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based Gentry introduces the following identity $\mathbf{a} \in \mathbb Z^n,\mathbf{b} \in \mathbb Z_q^n$

$$\langle \mathbf{a}, \text{PowersOfTwo}(\mathbf{b})\rangle =\langle \text{BitDecomp}^{-1}(\mathbf{a}), \mathbf{b}\rangle = \langle \text{Flatten}(\mathbf{a}), \text{PowersOfTwo}(\mathbf{b})\rangle$$

The given functions are defined as follows using Brakerski (2012) complementary

Let $l = \lfloor \log_{2} q \rfloor +1$

1. PowersOfTwo Let $\mathbf{b} \in \mathbb{Z}_{q}^n$ and $l \in \mathbb{Z}$, then $$\text{PowersOfTwo}(\mathbf{b}):=\Big(\mathbf{b}, 2 \cdot \mathbf{b}, \dots, 2^{l-1}\cdot \mathbf{b}\Big)$$

2. BitDecomp For $\mathbf{a} \in \mathbb{Z}^n$ let $\mathbf{w}_{i}\in\{ 0,1 \}^n$ such that $$\mathbf{a}= \sum_{i=0}^{l-1} 2^i \cdot \mathbf{w}_{i} \;\;(\text{mod } q)$$ and outputting the determined coefficients $\mathbf{w}_{i}$ with $0 \leq i \leq l-1$ $$\text{BitDecomp}(\mathbf{a}) := (\mathbf{w}_{0}, \dots, \mathbf{w}_{l-1})$$

3. Flatten
   Let $\mathbf{b} \in \mathbb{Z}^n$, then $$\text{Flatten}(\mathbf{b}):= \text{BitDecomp}\Big(\text{BitDecomp}^{-1}(\mathbf{b})\Big)$$

Using information from this math.stackexchange answer on the extension of the codomain of BitDecomp on $\mathbf w_i \in \mathbb Z^n$, I try to see how these identities hold. So far I got the following

$$\begin{alignat}{2} \left\langle \mathbf{a}\,,\, \text{PowersOfTwo}(\mathbf{b}) \right\rangle &= \sum_{i=0}^{n-1} a_{i} \cdot 2^{i} b_{i} &&\;\;(\text{mod } q) \\ &= \sum_{i=0}^{n-1} 2^ia_{i} \cdot b_{i} &&\;\;(\text{mod } q) \\ &= \left\langle \text{BitDecomp}^{-1}(\mathbf{a})\,,\, \mathbf{b}\right\rangle &&\;\;(\text{mod } q) \end{alignat}$$

Now somehow the $a_i$ must be reduced by the binary transformation, but I don't see how to justify this mathematically. I would be greatful for a bump into the right direction. More specifically, how to finish this proof to get the second part of the identity?

Answer 1

Assuming that $a \in \mathbb{Z}^{n \cdot \ell}$ and $b \in \mathbb{Z}_q^{n}$ where $a = (a_{1,0}, \dots, a_{1, \ell-1}, \dots, a_{n, 0}, \dots, a_{n, \ell-1})$ and $b = (b_1, \dots, b_n)$. Then using the definitions provided in Gentry's paper,

• $\mathsf{Powersof2}(b) = (b_1, 2b_1, \dots, 2^{\ell-1}b_1, \dots, b_n, 2b_n, \dots, 2^{\ell-1}b_n)$
• $\mathsf{BitDecomp}(b) = (b_{1,0}, \dots, b_{1, \ell - 1}, \dots, b_{n,0}, \dots, b_{n,\ell-1})$ where $b_{i,j}$ is the $j$-th bit in $b_i$'s binary representation.
• $\mathsf{BitDecomp}^{-1}(a) = (\sum 2^j \cdot a_{1,j}, \dots, \sum 2^{j} a_{n, j})$.
• $\mathsf{Flatten}(a) = \mathsf{BitDecomp}(\mathsf{BitDecomp}^{-1}(a) \bmod{q}) \in \{0,1\}^{n \cdot \ell}$.

An interesting point to note is that $\mathsf{Flatten}$ gives a vector with entries either 0 or 1. Another interesting point is $<\mathsf{BitDecomp}(c), \mathsf{Powersof2}(b)> = <c,b> \bmod{q}$ where $c \in \mathbb{Z}_q^n$. This immediately gives us

$$ \begin{align*} <\mathsf{BitDecomp^{-1}}(a), b> &= <\mathsf{BitDecomp^{-1}}(a) \bmod{q}, b> \bmod{q}\\ &=<\mathsf{BitDecomp} (\mathsf{BitDecomp^{-1}}(a) \bmod{q}), \mathsf{Powersof2}(b)> \bmod{q}\\ &= <\mathsf{Flatten}(a), \mathsf{Powersof2}(b) > \bmod{q} \end{align*} $$