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

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

  • Another example of the power of pseudosquares is identity based encryption. Primitives used in classical cryptography - such as ElGamal and RSA - are powerful tools, but they do not have enough structure to allow for some more involved cryptographic constructions, such as identity-based encryption. Indeed, IBE seems to require groups with more structures, such as pairings, or lattice-based cryptography. In this field, the Cock cryptosystem is an OVNI: it's an identity based encryption scheme based solely on the quadratic residuosity assumption, hence dealing with pseudosquares. Its existence suggests that pseudosquares enjoy very interesting and non-trivial features that cannot be found in, e.g., groups of squares, prime order fields ore elliptic curves without pairings.


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.