Arithmetic Design for Permutation Groups
Tamás Horváth6 
| (6) |
Secunet AG, Im Teelbruch 116, 45219 Essen, Germany |
Abstract
This paper investigates the hardware implementation of arithmetical operations (multiplication and inversion) in symmetric and alternating groups, as well as in binary permutation groups (permutation groups of order 2
r). Various fast and space-efficient hardware architectures will be presented. High speed is achieved by employing switching
networks, which effect multiplication in one clock cycle (full parallelism). Space-efficiency is achieved by choosing, on
one hand, proper network architectures and, on the other hand, the proper representation of the group elements. We introduce
a non-redundant representation of the elements of binary groups, the so-called compact representation, which allows low-cost realization of arithmetic for binary groups of large degrees such as 128 or even 256. We present highly
optimized multiplier architectures operating directly on the compact form of permutations. Finally, we give complexity and
performance estimations for the presented architectures
Keywords permutation multiplier - switching network - destination-tag routing - sorting network - separation network - binary group - compact representation - secret-key cryptosystem - PGM
References secured to subscribers.