Collisions in fast generation of ideal classes and points on hyperelliptic and elliptic curves (Q1772239)

In public key cryptography based on the discrete logarithm problem (DLP) one needs to compute scalar multiples of an element in a given cyclic group. It is then interesting to look for groups and algorithms allowing an easy computation of such an arithmetic operation. In the elliptic case of the DLP, \textit{N. Koblitz} [in: Advances in cryptology, Proc. Conf. Crypto'91, Lect. Notes Comput. Sci. 576, Springer 279--287 (1992; Zbl 0780.14018)] proposed the use of the so called subfield or Koblitz elliptic curves. The Frobenius endomorphism allows then to speed up the computation of scalar multiples of a point. In the hyperelliptic case an alternative approach has been proposed: Let \(D\in \text{Cl}({\mathcal C}| \mathbb{F}_{q^n})\)\, be an ideal class, \({\mathcal C}\) hyperelliptic curve defined over \(\mathbb{F}_q\). A ``random'' ideal class \(D_m\)\, is found as \[ D_m= \sum m_j\sigma^j(D),\,\, m=(m_0,m_1,\dots,m_{k-1}) \] with \(\sigma\) the Frobenius endomorphism induced by the field extension \(\mathbb F_{q^n}| \mathbb F_q\) and \(m=(m_0,m_1,\dots, m_k)\), \(m_i\) in a certain set of integers \({\mathcal R}\). The drawback of this construction is that more than one \(m\) can give the same ideal class. The present paper approaches this problem and find an upper bound on the number of representations of a given ideal class (theorem 2, section 3). In the particular case of genus 1 the authors consider a modified algorithm for the Koblitz elliptic curves due to \textit{J. Solinas} [Des. Codes Cryptography 19, 195--249 (2000; Zbl 0997.94017)], which uses a representation of \(m\) in the so-called non-adjacent form (\(m_i\in \{0,\pm 1\}\)\, and such that two consecutive terms are never both nonzero). Theorem 3, section 3 gives an upper bound on the number of representations in this case. As a corollary the authors give an expression for the probability of a collision (Section 4).