1
$\begingroup$

Let $E$ be a supersingular elliptic curve which is defined over $\mathbb{F}_q$ and $P\in E$. Then there exist a distortion map with respect to $P$. I am looking for an algorithm which finds the map and the complexity of the algorithm.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The paper "Easy Decision-Diffie-Hellman Groups" by S. Galbraith and V. Rotger contains an algorithm to generate a curve together with a distortion map (as pointed out by yyyyyyyy in the comments).

Computing a distortion map on a random super singular elliptic curve is computationally hard. A distortion map is a smooth endomorphism of the curve, and finding such an endomorphism is a well-known problem in cryptography. See, for instance, Problem 1 in [1]. The problem is heuristically equivalent to finding the entire endomorphism ring of the curve.

[1] L. De Feo, D. Kohel, A. Leroux, C. Petit, B. Wesolowski, SQISign: compact post-quantum signatures from quaternions and isogenies, https://eprint.iacr.org/2020/1240.pdf

$\endgroup$
1
  • 1
    $\begingroup$ That algorithm constructs an elliptic curve together with a distortion map. The question asks about finding a distortion map for a given curve, which is usually much more difficult. $\endgroup$
    – yyyyyyy
    Feb 18, 2022 at 3:57

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.