6
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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.
$\endgroup$
7
  • 1
    $\begingroup$ Thank you, I'll give it a try. It just seems counterproductive that a concept which will inevitably need to be programmed uses a definition of $\mod{}$ which is non-standard in all major languages $\endgroup$
    – lioness99a
    Mar 22, 2017 at 14:29
  • 1
    $\begingroup$ The "mod p" part in this case should not be thought of as a standard modulo (remainder when divided by p), but rather as the distance to the nearest multiple of p. $\endgroup$
    – K.G.
    Mar 23, 2017 at 8:30
  • $\begingroup$ @K.G.: +1 for nearest multiple of $p$. But distance is non-negative, when the result of that $\bmod$ can be negative. $\endgroup$
    – fgrieu
    Mar 23, 2017 at 8:49
  • $\begingroup$ Thanks for the edit, somehow I'd missed that definition in the notation section... Makes a whole lot more sense now! (and for reference, I'm currently playing around with writing a proof-of-concept in Python) $\endgroup$
    – lioness99a
    Mar 23, 2017 at 9:03
  • $\begingroup$ @fgrieu Offset is good. $\endgroup$
    – K.G.
    Mar 23, 2017 at 19:39

Your Answer

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

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