Bit-sliced binary normal basis multiplication

Billy Brumley, Dan Page

    Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

    1 Citation (Scopus)


    The performance of many cryptographic primitives is reliant on efficient algorithms and implementation techniques for arithmetic in binary fields. While dedicated hardware support for said arithmetic is an emerging trend, the study of software-only implementation techniques remains important for legacy or non-equipped processors. One such technique is that of software-based bit-slicing. In the context of binary fields, this is an interesting option since there is extensive previous work on bit-oriented designs for arithmetic in hardware, such designs are intuitively well suited to bit-slicing in software. In this paper we harness previous work, using it to investigate bit-sliced, software-only implementation arithmetic for binary fields, over a range of practical field sizes and using a normal basis representation. We apply our results to demonstrate significant performance improvements for a stream cipher, and over the frequently employed Ning-Yin approach to normal basis implementation in software.

    Original languageEnglish
    Title of host publicationProceedings - 20th IEEE Symposium on Computer Arithmetic, ARITH-20
    Number of pages8
    Publication statusPublished - 2011
    Publication typeA4 Article in conference proceedings
    Event20th IEEE Symposium on Computer Arithmetic, ARITH-20 - Tubingen, Germany
    Duration: 25 Jul 201127 Jul 2011


    Conference20th IEEE Symposium on Computer Arithmetic, ARITH-20


    • Algorithm design
    • analysis
    • Computations in finite fields
    • Computer arithmetic
    • Data encryption

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Software
    • Hardware and Architecture


    Dive into the research topics of 'Bit-sliced binary normal basis multiplication'. Together they form a unique fingerprint.

    Cite this