## Abstract

Polynomial multiplication is the basic and most computationally intensive operation in ring-learning with errors (ring-LWE) encryption and somewhat homomorphic encryption (SHE) cryptosystems. In this paper, the fast Fourier transform (FFT) with a linearithmic complexity of O(nlog n), is exploited in the design of a high-speed polynomial multiplier. A constant geometry FFT datapath is used in the computation to simplify the control of the architecture. The contribution of this work is three-fold. First, parameter sets which support both an efficient modular reduction design and the security requirements for ring-LWE encryption and SHE are provided. Second, a versatile pipelined architecture accompanied with an improved dataflow are proposed to obtain a high-speed polynomial multiplier. Third, the proposed architecture supports polynomial multiplications for different lengths n and moduli p. The experimental results on a Spartan-6 FPGA show that the proposed design results in a speedup of 3.5 times on average when compared with the state of the art. It performs a polynomial multiplication in the ring-LWE scheme (n=256,p=1049089) and the SHE scheme (n=1024,p=536903681) in only 6.3 μs and 33.1 μs, respectively.

Original language | English |
---|---|

Pages (from-to) | 157-166 |

Number of pages | 10 |

Journal | IEEE Transactions on Circuits and Systems I: Regular Papers |

Volume | 62 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Jan 2015 |

## Keywords

- Cryptography
- FFT polynomial multiplication
- Field-programmable gate array (FPGA)
- Number theoretic transform (NTT)
- Pipelined architecture
- Polynomial multiplication
- Ring-LWE
- SHE

## ASJC Scopus subject areas

- Electrical and Electronic Engineering