Hardware index to permutation converter
Abstract
We demonstrate a circuit that generates a permutation in response to an index. Since there are n! n-element permutations, the index ranges from 0 to n! à ¢ 1. Such a circuit is needed in the hardware implementation of unique-permutation hash functions to specify how parallel machines interact through a shared memory. Such a circuit is also needed in cryptographic applications. The circuit is based on the factorial number system. Here, each non-negative integer is uniquely represented as snà ¢ 1(nà ¢ 1)! +snà ¢ 2(nà ¢ 2)! +...+s11!, where 1 à ¢ à ¤ si à ¢ à ¤ i. That is, the permutation is produced by generating the digits si in the factorial number system representation of the index. The circuit is combinational and is easily pipelined to produce one permutation per clock period. We give experimental results that show the efà ¯à ¬ ciency of our designs. For example. we show that the rate of production of permutations on the SRC-6 reconà ¯à ¬ gurable computer is 1,820 times faster than a program on a conventional microprocessor in the case of 10-element permutations. We also show an efà ¯à ¬ cient reconà ¯à ¬ gurable computer implementation that produces random permutations using the Knuth shufà ¯à ¬ e algorithm. This is useful in Monte Carlo simulations. For both circuits, the complexity is O(n2), and the delay is O(n).
Description
19th Reconfigurable Architectures Workshop, May 21-22, 2012, Shanghai, China.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Affine equivalence and constructions of cryptographically strong Boolean functions
Chung, Jong Ho (Monterey, California: Naval Postgraduate School, 2013-09);In this thesis, we study a type of affine equivalence for the monomial rotation-symmetric (MRS) Boolean func-tions and two new construction techniques for cryptographic Boolean functions based on the affine equivalence of ... -
An analysis of the C class of bent functions
Stănică, Pantelimon; Mandal, Bimal; Gangopadhyay, Sugata; Pasalic, Enes (2015-06-14);Two (so-called C;D) classes of permutation-based bent Boolean functions were introduced by Carlet two decades ago, but without specifying some explicit construction methods for their construction (apart from the subclass ... -
Circulant matrices and affine equivalence of monomial rotation symmetric Boolean functions
Canright, David; Chung, Jong H.; Stănică, Pantelimon (Elsevier, 2015);The goal of this paper is two-fold. We first focus on the problem of deciding whether two monomial rotation symmetric (MRS) Boolean functions are affine equivalent via a permutation. Using a correspondence between such ...