# Partially Homomorphic Cryptographic Schemes - Deterministic vs Probabilistic

While reading this paper I realized that textbook RSA was the only deterministic PHE scheme mentioned. I did cross-check the ones listed in the Wikipedia article also and, quite on the opposite direction to this question, I could not find any of them to be deterministic. Now, I am aware that, as drLecter points out in the answer to the question previously linked, the deterministic ones are weaker and are to be avoided. However, I would be very interested in knowing whether any other PHE scheme exists aside from RSA. I think it might be the reason why it is the only one I've seen where the operation is the same (modular multiplication) in the Plaintext and Ciphertext space.

Also, trying to respect the original notation on RSA's homomorphism but emulating the figure 2.1* of the paper which of these 3 diagrams would be more correct?

*I linked a cached version of the paper 'cause the only pdf I found gets directly downloaded when clicking the link. Unfortunately the figure 2.1 cannot be seen on the cached version, here is the link for the actual pdf.

## 1 Answer

Yes, there exist other deterministic PHE schemes. Actually, you can turn any probabilistic PHE into a deterministic one. This is achieved by deriving the random coins for the encryption deterministically from the message to be encrypted, e.g., by computing the random coins as a hash of the message (using a suitable hash function compatible with the randomness space of the encryption scheme).

Moreover, the determinism of the PHE is not related to whether the operation on plain- and ciphertexts are identical (a simple counterexample is ElGamal encryption, which is a probabilistic PHE, and uses the same operations on plaintexts and ciphertext components).

• While what you say is true, you should be aware that such constructions do not have the same properties as RSA has. E.g. what happens if you encrypt two distinct messages and multiply the ciphertexts, or if you encrypt the product of the messages directly.
– K.G.
Nov 20, 2017 at 11:36
• @K.G. I agree. But I think that goes far beyond the question. Nov 20, 2017 at 12:31
• @K.G. Both multiplying ciphertexts as well as encrypt the product of messages are just specific realizations of homomorphic properties in the context of RSA. In other cryptosystems neither of those have to be related to an existing homomorphism (although the product of ciphertexts is involved quite often, e.g. ElGamal and Paillier)
– tylo
Nov 20, 2017 at 13:00