1

I was wondering if someone could explain the Digit Extraction from HElib in simple words:

Apply a homomorphic (non-linear) digit-extraction procedure, computing $r$ ciphertexts that contain the digits $e − e′ + r − 1$ through $e − e′$ of the integers in the slots, respectively, relative to plaintext space mod-$p^r$. This requires that we generalize the bit-extraction procedure from [21] to a digit-extraction procedure for any prime power $p^r \ge 2$, this is done in Section 5.3. Once we extracted all these digits, we can combine them to get an encryption of the coefficients of $m$ in the slots relative to plaintext space modulo $p^r$.

Maarten Bodewes
  • 92,551
  • 13
  • 161
  • 313
kindi
  • 11
  • 2
  • I've added the relevant section to the question. Please point out what you don't understand from it, as others may find that a reasonable explanation. – Maarten Bodewes Jan 25 '24 at 15:18
  • @MaartenBodewes Op simply doesn't want to read the referred article that the quote only mention it. – kelalaka Jan 25 '24 at 16:34
  • I don't make those kind of assumptions, but as it is the question will probably be closed as "too broad". – Maarten Bodewes Jan 25 '24 at 17:06
  • @MaartenBodewes, Thank you for the precise answer and for allowing me to narrow down my question. I will come back with more intelligent question if this question survives :-) – kindi Jan 25 '24 at 18:31
  • @kelalaka, I have gone through so many articles/codes/other-materials to understand the tricks behind bootstrapping. Probably I might not have proper mathematical background to understand it. I will keep trying regardless of my inefficacy and online bullying. There always exists some altruist people (like @MaarteenBodewes) to help others. – kindi Jan 25 '24 at 18:50
  • https://crypto.stackexchange.com/questions/42666/what-exactly-is-bootstrapping-in-fhe?rq=1 – kelalaka Jan 25 '24 at 19:04
  • kelalaka is not such a bully as you can see from them pointing out the extra information :) There is no need to post another question, you can just [edit] this one and indicate where you're stuck. – Maarten Bodewes Jan 25 '24 at 19:32
  • @MaartenBodewes, Thanks sir. I will take a closer look and come up with some more prudent questions. Thanks for the privileges :-) This time, I will edit the question. – kindi Jan 26 '24 at 02:22
  • The lemma 1 in GHS11 states that: Let $q = 2^r + 1$ for a positive integer $r$, and let $z$ be a non-negative integer smaller than $\frac{q^2}{2} - q$, such that $[z]_q$ is also negative, $[z]_q \in [0, \frac{q}{2}]$. Then $[[z]_q]_2 = z \langle r \rangle \oplus z \langle 0 \rangle$.

    Does it mean, consider those $z$ for which $[z]_q$ is non-negative?

    Or, does it mean, if $0 \leq z < (\frac{q^2}{2} - q)$ then $[z]_q \in [0, \frac{q}{2}]$?

    Keep in mind that, $[\cdot]_q$ maps an integer in-between $(\frac{-q}{2}, \frac{q}{2}]$.

     – kindi Feb 10 '24 at 00:25

0 Answers0