Paper 2022/480

Medha: Microcoded Hardware Accelerator for computing on Encrypted Data

Ahmet Can Mert, Aikata, Sunmin Kwon, Youngsam Shin, Donghoon Yoo, Yongwoo Lee, and Sujoy Sinha Roy

Abstract

Homomorphic encryption enables computation on encrypted data, and hence it has a great potential in privacy-preserving outsourcing of computations to the cloud. Hardware acceleration of homomorphic encryption is crucial as software implementations are very slow. In this paper we present design methodologies for building a programmable hardware accelerator for speeding up the cloud-side homomorphic evaluations on encrypted data. First, we propose a divide-and-conquer technique that enables homomorphic evaluations in the polynomial ring $R_{Q,2N} = \mathbb{Z}_{Q}[x]/(x^{2N} + 1)$ to use a hardware accelerator that has been built for the smaller ring $R_{Q,N} = \mathbb{Z}_{Q}[x]/(x^{N} + 1)$. The technique makes it possible to use a single hardware accelerator flexibly for supporting several homomorphic encryption parameter sets. Next, we present several architectural design methods that we use to realize the flexible and instruction-set accelerator architecture, which we call as `Medha'. At every level of the implementation hierarchy, we explore possibilities for parallel processing. Starting from hardware-friendly parallel algorithms for the basic building blocks, we gradually build heavily parallel RNS polynomial arithmetic units. Next, many of these parallel units are interconnected elegantly so that their interconnections require the minimum number of nets, therefore making the overall architecture placement-friendly on the platform. As homomorphic encryption is computation- as well as data-centric, the speed of homomorphic evaluations depends greatly on the way the data variables are handled. For Medha, we take a memory-conservative design approach and get rid of any off-chip memory access during homomorphic evaluations. Finally, we implement Medha in a Xilinx Alveo U250 FPGA and measure timing performances of the microcoded homomorphic addition, multiplication, key-switching, and rescaling routines for the leveled fully homomorphic encryption scheme RNS-HEAAN at 200 MHz clock frequency. For the large parameter sets $(\log Q, N) = (438, 2^{14})$ and $(546, 2^{15})$, Medha achieves accelerations by up to $68\times$ and $78\times$ times respectively compared to a highly optimized software implementation Microsoft SEAL running at 2.3 GHz.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
Homomorphic EncryptionCKKSFlexibleHardware Accelerator
Contact author(s)
ahmet mert @ iaik tugraz at
aikata @ iaik tugraz at
sujoy sinharoy @ iaik tugraz at
History
2022-04-23: received
Short URL
https://ia.cr/2022/480
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/480,
      author = {Ahmet Can Mert and Aikata and Sunmin Kwon and Youngsam Shin and Donghoon Yoo and Yongwoo Lee and Sujoy Sinha Roy},
      title = {Medha: Microcoded Hardware Accelerator for computing on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2022/480},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/480}},
      url = {https://eprint.iacr.org/2022/480}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.