Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Frequency Domain Arithmetic for Cryptography

 

SELCUK BAKTIR
Cryptography & Information Security Laboratory
Electrical & Computer Engineering Department
Worcester Polytechnic Institute

Finite fields have many applications in coding theory and cryptography, therefore efficient implementation of finite field arithmetic operations is crucial. The known fastest multiplication algorithm, introduced by Schnhage and Strassen, performs multiplication in the frequency domain using the Fast Fourier Transform (FFT) with complexity O(m log(m) log(log(m))) for multiplication of m-bit integers or m-coefficient polynomials. Unfortunately, the method bears significant overhead due to the conversions between the time and frequency domains, which makes it impractical for relatively short (160-1024 bit) operands as used in many applications. In this work, we investigate practical frequency domain multiplication techniques for cryptographic operand lengths. We first propose using the FFT for performing efficient multiplication in Mersenne and Fermat extension fields. We show that, with careful selection of parameters, all multiplications required for the FFT computations can be avoided and polynomial multiplication in these finite fields can be achieved with only O(m) multiplications in addition to as low as O(m log(m)) simple shift, addition and subtraction operations. Thus, in constrained devices where multiplication is expensive, the suggested method outperforms other efficient methods such as Karatsuba for even small operands, e.g. relevant to elliptic curve cryptography (ECC). Finally, we introduce "DFT Modular Multiplication" which computes Montgomery products of polynomials in the frequency domain. Thus, both polynomial multiplication and modular reduction are performed in the frequency domain, and costly conversions between the frequency and time domains are avoided. We propose a novel time/area efficient DFT modular multiplier architecture and an ECC processor which achieves ECC in the frequency domain utilizing the proposed multiplier. To our best knowledge, this work presents the first hardware implementation of a frequency domain multiplier for ECC and the first hardware implementation of ECC in the frequency domain. The synthesis results for our ECC processor are presented for custom VLSI CMOS technology for 169, 289 and 361 bit fields. We show that the proposed ECC processor is time/area efficient and is promising for constrained environments such as wireless sensor networks.

 

DATE: June 28, 2006, Wednesday@ 13:40
PLACE: EA 409