1
$\begingroup$

Let $G$ be a prime order $Q$ elliptic curve over a prime field of size $P$ which admits the following mapping $f$

$f(aG, bG) = abG$

which can be computed in polynomial time in $\log(PQ)$.

Is the existence of such a thing ruled out assuming ECDLP hardness or a substantially stronger computational assumption?

If such an efficient mapping existed, we would get an easy practical FHE. Clearly such a thing either doesn't exist or is very very difficult to find. Do we have any formalization of this hardness?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ @HilderVitorLimaPereira: the corresponding addition operation $g(aG, bG) = aG + bG = (a+b)G$ is easy. $\endgroup$
    – poncho
    Commented Sep 17 at 14:09

2 Answers 2

Reset to default
3
$\begingroup$

This function would solve the computational Diffie-Hellman problem in polynomial time. We specifically intend to choose cryptographic curves as ones where this problem is hard.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great, so there is an assumption named after this exact problem. No reducing from another assumption is needed $\endgroup$
    – MERTON
    Commented Sep 17 at 20:09
2
$\begingroup$

IIRC, such an "ideal pairing" would also make it possible to solve the discrete log problem in $G$ in subexponential time:

https://crypto.stanford.edu/~dabo/pubs/abstracts/bbf.html

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! Looking into this. Interesting curves would be the ones where DLP is hard but CDH is easy (the gap between them is as large as possible). Apparently this paper put a limit on the difficulty gap between these two. $\endgroup$
    – MERTON
    Commented Sep 17 at 20:29

Your Answer

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

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