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$?


1 Answer 1


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$).

  • $\begingroup$ Okay, this makes much more sense than what I had in mind. Thank for the other link as well! $\endgroup$
    – sycs
    Commented Aug 17, 2016 at 0:11

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.