Alternative application-specific processor architectures for fast arbitrary bit permutations

Zhijie Jerry Shi, Xiao Yang, Ruby B. Lee

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


Block ciphers are used to encrypt data and provide data confidentiality. For interoperability reasons, it is desirable to support a variety of block ciphers efficiently. Of the basic operations in block ciphers, only bit permutation is very slow on existing processors, followed by integer multiplication. Although new permutation instructions proposed recently can accelerate bit permutations in general-purpose processors, reducing the number of instructions needed to achieve an arbitrary n-bit permutation from O(n) to O(logSUB align=right2n), the data dependency between permutation instructions prevents them from being executed in fewer than logSUB align=right2n cycles, even on superscalar processors. Since Application-Specific Instruction-Set Processors (ASIPs) have fewer constraints on maintaining standard processor datapath and control conventions, six alternative ASIP approaches are proposed in this paper to achieve arbitrary 64-bit permutations in one or two cycles without increasing the cycle time. These approaches use new BFLY and IBFLY instructions. We also compare these approaches and their efficiency in performing arbitrary 64-bit permutations.

Original languageEnglish (US)
Pages (from-to)219-228
Number of pages10
JournalInternational Journal of Embedded Systems
Issue number4
StatePublished - 2008

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture


  • ASIP
  • Application specific instruction-set processor
  • Bit permutation
  • Block cipher
  • Confidentiality
  • Cryptography acceleration
  • Embedded system
  • Instruction set architecture
  • Software encryption
  • Symmetric-key cipher


Dive into the research topics of 'Alternative application-specific processor architectures for fast arbitrary bit permutations'. Together they form a unique fingerprint.

Cite this