1
$\begingroup$

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?

HomDiag1 HomDiag2 HomDiag3

*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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – K.G.
    Nov 20, 2017 at 11:36
  • $\begingroup$ @K.G. I agree. But I think that goes far beyond the question. $\endgroup$
    – DrLecter
    Nov 20, 2017 at 12:31
  • $\begingroup$ @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) $\endgroup$
    – tylo
    Nov 20, 2017 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.