# Why is $-1$ an illegal message in the Goldwasser-Micali Encryption Scheme

I'm not sure why in the Goldwasser-Micali encryption scheme with a Blum integer $N$, the message $-1$ is always a illegal message.

Can you give me some direction for starting?

What is illegal message's meaning?

• I assume you refer to the Goldwasser-Micali (GM) encryption scheme. The GM scheme has an associated message space $M=\{0,1\}$, i.e. you encrypt bits. So by definition $-1$ is not in the message space. Where did you read "illegal message"? Is your question "Are there any technical reasons why the message -1 is not allowed"? Nov 4 '13 at 17:07
• Yes I meant if there are any technical reasons why the message -1 is not allowed. Thanks for clarifying it. Nov 4 '13 at 22:17

I'm going to use the notation from here.

I'm still not sure why one wants to handle $-1$ as a message, but anyways. Simple solution is that you simply define: if message is $-1$ set message to $1$ and the other way round when decrypting. Second point is that you can only encrypt messages from a message space with two elements (independent from how you name them).

Ok, but maybe this is the question/answer:

Basically the idea is that you encrypt a message bit by bit and the security of the encryption scheme relies on the quadratic residuosity problem.

That is, it is hard to distinguish between quadratic residues modulo $n=pq$ for primes $p$ and $q$ (the set is denoted as $QR_n$) and pseudo-squares modulo $n$. Thereby, a pseudo-square $x$ modulo $n$ is an element with Jacobi symbol $\left( \frac{x}{n} \right)=1$. This means that from the Jacobi symbol it looks like a quadratic residue, but actually it belongs to the set of quadratic non-residues ($QNR_n$), i.e., it is a quadratic non-residue modulo $p$ as well as modulo $q$, giving $\left( \frac{x}{n} \right)=\left( \frac{x}{p} \right)\cdot \left( \frac{x}{q} \right)=(-1)\cdot(-1)=1$.

However, without knowing the factorization of $n$, i.e., $p$ and $q$, which would allow us to compute the Legendre symbols $\left( \frac{x}{p} \right)$ and $\left( \frac{x}{q} \right)$, we cannot decide whether $x$ is a square or a pseudo-square.

Now, such a pseudo square $x$ and $n$ is the public key and the factorization $p,q$ is the private key. Taking $n$ as Blum integer has the reason that you can efficiently find such an $x$ (i.e., set $x=N-1$).

Encrypting amounts to chosing a random square $y^2$ for $y$ random from $Z_n^*$ and for message $m\in\{0,1\}$ we compute $c=y^2x^m \pmod n$. This means

• if $m=1$: $c=y^2x \pmod n$ (gives a non-square, but with Jacobi symbol 1)
• if $m=0$: $c=y^2 \pmod n$ (gives a square)

Now, by the quadratic residuosity assumption, without knowing $p$ and $q$ given the public key and $c$, one cannot decide whether $c$ contains an encryption of $1$ or $0$.

Decrypting is simply deciding whether $c$ is in $QR_n$ (giving $m=0$) or in $QNR_n$ (giving $m=1$).

Your question is now: what if we use message space $M=\{0,-1\}$? When taking $m=-1$, we would have $c=y^2x^{-1}$, i.e., we can interpret this as using the inverse $x^{-1}$ of $x$ modulo $n$. The question is: Would this also be a pseudo-square?

Now, we know that $x\cdot x^{-1} \equiv 1 \pmod n$ and we know that the $\left( \frac{1}{n} \right)=1$ ($1$ is in $QR_n$) and we know that for $a\equiv b \pmod n$ we have that $\left( \frac{a}{n} \right)=\left( \frac{b}{n} \right)$. This and the fact that the Jacobi symbol is multiplicative gives us that:

$\left( \frac{x\cdot x^{-1}}{n} \right)=\left( \frac{x}{n} \right)\cdot \left( \frac{x^{-1}}{n} \right)=1$. Now, we know the Jacobi symbol of $x$, which gives us

$1\cdot \left( \frac{x^{-1}}{n} \right)=1$. However, since $x$ is in $QNR_n$ and $1$ is in $QR_n$, $x^{-1}$ must be in $QNR_n$. Since it, however, must have a Jacobi symbol of $1$ is must be a pseudo-square.

So, yes, GM encryption would technically also work for $M=\{0,-1\}$ (but you could then give $x^{-1}$ instead of $x$ in the public key and work with $M=\{0,1\}$ again). I see no real reason why one should do that anyways (costs an extra inversion). Maybe there is an (obvious) security problem if you have $x$ in the public key and use $x^{-1}$ in the encryption, which I do not see at the moment.

• When you are using safe primes, you know that -1 is a quadratic non-residue. So regardless of what's in the public key, you can encrypt b as y^2(-1)^b. The ciphertexts will have the same distribution, regardless of whether you use -1, x or 1/x.
– K.G.
Nov 6 '13 at 8:21
• I agree that when you are working with Blum integers, -1 will always be a quadratic non-residue and will have Jacobi symbol 1. But the message space of GM is not $Z_n^*$ but $\{0,1\}$ and the question refered to whehter we can replace $-1$ with $1$ in the message space (maybe I did not interpret this correctly and maybe I also did not get your point @K.G. ;) Nov 6 '13 at 11:06
• It wasn't entirely clear, but my comment was directed at the final sentence in your answer. As for the question, I have no idea how to make sense of it.
– K.G.
Nov 6 '13 at 13:29
• @K.G. ahh, now I see what you targeted on. ok, thx that makes sense! Nov 6 '13 at 13:42