Hardware Implementation of Barrett Reduction Exploiting Constant Multiplication
Why is this work in the frame?
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
No Canadian affiliation. An affiliation-only frame — the usual design — would never have seen this work. It is one of the works that make the case for inverting the frame.
The three-model screen
all 1,000 screened works →All three models called this out of scope.
Hardware implementation of Barrett modular reduction for elliptic curve cryptography; the object is a circuit design.
The dissertation develops hardware implementations for cryptographic arithmetic rather than studying research.
Hardware implementation of modular reduction for cryptography; computer engineering, not metaresearch.
Abstract
The efficient realization of an Elliptic Curve Cryptosystem is contingent on the efficiency of scalar multiplication. These systems can be improved by optimizing the underlying finite field arithmetic operations which are the most costly such as modular reduction. There are elliptic curves over prime fields for which very efficient reduction formulas are possible due to the special structure of the moduli. For prime moduli of arbitrary form, however, use of general reduction formulas, such as Barrett's reduction algorithm, are necessary. Barrett's algorithm performs modular reduction efficiently by using multiplication as opposed to division, an operation which is generally expensive to realize in hardware. We note, however, that when an Elliptic Curve Cryptosystem is defined over a fixed prime field, all multiplication steps in Barrett's scheme can be realized through constant multiplications; this allows for further optimization. In this thesis, we study the influence using constant multipliers has on four different Barrett reduction variants targeting the Virtex-7 (xc7vx485tffg1157-1). We use the FloPoCo core generator to construct constant multiplier implementations for the different multiplication steps required in each scheme. Then, we create a hybrid constant multiplier circuit based on Karatsuba multiplication which uses smaller FloPoCo-generated base multipliers. It is shown that for certain multiplication steps, the hybrid design provides an improvement in the resource utilization of the constant multiplier circuit at the cost of an increase in the critical path delay. A performance comparison of different Barrett reduction circuits using different combinations of constant multiplier architectures is presented. Additionally, a fully pipelined implementation of each Barrett reduction variant is also designed capable of achieving operational frequencies in the range of 496-504MHz depending on the Barrett scheme considered. With the addition of a 256-bit pipelined Karatsuba multiplier circuit, we also present a compact and fully pipelined modular multiplier based on these Barrett architectures capable of achieving very high throughput compared to others in the literature without the use of embedded multipliers.
Stored with the screening record, where it is evidence for the labels above.
The record
- Venue
- UWSpace (University of Waterloo)
- Topic
- Cryptography and Residue Arithmetic
- Field
- Computer Science
- Canadian institutions
- —
- Funders
- Natural Sciences and Engineering Research Council of CanadaNational Institute of Standards and TechnologyUniversity of Waterloo
- Keywords
- Multiplication (music)Reduction (mathematics)Constant (computer programming)Computer scienceArithmeticMathematicsProgramming language
- Has abstract in OpenAlex
- yes