Architectural techniques for accelerating subword permutations with repetitions

John P. McGregor, Ruby B. Lee

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

We propose two new instructions, swperm and sieve, that can be used to efficiently complete an arbitrary bit-level permutation of an n-bit word with or without repetitions. Permutations with repetitions are rearrangements of an ordered set in which elements may replace other elements in the set; such permutations are useful in cryptographic algorithms. On a four-way superscalar processor, we can complete an arbitrary 64-bit permutation with repetitions of 1-bit subwords in 11 instructions and only four cycles using the two proposed instructions. For subwords of size 4 bits or greater, we can perform an arbitrary permutation with repetitions of a 64-bit register in a single cycle using a single swperm instruction. This improves upon previous results by requiring fewer instructions to permute 4-bit or larger subwords packed in a 64-bit register and fewer execution cycles for 1-bit subwords on wide superscalar processors. We also demonstrate that we can accelerate the performance of the popular DES block cipher using the proposed instructions. We obtain a DES performance improvement of at least 55% in constrained embedded environments and an improvement of 71% on a four-way superscalar processor when applying DES as a cryptographic hash function.

Original languageEnglish (US)
Pages (from-to)325-335
Number of pages11
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume11
Issue number3
DOIs
StatePublished - Jun 2003

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Keywords

  • Cryptography
  • Encryption
  • Instruction set architecture
  • Permutation
  • Permutation instruction
  • Processor architecture
  • Subword parallelism
  • Subword permutation

Fingerprint Dive into the research topics of 'Architectural techniques for accelerating subword permutations with repetitions'. Together they form a unique fingerprint.

  • Cite this