# What is the advantage of Pseudosquare?

Pseudosquares ,which are not square but Jacobi symbol are still 1, are used in some cryptographic algorithm. What is the advantage of them over the exact squares? If we used squares instead of pseudosquares, what would we lost? I think,factorization can be hard and so security is ensured. But I am not sure about certain reason

• "are used in some cryptographic algorithm" Which one? Apr 3 '16 at 21:30
• As far as I see, it was used in Goldwasser miccali cryptosystem for key generation @fkraiem Apr 3 '16 at 21:42
• That is one example, yes. If that's what the question is about, it should mention it. Apr 3 '16 at 21:48
• In the GM cryptosystem, the "advantage" of using a non-square is that if you use a square, the system doesn't work. Apr 3 '16 at 21:49

Your question is a bit broad for a completely detailed answer: pseudosquares is essentially a subgroup of $\mathbb{Z}_n$ (for an RSA modulus $n$) with particular properties, based on which a considerable number of cryptographic protocols have been designed. Nevertheless, having done some work on primitives that rely crucially on the properties of pseudosquares, I will try to give you an intuition of some aspects that I found important:
• Protocols involving sending a square are inherently more difficult to be made secure against malicious adversaries. This is because when dealing with malicious adversaries, you must ensure that they remain honest. However, given an element of $\mathbb{Z}_n$ with Jacobi symbol $1$, it is computationally infeasible to determine whether this number is a square or not (this is the quadratic residuosity assumption). Hence, to ensure that a player indeed send a square, you must rely on expensive zero-knowledge proofs to check it. If, however, your protocol can be directly built using pseudosquares instead of squares, you remove this burden: checking whether a number is a pseudosquare (ie computing the Jacobi symbol) can be done in polynomial time (even without the factorization).
• There is a very natural cryptosystem associated with the group of pseudosquares: to encrypt 0, send a random square, to encrypt $1$ send a random non-square pseudosquare. More formally, the public key is a non-square pseudosquare $y$, and encrypting a bit $b$ is done by computing $c = y^{2r+b}$ for a random integer $r$. With the factorization, one can recover $b$ by chechking whether $c$ is a square. The security comes from the quadratic residuosity assumption. This is the Goldwasser-Micali encryption scheme. Actually, this scheme has many good properties: it s randomizable, homomorphic for the xor operation, lossy (id est, the public key can come in two forms, either $y$ is a square and the encryption perfectly masks the bit, or it is a non-square and $b$ can be decrypted; this property is very useful to make security proofs of cryptographic schemes). It also allows for the design of oblivious transfer protocols (hence multiparty computation), among a considerable number of other applications.