Leo Ducas and Daniele Micciancio's recent paper "FHE Bootstrapping in less than a second" gave an exciting result that one can compute the `atom operation' of Fully Homomorphic Encryption (i.e. NAND-and-Recrypt) within 1 second without loss of security. I am trying to figure out how their scheme works.

However the key technique of their bootstrapping scheme, 'Homomorphic Accumulator', uses some decomposition algorithms that may be common and trivial in the area of mathematics but I have no idea about them.

Concretely, on page 10, the Algorithm 1 states:

(For each $i$) compute the base-$B_r$ representation of $-a_i = \sum_j B_r^j \cdot a_{i,j}$ ($\mod q$)

where $j$, $B_r$ are small integers and each $a_i$ is a component of vector $\boldsymbol{a}$.

Similarly, on the next page,

On input the current accumulator content $ACC \in R^{2d_g \times 2}$... first computes the base-$B_g$ decomposition of $u^{-1}ACC = \sum_{i=1}^{d_g} B_g^{i-1} \boldsymbol{D}_i$ (where each $\boldsymbol{D}_i \in R^{2d_g \times 2} $ has entries with coefficients in $\{ \frac{1-B_g}{2}, \dots, \frac{B_g-1}{2} \}$...

My question is, how to perform these decompositions?

  • 3
    $\begingroup$ Are you really asking for an algorithm to represent an integer $x$ in base $b$? That's standard stuff. Have I misunderstood your question? $\endgroup$ – D.W. Oct 13 '14 at 9:13
  • $\begingroup$ I overthought the problem, D.W. you have pointed out what I once wondered. Thank you. Indeed, it is just a simple numeral system conversion. $\endgroup$ – phan Oct 14 '14 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.