I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts I simply still find the paper too hard to read and digest. To my aid I have compared a pair of surveys on the topic, Marcolla et al from 2022, and Acar et al from 2017 (both of which reference the PhD dissertation but the paper accompanies it, I believe). However, both surveys define the encryption differently. Let me share their descriptions quickly.

2022 survey (section V.A)

Given a "good" basis vector of the lattice $B_{\mathrm{pk}}$ as public key, Marcolla describes the encryption process as converting a message $m$, $m \in {0,1}$ into a point as $ \boldsymbol{a} = m + 2\boldsymbol{e}$, where e is a small random vector in $\mathbb{R}^n$ (shouldn't it be $\mathbb{Z}^n$?) with coefficients taken randomly from $\{0, ±1\}$. Then ciphertext c is produced by translating a into parallelepiped $P(B_{\mathrm{pk}})$ through: $$ \boldsymbol c = \boldsymbol a − (⎡ \boldsymbol a B_{\mathrm{pk}}^{-1} ⎦ B_{\mathrm{pk}}) $$ where ⎡⎦ is rounding to nearest integer.

2017 survey (section 3.3.1)

This survey explains that the construction first utilizes ideals and rings then lattices, however, it is not clear to me if their description is also using lattices or not. For a message $\boldsymbol m \in {0,1}^n$, which here is a string of bits instead of just one bit as above, ciphertext is produced:

$$ \boldsymbol c = \boldsymbol m + \boldsymbol r \cdot B_I + \boldsymbol g \cdot B_J^{pk} $$

where $\boldsymbol r$ and $\boldsymbol g$ are random vectors, $B_I$ is the basis of the ideal $I$, but not the same as the public key basis vector $B_J^{pk}$. The first two terms are referred to as the "noise parameter".


So the noise expressions between the two are similar. $\boldsymbol m + \boldsymbol r \cdot B_I$ is similar to $ m + 2\boldsymbol e$ but I do not understand the connection between $B_I$ and $\boldsymbol e$. One is a random vector, one is the basis of the ideal.

Then how the noisy message vector is applied to obtain $\boldsymbol c$ also differs between the two definitions.

  1. How do the two definitions relate to one another? Are they equivalent somehow?
  2. Where exactly is this explained in Gentry's paper? 3.3 seems to be closer to 2022 surveys definition, and 3.1 seems to be closer to 2017's definition. It looks to me like it is spread out over multiple sections (section 4 and 5), and perhaps this is the case but it would be just as nice to get some confirmation of that :)

Sorry for the long and broad question, any help is very appreciated. I am ok with cryptographic concepts, but the math is a bit beyond me (especially working with ideals and lattices).

  • 1
    $\begingroup$ Welcome to Cryptography.SE. Your question is too broad. Could you limit it to one specific question? $\endgroup$
    – kelalaka
    Nov 21 at 15:06
  • $\begingroup$ Thank you, @kelalaka ! I was afraid that it would be, I have trimmed it down now. Let me know if this is better. $\endgroup$
    – Parham
    Nov 21 at 17:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.