Homomorphic Encryption and the Approximate GCD Problem Confusion

Question

Note: I asked this question on Math.StackExchange yesterday and it wasn't answered, so I thought I would repost it here, in hope of getting an answer

---

I am reading Homomorphic Encryption and the Approximate GCD Problem, specifically Section 3.2 on page 23, which outlines a basic encryption scheme:

The user chooses a large odd integer $p$ to be the secret key for the system.

A plaintext is a single bit $m$. To encrypt a message $m\in\{0,1\}$ and obtain a ciphertext $c$, the user chooses $q,e \in\mathbb{Z}$ independently and randomly from some distribution for each encryption and computes $$E(m,p) =qp+ 2e+m$$

The binary size of $q$ is generally chosen to be greater than the binary size of $p$. The binary size of $e$, which is referred to as the error, is much smaller than the binary size of $p$. We will discuss the exact sizes for these parameters later on.

The decryption function for this system is given by $$D(c,p) = (c\mod p)\mod 2$$

To see that the decryption function is correct for a ciphertext $c=qp+ 2e+m$, observe that \begin{align}D(c,p) &= (qp+ 2e+m\mod p)\mod 2 \\&= (2e+m)\mod 2\\ &=m \end{align}

Note that for this to work we need \begin{align}2|e|+ 1&<\frac p2\\|e|&<\frac p4−\frac 12\end{align} so that $(2e+m\mod p) = 2e+m$.

However, what I am struggling with is, if we choose $e<0$ then \begin{align}2e+m\mod p &= (p-2|e|)+m\\&\neq2e+m\end{align} by the definition of modulo (at least as seen by most common programming languages):

$a\mod b=r$ where $a=qb+r$ and $0\leq r<b$

Since $p$ is specified to be odd, then we have \begin{align}&((p-2|e|)+m)\mod 2 \\ &=((p\mod2)-((2|e|)\mod 2))+(m\mod 2)\mod 2\\ &= ((1-0)+m)\mod2\tag{as $p$ is odd}\\ &= (1+m)\mod 2\tag{as $m$ is either $1$ or $0$}\\ &\neq m\end{align}

I'm just trying to understand why we specify $$|e|<\frac p4 - \frac 12$$ and not $$0<e<\frac p4 - \frac 12$$

as, as far as I understand, the decryption doesn't work when \begin{align}0<-e&<\frac p4 - \frac 12\\ \frac 12 - \frac p4 < e &< 0 \end{align}

Example

Choose $p=1583$, $q=52498$, then $|e|<\frac{1583}{4}-\frac 12 = 395.25$ so choose $e=-241$

For $m=1$, we have \begin{align}c&=52498\times 1583+2\times (-241)+1\\ &= 83104334-482+1\\ &= 83103853\end{align}

We decrypt this as follows \begin{align}D(c,p)&=(c\mod p)\mod 2\\ &= (83103853\mod 1583) \mod 2\\ &= 1102 \mod 2\\ &= 0\\ &\neq m=1\end{align}

We can see that \begin{align}(c\mod p) &= 1102\\ &= (2\times 550.5) + 1\end{align} and $550.5 > 395.25$ which doesn't satisfy the constraint on $|e|$

---

Can someone either confirm that my logic is correct, or explain to me where it is falling apart please.

Answer 1

The reference linked states in its Notation section (page vii):

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

Thus the definition of $\bmod$ used is the non-standard $$(a\bmod p)=r\;\iff\;p\text{ divides }a-r\;\text{ and }\;-p<2r\le p$$

This can be viewed as the offset of $a$ from the nearest multiple of $p$ (with nearest selecting the lower as a tie-breaker), as suggested by a comment.

This can be programmed as r = ((a + (p-1)/2) % p) - (p-1)/2, making sure that

• things are evaluated as signed integers (which in C can require some explicit casting for unsigned p);
• the addition of (p-1)/2 does not cause overflow.