Paper 2022/771

Field Instruction Multiple Data

Khin Mi Mi Aung, Institute for Infocomm Research
Enhui Lim, Institute for Infocomm Research
Jun Jie Sim, Nanyang Technological University
Benjamin Hong Meng Tan, Institute for Infocomm Research
Huaxiong Wang, Nanyang Technological University
Sze Ling Yeo

Fully homomorphic encryption~(FHE) has flourished since it was first constructed by Gentry~(STOC 2009). Single instruction multiple data~(SIMD) gave rise to efficient homomorphic operations on vectors in \((\mathbb{F}_{t^d})^\ell\), for prime \(t\). RLWE instantiated with cyclotomic polynomials of the form \(X^{2^N}+1\) dominate implementations of FHE due to highly efficient fast Fourier transformations. However, this choice yields very short SIMD plaintext vectors and high degree extension fields, e.g. \(\ell < 100, d > 100\) for small primes~(\(t = 3, 5, \dots\)). In this work, we describe a method to encode more data on top of SIMD, \emph{Field Instruction Multiple Data}, applying reverse multiplication friendly embedding~(RMFE) to FHE. With RMFE, length-\(k\) \(\mathbb{F}_{t}\) vectors can be encoded into \(\mathbb{F}_{t^d}\) and multiplied once. The results have to be recoded~(decoded and then re-encoded) before further multiplications can be done. We introduce an FHE-specific technique to additionally evaluate arbitrary linear transformations on encoded vectors for free during the FHE recode operation. On top of that, we present two optimizations to unlock high degree extension fields with small \(t\) for homomorphic computation: \(r\)-fold RMFE, which allows products of up to \(2^r\) encoded vectors before recoding, and a three-stage recode process for RMFEs obtained by composing two smaller RMFEs. Experiments were performed to evaluate the effectiveness of FIMD from various RMFEs compared to standard SIMD operations. Overall, we found that FIMD generally had \(>2\times\) better (amortized) multiplication times compared to FHE for the same amount of data, while using almost \(k/2 \times\) fewer ciphertexts required.

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2022
Homomorphic Encryption Finite Extension Fields RMFE Single Instruction Multiple Data
Contact author(s)
lim_enhui @ i2r a-star edu sg
junjie005 @ e ntu edu sg
benjamin_tan @ i2r a-star edu sg
2022-06-16: approved
2022-06-15: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Khin Mi Mi Aung and Enhui Lim and Jun Jie Sim and Benjamin Hong Meng Tan and Huaxiong Wang and Sze Ling Yeo},
      title = {Field Instruction Multiple Data},
      howpublished = {Cryptology ePrint Archive, Paper 2022/771},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.