Security Analysis of Group Action Inverse Problem with Auxiliary Inputs with Application to CSIDH Parameters

摘要

In this paper, we consider the security of a problem called Group Action Inverse Problem with Auxiliary Inputs (GAIPwAI). The Group Action Inverse Problem (GAIP) plays an important role in the security of several isogeny-based cryptosystems, such as CSIDH, SeaSign and CSI-FiSh. Briefly speaking, given two isogenous supersingular curves E and E' over F_p, where E' is defined by an ideal a in the F_p-endomorphism ring of E and denoted by E' = [a] * E, GAIP requires finding a ⊂ End_(F_p)(E). Its best classical algorithm is based on the baby-step-giant-step method and it runs in time O(p~(1/4)). In this paper, we show that if E and E' are given together with [a~d] * E for a positive divisor d that divides the order of the class group of Z[-p~(1/2)], then a can be computed in O((p~(1/2)/d)~(1/2) -I- d~(l/2)) time complexity. In particular, when d ≈ p~(1/4), it can be solved in time O(p~(1/8)) which is significantly less than O(p1/4). Applying the idea to CSIDH-512 parameters, we show that, if an additional isogenous curve [a~d] * E is given, the security level of this cryptosystem reduces to 68-bit security instead of 128-bit security as originally believed.