I have recently been very interested in elliptic curves because they are a powerful tool in crypto, ECC, pairing, etc. However, it seems that elliptic curves are not popular in homomorphic encryption. I understand that lattice-based crypto is currently the only way to construct FHE, like LWE. Elliptic curves can only be used to construct PHE; for example, BGN. After doing some research as a freshman in HE, I found that there is not much effort in trying to use EC to construct FE. So, I'm just wondering why. Is it because elliptic curves have some issues in their structure, making it hard to construct HE? Or is it because lattice-based construction is a hot topic, so researchers prefer it over EC?

  • 1
    $\begingroup$ For FHE you need two operations: addition and multiplication (or equivalently "xor" and "and"). What's your suggestion for a second operation for two elements of a elliptic curves? $\endgroup$
    – j.p.
    Nov 18 '20 at 7:08
  • $\begingroup$ If I trust my instinct about what searching for recent articles mentioning Fully Homomorphic ECC returns, indeed nobody has figured it out. Note: I didn't read much past the abstracts (beyond the obligatory color graphs), and advise against it. $\endgroup$
    – fgrieu
    Nov 24 '20 at 12:33
  • $\begingroup$ @j.p. I understand that point adding is the rule of the elliptic curve group, and we can not multiple points directly cause it seems meaningless. However, that's not the only way, in BGN scheme, multiplication can be done by pairing, but only once. So I think the problem is that we just have not found THE right solution yet. $\endgroup$
    – rzxh
    Nov 29 '20 at 12:28
  • $\begingroup$ @HilderVitorLimaPereira In fact I really don't know and that's why I ask the question here. I read some papers recently and get the conclusion that constructing such a scheme with EC is definitely not easy, someone has to dive into the mathmatical background of EC. I can't grab the key problem and that's why I ask for some help or direction. Thanks for your reply. $\endgroup$
    – rzxh
    Nov 29 '20 at 12:47
  • $\begingroup$ I am not an expert, but I think that you can get "FHE for quadratic functions" from elliptic curves (see this). I think the difficulty for getting higher than degree 2 is related to the difficulty of getting multilinear maps of degree greater than 2, of which there has been a decent amount of research within the last decade due to applications to constructing indistinguishability obfuscation. That being said, someone who works in pairings-based crypto should probably verify this understanding. $\endgroup$
    – Mark
    Dec 27 '20 at 23:02

From my point of view, Homomorphism is a inherent attribute of certain lattice-based scheme.Researchers try every means of solution to enhance the attribute,but not all primitives have this attribute.


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.