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?

  • $\begingroup$ 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"? $\endgroup$
    – DrLecter
    Nov 4 '13 at 17:07
  • $\begingroup$ Yes I meant if there are any technical reasons why the message -1 is not allowed. Thanks for clarifying it. $\endgroup$
    – user9189
    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.

  • $\begingroup$ 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. $\endgroup$
    – K.G.
    Nov 6 '13 at 8:21
  • $\begingroup$ 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. ;) $\endgroup$
    – DrLecter
    Nov 6 '13 at 11:06
  • $\begingroup$ 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. $\endgroup$
    – K.G.
    Nov 6 '13 at 13:29
  • $\begingroup$ @K.G. ahh, now I see what you targeted on. ok, thx that makes sense! $\endgroup$
    – DrLecter
    Nov 6 '13 at 13:42

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.