Implementation Complexity for Achieving Bit Permutations in One or Two Cycles in Superscalar Processors

Abstract — The increasing importance of secure information processing in publicly accessible Internet and wireless networks poses new challenges in the architecture of future general-purpose processors. Symmetric-key cryptography algorithms are an important class of algorithms used to achieve confidentiality. Many of them use a category of operations that are not well supported by today’s word-oriented microprocessors: bit-oriented permutations. In this paper, we show how arbitrary bit permutations within a word can be achieved in just one or two cycles. This improves upon the O(n) instructions needed to achieve any one of n! permutations of n bits in existing RISC processors; it also improves upon recent work that achieves this in O(log(n)) instructions and cycles. This paper contributes two new architectural solutions, one with only microarchitecture changes, and another with ISA support as well. Slightly enhanced 4-way and 2-way superscalar microprocessors can achieve arbitrary 64-bit permutations in one or two cycles. We also define new architectural concepts for (s,t) datapaths and functional units, and grouped instructions. Keywords—cryptography; bit permutation; superscalar; processor architecture; instruction set architecture (ISA); microarchitecture; I