Paper 2013/866

Compact Ring-LWE based Cryptoprocessor

Sujoy Sinha Roy and Frederik Vercauteren and Nele Mentens and Donald Donglong Chen and Ingrid Verbauwhede

Abstract

In this paper we propose an efficient and compact processor for a ring-LWE based encryption scheme. We present three optimizations of the Number Theoretic Transform (NTT) used for polynomial multiplication: we avoid pre-processing in the negative wrapped convolution by merging it with the main algorithm, we reduce the fixed computation cost of the twiddle factors and propose an advanced memory access scheme. These optimization techniques reduce both the cycle and memory requirements. Finally, we also propose an optimization of the ring-LWE encryption system that reduces the number of NTT operations from five to four resulting in 20\% speed-up. We use these computational optimizations along with several architectural optimizations to implement an instruction-set ring-LWE based cryptoprocessor. For dimension 512, corresponding to a high security level, our processor performs encryption/decryption operations in 53/21$\mu s$ on a Virtex 6 FPGA and only requires 1879 LUTs, 1142 FFs and 3 BRAMs. Our processor is therefore three times smaller than the current state of the art hardware implementations, whilst running somewhat faster.