Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a vector of polynomial in $R_q^n$, in particular, how the $u_j$'s are in $R_2^n$.
Does it assume that the polynomial is in coefficient representation? Can someone please give an example for $n=1$, and $n=2$?
To understand that, we have to understand how it works for a single polynomial (which means, for $n = 1$).
First of all, think about the binary decomposition of an integer value: given $m \in \mathbb Z_q$, it is always possible to write $m = \sum_{i=0}^{\log q} b_i 2^i$, with each $b_i$ in $\{0, 1\}$.
Now, just see that if you decompose each coefficient $a_i$ of a polynomial into the binary representation $\sum_{j=0}^{\log q} b_{j,i} 2^j$ , you get $\log q$ polynomials:
$\begin{align} p(x) &= a_dx^d + a_{d-1}x^d_{d-1} + ... + a_1x + a_0\\ &= \left( \sum_{j=0}^{\log q} b_{j,d} 2^j \right)x^d + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j \right)x^{d-1} + ... + \left( \sum_{j=0}^{\log q} b_{j,1} 2^j \right)x^1 + \sum_{j=0}^{\log q} b_{j,0} 2^j\\ &= \left( \sum_{j=0}^{\log q} b_{j,d} 2^jx^d \right) + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j x^{d-1} \right) + ... + \left( \sum_{j=0}^{\log q} b_{j,1} 2^jx^1 \right) + \sum_{j=0}^{\log q} b_{j,0} 2^j\\ &= \sum_{j=0}^{\log q} \left(b_{j,d} 2^j x^d + b_{j,d-1} 2^j x^{d-1} + ... + b_{j,1} 2^j x^1 + b_{j,0} 2^j \right) \\ &= \sum_{j=0}^{\log q} \left(b_{j,d} x^d + b_{j,d-1} x^{d-1} + ... + b_{j,1} x^1 + b_{j,0} \right) 2^j \\ &= \sum_{j=0}^{\log q} u_j(x)2^j \end{align}$
Therefore, what this BitDecomp function does when it receives a single polynomial is to return a vector with those $\log q$ polynomials $u_j$.
Thus, when given a vector with $n$ polynomials, it returns a vector with $n \cdot \log q$ polynomials.
Maybe this answer will be useful to you, since it is very related to your question ($Dec_{w,q}$ is a generalization of BitDecomp that uses a parameter $w$ to the base instead of fixing the value $2$).
