Architectural enhancements for fast subword permutations with repetitions in cryptographic applications

J. P. McGregor, R. B. Lee

Research output: Contribution to conferencePaperpeer-review

26 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 4-way superscalar processor; an arbitrary 64-bit permutation with repetitions of 1-bit subwords can be completed in 11 instructions and only 4 cycles using the two proposed instructions. For subwords of size 4 bits or greater, an arbitrary permutation with repetitions of a 64-bit register can be completed in a single cycle using a single swperm instruction. This improves upon previous permutation instruction proposals that require log(r) sequential instructions to permute r subwords of a 64-bit word without repetitions. Our method requires 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.

Original languageEnglish (US)
Pages453-461
Number of pages9
StatePublished - 2001
EventIEEE International Conference on: Computer Design: VLSI in Computers and Processors (ICCD 2001) - Austin, TX, United States
Duration: Sep 23 2001Sep 26 2001

Other

OtherIEEE International Conference on: Computer Design: VLSI in Computers and Processors (ICCD 2001)
Country/TerritoryUnited States
CityAustin, TX
Period9/23/019/26/01

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Architectural enhancements for fast subword permutations with repetitions in cryptographic applications'. Together they form a unique fingerprint.

Cite this