Why doesn't FHE scheme see a modulus space $\Bbb Z_p$ as $[0,p)$ ? Instead, it consider $\Bbb Z_p$ as $\left[-\frac{p}{2},\frac{p}{2}\right)$.

What's the concrete reason? What happens if I use $[0,p)$?


The notation

Many works on FHE use a function of $a$ and $p$ giving how far above or below the nearest multiple of $p$ the quantity $a$ is. Craig Gentry and Shai Halevi note that quantity as $[a]_p$ in Implementing Gentry's Fully-Homomorphic Encryption Scheme (extended abstract in proceedings of Eurocrypt 2011). It replaces $((a+\lfloor p/2\rfloor)\bmod p)-\lfloor p/2\rfloor$. This $[a]_p$ belongs to $[−p/2,p/2)$.

Nathanael Black in Homomorphic Encryption and the Approximate GCD Problem (page vii) go as far as using $a\bmod p$ rather than $[a]_p$:

$a\bmod p\;\;$ Denotes reducing $a$ modulo $p$ into the interval $(-p/2, p/2]$

which is equivalent to $$(a\bmod p)=r\;\iff\;p\text{ divides }a-r\;\text{ and }\;r\in(-p/2, p/2]$$ (the difference in interval boundaries is immaterial for odd $p$).

Alternatively, that variant $[a]_p$ of $a\bmod p$ could be defined as $a-p\cdot\lceil a/p\rfloor$, where $\lceil x\rfloor$ denotes rational $x$ rounded to the nearest integer (rounding up for Gentry et al.). This is similar to the standard $a\bmod p\;=\;a-p\cdot\lfloor a/p\rfloor$.

For both the standard and alternate definitions of operator $\bmod$, it holds that: $$\begin{align} ((a+b)\bmod p)&=(((a\bmod p)+b)\bmod p)\\ &=(((a\bmod p)+(b\bmod p))\bmod p)\\ \end{align}$$ $$\begin{align} ((a\cdot b)\bmod p)&=(((a\bmod p)\cdot b)\bmod p)\\ &=(((a\bmod p)\cdot(b\bmod p))\bmod p)\\ \end{align}$$ $$\begin{align} (a\bmod p)&\equiv a&\pmod p\\ ((a+b)\bmod p)&\equiv a+b&\pmod p\\ ((a\cdot b)\bmod p)&\equiv a\cdot b&\pmod p\\ \end{align}$$ Note: In the above the notation $r\equiv a\pmod p$ means that $p$ divides $a-r$, and needs no adaptation. It is recognizable from operator $\bmod$ by the use of an opening parenthesis immediately on the left of $\bmod$, and (sometime: or) the use of an $\equiv$ sign somewhere on the left of and paired with $\bmod$.

Why it is useful

With the alternate definition $[a]_p$ of $a\bmod p$ comes an additional useful property, that does not hold for the standard $\bmod$: when $p$ is odd, for all $a$, it holds that $[-a]_p=-[a]_p$. That also holds for large even $p$ and most $a$.

The concept allows an easy extension to signed numbers and subtraction of one of the simplest (partially) homomorphic encryption system: Paillier's encryption. All it takes is defining a modified decryption as $D'(c)=[D(c)]_n$ and restriction of plaintext range; see this.

In some FHE systems, $[a]_p$ matches a signed noise term algebraically added to a signal aligned to multiples of $p$, and $a-[a]_p$ is the pristine signal recovered from the noisy $a$, minimizing the absolute value of noise $[a]_p$.

  • $\begingroup$ Hi! Thank you for giving me your insight. The "mod" operation is taken by considering (−p/2,p/2] rather than [0,p-1] among many papers. $\endgroup$
    – mallea
    May 3 '18 at 18:27
  • $\begingroup$ One exanmple is eprint.iacr.org/2012/099 page 3. $\endgroup$
    – mallea
    May 3 '18 at 18:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.