The Group Action of CSIDH and CSURF Sample Clauses

The Group Action of CSIDH and CSURF. ‌ √ → The traditional way of evaluating the group action of an element [a] ∈ Cl(O) is by using ‘traditional’ V´elu’s [25] or ´elu [4] formulas. The group action maps E [a] E and can be described by the kernel E[a] of an isogeny ϕa of finite degree. Specifically, [a] E = E/E[a] where E[a]= Ker(ϕ). ϕ∈a i In both CSIDH and CSURF, we apply specific elements [li] ∈ Cl(O) such that l±1 = (li,π ∓ 1) and li is the i-th odd prime dividing (p + 1). For li, we have E[l±1]= E[li] ∩ E[π ∓ 1], where P ∈ E[li] means P is a point of order li and P ∈ E[π ∓ 1] implies π(P ) = ±P , so P is either an Fp-rational point or a zero-trace point over Fp2 . Thus, the group action E → [l±1] E is usually calculated by sampling a point P ∈ E[l±1] and applying V´elu’s formulas with input point P . A secret key for i CSIDH is then a vector (ei), which is evaluated as E → i[li]ei E. CSURF O changes the order used to Z[ 1+π ] to also perform 2-isogenies on the surface of the isogeny graph; these 2-isogenies do not require the sampling of a 2-order point but can instead be calculated by a specific formula based on radical com- putations. ) Key space. Originally, the secret key e = (ei) was sampled from −m . . m n for some bound m ∈ N. This was improved in [12, 15, 18] by varying the bound m per degree li (a weighted L∞-xxxx xxxx). Further developments with regards to improving the key space are presented in [19], using an (L1 +L∞)-xxxx xxxx, and in CTIDH ([3]). These methods can give significant speed-ups. In their cores, they rely on (variations of) V´elu isogenies to evaluate the group action. In [7, 8], the authors compare the performance of radical isogenies to CSIDH by using an unweighted L∞-xxxx xxxx for CSIDH-512 versus a weighted L∞-xxxx xxxx for the implementation using radical isogenies. This gives a skewed benchmark, which favors the performance of CSURF and CRADS. In this paper, to make a fair comparison to the previous work, we continue in the line of [12, 15, 18] by using weighted L∞-norm balls for the implementations of CSIDH, CSURF and CRADS. It remains interesting to analyse the impact of radical isogenies in key spaces that are not based on weighted L∞-norm balls. As radical isogenies can easily be made to have exactly the same cost per degree (with only slightly extra cost), they are interesting to analyse with respect to CTIDH.