Collisions in Fast Generation of Ideal Classes and Points on Hyperelliptic and Elliptic Curves

Tanja Lange, Igor Shparlinski

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    Koblitz curves have been proposed to quickly generate random ideal classes and points on hyperelliptic and elliptic curves. To obtain a further speed-up 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
    JournalJournal of Applicable Algebra in Engineering
    Volume15
    Issue number5
    Pages (from-to)329-337
    Number of pages9
    ISSN0938-1279
    Publication statusPublished - 2005

    Keywords

    • Public key cryptography
    • discrete logarithm
    • hyperelliptic curves
    • Koblitz curves
    • collisions

    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