Cryptology ePrint Archive: Report 2015/631

Accelerating Homomorphic Evaluation on Reconfigurable Hardware

Thomas Pöppelmann and Michael Naehrig and Andrew Putnam and Adrian Macias

Abstract: Homomorphic encryption allows computation on encrypted data and makes it possible to securely outsource computational tasks to untrusted environments. However, all proposed schemes are quite inefficient and homomorphic evaluation of ciphertexts usually takes several seconds on high-end CPUs, even for evaluating simple functions. In this work we investigate the potential of FPGAs for speeding up those evaluation operations. We propose an architecture to accelerate schemes based on the ring learning with errors (RLWE) problem and specifically implemented the somewhat homomorphic encryption scheme YASHE, which was proposed by Bos, Lauter, Loftus, and Naehrig in 2013. Due to the large size of ciphertexts and evaluation keys, on-chip storage of all data is not possible and external memory is required. For efficient utilization of the external memory we propose an efficient double-buffered memory access scheme and a polynomial multiplier based on the number theoretic transform (NTT). For the parameter set (n=16384,log_2(q)=512) capable of evaluating 9 levels of multiplications, we can perform a homomorphic addition in 48.67 and a homomorphic multiplication in 0.94 ms.

Category / Keywords: implementation /

Original Publication (with major differences): IACR-CHES-2015

Date: received 25 Jun 2015

Contact author: thomas poeppelmann at rub de, mnaehrig@microsoft com, anputnam@microsoft com