Search

CSIDH is an isogeny-based key exchange protocol proposed by Castryck et al. in 2018. It is based on the ideal class group action on F p -isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over F p by representing points as x -coordinate over Montgomery curves. There is a special coordinate on Edwards curves (the w -coordinate) to calculate group operations and isogenies. If we try to calculate the class group action on Edwards curves by using the w -coordinate in a similar way on Montgomery curves, we have to consider points defined over F p 4 . Therefore, calculating the class group action on Edwards curves with w -coordinates over only F p is not a trivial task. In this paper, we prove some theorems about the properties of Edwards curves. We construct the new CSIDH algorithm using these theorems on Edwards curves with w -coordinates over F p. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith. This paper is an extended version of [29]. We added the construction of a technique similar to Elligator on Edwards curves. This technique contributes to the efficiency of the constant-time CSIDH algorithm. We also added the construction of new formulas to compute isogenies in O ˜ (ℓ) time on Edwards curves. It is based on formulas on Montgomery curves proposed by Bernstein et al. ( élu's formulas). In our analysis, these formulas on Edwards curves are a little bit faster than those on Montgomery curves. We finally implemented CSIDH, élu's formulas, and CTIDH [3] (faster constant-time CSIDH) on Edwards curves. Each result shows the efficiency of algorithms on Edwards curves. [ABSTRACT FROM AUTHOR]

By a result of Latimer and MacDuffee, there are a finite number of equivalence classes of n × n matrices over F q [ T ] with minimum polynomial p (X) , where p is an n th degree polynomial, irreducible over F q [ T ]. In this paper, we develop an algorithm for finding a canonical representative of each matrix class, for p (X) = X 2 − Γ X − Δ ∈ F q [ T ] [ X ]. [ABSTRACT FROM AUTHOR]

In this paper, we provide two distinct list decoding algorithms tailored for specific classes of maximal order number field codes. The first algorithm focuses on the unit codes, while the second algorithm is dedicated to the Arakelov divisor-based number field codes. These codes were originally introduced by Maire and Oggier. To achieve our decoding goals, we utilize the list decoding algorithm for general number field codes proposed by Biasse and Quintin. Our approach involves carefully calculating the required parameter B from Biasse and Quintin's algorithm, and adjusting the returned list to satisfy the desired conditions. For unit codes, we consider two cases: when the underlying number field is totally real and when it has an arbitrary signature. We separate these cases because the parameter B can be improved in the totally real scenario. Additionally, we present our list decoding algorithm for Arakelov divisor-based number field codes, focusing on number fields with arbitrary signatures. [ABSTRACT FROM AUTHOR]

Pairing-friendly curves with the lack of twists, such as BW13-P310 and BW19-P286 , have been receiving attention in pairing-based cryptographic protocols as they provide fast operation in the first pairing subgroup G 1 at the 128-bit security level. However, they also incur a performance penalty for hashing to G 2 simultaneously since G 2 is totally defined over a full extension field. Furthermore, the previous methods for hashing to G 2 focus on pairing-friendly curves admitting a twist, which can not be employed for our selected curves. In this paper, we propose a general method for hashing to G 2 on curves with the lack of twists. More importantly, we further optimize the general algorithm on curves with non-trivial automorphisms, which is certainly suitable for BW13-P310 and BW19-P286. Theoretical estimations show that the latter would be more efficient than the former. For comparing the performance of the two proposed algorithms in detail, high speed software implementation over BW13-P310 is also provided on a 64-bit processor. Experimental results show that the general algorithm can be sped up by up to 88% if the computational cost of cofactor multiplication for G 2 is only considered, while the improved method is up to 71% faster than the general one for the whole process. [ABSTRACT FROM AUTHOR]

In this paper, based on the structure of embedded fields, we investigate explicit construction of systematic (k + 1 , k) mMDS sliding window codes with memory m = 2 , 3. First, over GF(2 l h) with l ≥ 1 and h ≥ 2 , we propose an algorithm to construct (2 l h − 1 + 1 , 2 l h − 1) mMDS codes with memory 2, which are optimal in the sense that 2 l h − 1 is the maximum possible value of k for a (k + 1 , k) sliding window code with memory 2 over GF(2 l h) to be mMDS. When l ≥ 2 , every constructed code has the extra property that it contains a (2 h − 1 + 1 , 2 h − 1) mMDS sliding window code with memory 2 as a subcode over the subfield GF(2 h). Next, over GF(2 2 l h) with l ≥ 1 and h ≥ 2 , we introduce a method to construct (k + 1 , k) mMDS codes memory 3, and a few new codes have been obtained consequently. When l ≥ 2 , every code constructed by the new approach also has the property that it contains an mMDS subcode over the subfield GF(2 2 h). The embedding subfield-subcode property enhances the flexibility and efficiency of the designed codes. [ABSTRACT FROM AUTHOR]

An n -arc in (k − 1) -dimensional projective space is a set of n points so that no k lie on a hyperplane. In 1988, Glynn gave a formula to count n -arcs in the projective plane in terms of simpler combinatorial objects called superfigurations. Several authors have used this formula to count n -arcs in the projective plane for n ≤ 10. In this paper, we determine a formula to count n -arcs in projective 3-space. We then use this formula to give exact expressions for the number of n -arcs in P 3 (F q) for n ≤ 7 , which are polynomial in q for n ≤ 6 and quasipolynomial in q for n = 7. Lastly, we generalize to higher-dimensional projective space. [ABSTRACT FROM AUTHOR]

In this paper, we explore some properties of hulls of cyclic serial codes over a finite chain ring and we provide an algorithm for computing all the possible parameters of the Euclidean hulls of that codes. We also establish the average p r -dimension of the Euclidean hull, where F p r is the residue field of R , as well as we give some results of its relative growth. [ABSTRACT FROM AUTHOR]

Our aim for this paper is to find the construction method for quasi-cyclic self-orthogonal codes over the finite field F p m . We first explicitly determine the generators of α -constacyclic codes over the finite Frobenius non-chain ring R p , m = F p m [ u , v ] / 〈 u 2 = v 2 = 0 , u v = v u 〉 , where m is a positive integer, α = a + u b + v c + u v d is a unit of R p , m , a , b , c , d ∈ F p m , and a is nonzero. We then find a Gray map from R p , m [ x ] / 〈 x n − α 〉 (with respect to homogeneous weights) to F p m [ x ] / 〈 x p 3 m + 1 n − a 〉 (with respect to Hamming weights), which is linear and preserves minimum weights. We present an efficient algorithm for finding the Gray images of α -constacyclic codes over R p , m of length n , which produces infinitely many quasi-cyclic self-orthogonal codes over F p m of length p 3 m + 1 and index p 3 m. In particular, some family turns out to be "Griesmer" codes; these Griesmer quasi-cyclic self-orthogonal codes are "new" codes compared with previously known Griesmer codes of dimension 4. [ABSTRACT FROM AUTHOR]

In this paper we establish decomposition theorems for derivations of group rings. We provide a topological technique for studying derivations of a group ring A [ G ] in case G has finite conjugacy classes. As a result, we describe all derivations of algebra A [ G ] for the case when G is a finite group, or G is an FC-group. In addition, we describe an algorithm to explicitly calculate all derivations of a group ring A [ G ] in case G is finite. As examples, derivations of Z 4 [ S 3 ] and F 2 m D 2 n are considered. [ABSTRACT FROM AUTHOR]

Quasi-subfield polynomials were introduced by Huang et al. together with a new algorithm to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) over finite fields of small characteristic. In this paper we provide both new quasi-subfield polynomial families and a new theorem limiting their existence. Our results do not allow to derive any speedup for the new ECDLP algorithm compared to previous approaches. [ABSTRACT FROM AUTHOR]