# Proving that $\operatorname{parity}(c) = \operatorname{loc}(c \cdot \operatorname{Enc}(2^{-1}))$

I am studying the Goldwasser, Micali, Tong theorem about information leakage in RSA. In every book I have searched, there is the following remark $$(c = \operatorname{Enc}(x))$$:

Note that $$\operatorname{loc}(c) = \operatorname{parity}(c \cdot \operatorname{Enc}(2))$$ and $$\operatorname{parity}(c) = \operatorname{loc}(c \cdot \operatorname{Enc}(2^{-1}))$$

with \begin{align} \operatorname{loc}(x^e\bmod n)&=\begin{cases} 0,&x\le n/2\\ 1,&x>n/2 \end{cases}\\ \\ \operatorname{parity}(x^e\bmod n)&=\begin{cases} 0,&x\bmod 2=0\\ 1,&x\bmod 2=1 \end{cases}\end{align}

I have proven the first, but I am having trouble proving the second. I cannot understand how $$\operatorname{loc}(c \cdot \operatorname{Enc}(2^{-1}))$$ could be equal to $$1$$, as this would mean that $$x/2 > n/2$$ and as a result $$x$$ would be greater than $$n$$, while being an element of $$\mathbb{Z}_n$$. Am I missing something?

• Consider unrolling the definition of $loc(c \cdot Enc(2^{-1}))$. Jan 11 at 20:59
• I have, but I get stuck on how to handle the fact that $x$ is greater than $n$. It should not be possible, should it? Jan 11 at 21:03
• So what expression do you actually get after unrolling? Also, I believe it's safe to assume that whatever $x$ is underneath $c$ is less than $n$ before RSA encryption was performed. Jan 11 at 21:08
• if $loc(c \cdot Enc(2^{-1})) = loc(Enc(x/2)) = 1$, then the unrolled expression is $x/2 > n/2$, which means that $x>n$. But as we said before, this cannot be the case. Jan 11 at 21:13
• What I was getting at is that now, that you have established the first result. You can then use that together with your last comment to also establish the second result. Obviously, you may still want to establish the result directly instead. Jan 11 at 21:23

The issue encountered in the question is that it assimilates $$x\cdot 2^{-1}$$ to $$x/2$$, which does not hold e.g. for $$x=1$$. Problem is that $$x\cdot 2^{-1}$$ is an element of $$\mathbb Z_n$$, but $$1/2$$ is not for the definition of operator $$/$$ used in the question. We need to be careful with what the notations used exactly mean.

In the question and this answer, operators with two integer operands $$+$$, $$-$$, $$\times$$ are integer addition, subtraction, multiplication; $$/$$ is division with $$a/b$$ a rational when $$a$$ is an integer and $$b$$ a non-zero integer. For integer $$a$$ and strictly positive integer $$n$$, the expression $$a\bmod n$$ with no parenthesis immediately on the left of $$\bmod$$ stands for the uniquely defined integer $$r$$ with $$0\le r and $$a-r$$ a multiple of $$n$$.

We regard the ring $$\mathbb Z_n$$ in the question as the set of integers in $$[0,n)$$. When $$a,b\in\mathbb Z_n$$, the notation $$a\cdot b$$ designates the integer $$a\times b\bmod n$$, which belongs to $$\mathbb Z_n$$.

In RSA, $$n$$ is odd, and for $$x$$ an integer in $$[0,n)$$ it holds $$\operatorname{Enc}(x)=x^e\bmod n$$. The result is an integer in $$[0,n)$$ and does not depend on if the multiplication of the $$e$$ terms in $$x^e$$ is made in the ring $$\mathbb Z$$ or the ring $$\mathbb Z_n$$.

In the expression $$\operatorname{Enc}(2^{-1})$$, the notation $$2^{-1}$$ designates $$u\in\mathbb Z_n$$ with $$2\cdot u=1$$, that is $$2\times u\bmod n=1$$. We thus have $$2^{-1}=u=(n+1)/2$$. Therefore \begin{align}\operatorname{loc}\left(c\cdot\operatorname{Enc}(2^{-1})\right)&=\operatorname{loc}\left(c\times\operatorname{Enc}(u)\bmod n\right)\\ &=\operatorname{loc}\left((x^e\bmod n)\times(u^e\bmod n)\bmod n\right)\\ &=\operatorname{loc}\left(\left(x\times u\right)^e\bmod n\right)\\ &=\begin{cases} 0,&(x\times u\bmod n)\le n/2\\ 1,&(x\times u\bmod n)>n/2 \end{cases}\\ &=\begin{cases} 0,&(x\times(n+1)/2\bmod n)\le n/2\\ 1,&(x\times(n+1)/2\bmod n)>n/2 \end{cases}\end{align}

If $$\operatorname{parity}(x^e\bmod n)=0$$, that is if $$x$$ regarded as an integer in $$[0,n)$$ is even, then $$x=2\times y$$ for some integer $$y\in[0,n/2)$$, thus \begin{align}x\times(n+1)/2\bmod n&=(2\times y)\times(n+1)/2\bmod n\\ &=y\times(n+1)\bmod n\\ &=y\bmod n\\ &=y\\ &\le n/2 \end{align} thus $$\operatorname{loc}\left(c\times\operatorname{Enc}(2^{-1})\right)=0$$.

If $$\operatorname{parity}(x^e\bmod n)=1$$, that is if $$x$$ regarded as an integer in $$[0,n)$$ is odd, then $$x=2\times y+1$$ for some integer $$y\in[0,n/2)$$, thus \begin{align}x\times(n+1)/2\bmod n&=(2\times y+1)\times(n+1)/2\bmod n\\ &=(2\times y+n+1)\times(n+1)/2\bmod n\\ &=2\times(y+(n+1)/2)\times(n+1)/2\bmod n\\ &=(y+(n+1)/2)\times(n+1)\bmod n\\ &=y+(n+1)/2\bmod n\\ &=y+(n+1)/2\\ &>n/2\end{align} thus $$\operatorname{loc}\left(c \cdot \operatorname{Enc}(2^{-1})\right)=1$$.

Hence $$\operatorname{parity}(c)=\operatorname{loc}(c \cdot \operatorname{Enc}(2^{-1}))$$.

• Excellent response. I don't know how or why I got so confused over $2^{-1}$, but thanks a lot for the clarifications. I have accepted your answer. It was really helpful, as always! Jan 14 at 20:44