Aung, K M M., Lim, E H., Sim, J J., Tan, H M B. Field Instruction Multiple Data, Fully homomorphic encryption. HomomorphicEncryption.org Workshop
Abstract:
In this work, we describe a method to encode more data on top of SIMD, Field Instruction Multiple Data, applying reverse multiplication friendly embedding (RMFE) to FHE. With RMFE, length-k Ft vectors can be encoded into Ftd 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 2r 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× better (amortized) multiplication times compared to FHE for the same amount of data, while using almost k/2× fewer ciphertexts required.
License type:
Publisher Copyright
Funding Info:
This research / project is supported by the A*STAR - RIE2020 Advanced Manufacturing and Engineering (AME) Programmatic Programme
Grant Reference no. : A19E3b0099