A key-private cryptosystem from the quadratic residuosity

This paper presents a key-private public-key cryptosystem. More specifically, in addition to confidentiality, it provides privacy. Informally, ciphertexts yield no information whatsoever about its recipient (beyond what is publicly known). The presented cryptosystem also features a very fast key generation: the key generation boils down to a mere squaring modulo an RSA modulus. Further, it comes with strong security guarantees: it is proved to be semantically secure and key-private under the standard quadratic residuosity assumption.