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

Tanja Lange*, Igor Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

Koblitz curves have been proposed to quickly generate random ideal classes and points on hyperelliptic and elliptic curves. To obtain a further speedup a different way of generating these random elements has recently been proposed. In this paper we give an upper bound on the number of collisions for this alternative approach. For elliptic Koblitz curves we additionally use the same methods to derive a bound for a modified algorithm. These bounds are tight for cyclic subgroups of prime order, which is the case of most practical interest for cryptography.

Original languageEnglish
Pages (from-to)329-337
Number of pages9
JournalApplicable Algebra in Engineering, Communications and Computing
Volume15
Issue number5
DOIs
Publication statusPublished - Feb 2005

Keywords

  • Collisions
  • Discrete Logarithm
  • Hyperelliptic Curves
  • Koblitz Curves
  • Public Key Cryptography

Fingerprint Dive into the research topics of 'Collisions in fast generation of ideal classes and points on hyperelliptic and elliptic curves'. Together they form a unique fingerprint.

Cite this