3
$\begingroup$

I am learning about partially homomorphic cryptography, and was interested to see if there was a system such that one operation was homomorphic, but its inverse was not.

For example, if I have two messages $m_1$ and $m_2$, with an ecryption scheme $e(x)$, is there a cryptosystem such that we can compute $e(m_1 + m_2)$, but it would be infeasible to compute $e(m_1 - m_2)$? Or a cryptosystem that can compute $e(m_1 m_2)$ but not $e(m_1 m_2^{-1})$?

I looked into homomorphic addition systems such as Pallier, which is feasible to compute the additive inverse. I also looked into homomorphic multiplication systems such as RSA and El Gamal, but it seems like its possible to compute the multiplicative inverse as well. Is it always the case that if one operation is homomorphic, its inverse is also homomorphic?

|improve this question|||||
$\endgroup$
  • $\begingroup$ I suspect this may be referred to as a "Monoid homomorphism" (as opposed to a Group/Ring/Field homomorphism). A Monoid is like a group without inverses. $\endgroup$ – Ella Rose Nov 22 '18 at 4:26
  • $\begingroup$ Thanks -- I will try to research more into monoid homomorphism. I spent about 30 minutes on it, and it seems to be mostly theoretical, and not related to the typical cases of homomorphic encryption (computing the sum or multiplication of the message in encrypted space). Is there any existing homomorphic encryption schemes that are monoid? $\endgroup$ – user3667125 Nov 22 '18 at 6:11
  • 2
    $\begingroup$ @EllaRose saying that a monoid is like a group without inverse is a bit misleading. Every group (with the implied inverse) is also a monoid. It's just that a monoid does not require existence of an inverse. So more precisely you would require a homomorphism over a monoid that is not a group or where the inverse is infeasible to compute in polynomial time. (The latter seems more likely to work out as a structure to define a pke scheme over.) $\endgroup$ – Maeher Nov 22 '18 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.