A Unified Multiply/Accumulate Unit for Pairing-Based Cryptography over Prime, Binary and Ternary FieldsTobias Vejda, Johann Groszschaedl, Dan Page, A Unified Multiply/Accumulate Unit for Pairing-Based Cryptography over Prime, Binary and Ternary Fields. Digital System Design, Architectures, Methods and Tools (DSD). ISBN 978-1-4577-1048-3, pp. 658–666. September 2011. No electronic version available.
Bilinear maps, or pairings, on elliptic curves are an active area of research in modern cryptology with applications ranging from cryptanalysis (e.g. MOV attack) over identity-based encryption to short signature schemes. Many parameterisations and implementation options for pairing-based cryptography have been investigated in the recent past. Elliptic curves over prime fields are often preferred for software implementation, whereas extension fields of characteristic two and three offer advantages for implementation in hardware. In the ideal case, a hardware accelerator for pairing-based cryptography can support all three types of field to ensure inter-operability with a broad spectrum of applications. This need has motivated the design of so-called unified multipliers, which are basically multipliers that integrate different types of operands (e.g. integers and polynomials) into a single data path. In the present paper, we introduce a unified multiply/accumulate unit for signed/unsigned integers as well as binary and ternary polynomials. The multiplier generates partial products using a Redundant Signed-Digit (RSD) representation that allows for efficient combination of all three operand types into one data path. In addition, our design takes advantage of a high-radix encoding scheme for integers and binary polynomials to reduce the overall number of partial products and utilise the data path in an optimal way. We compare our multiplier with a previous radix-2 implementation of Ozturk et al and analyse the differences in terms of silicon area and critical path delay. The unified multiply/accumulate unit described in this paper can be used in embedded systems like smart cards, either as arithmetic core of a cryptographic co-processor, or as functional unit of an application-specific processor.