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.
1 Answer
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
-
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$– yyyyyyyFeb 18, 2022 at 3:57