Paper 2024/314
Exploring the Advantages and Challenges of Fermat NTT in FHE Acceleration
Abstract
Recognizing the importance of fast and resource-efficient polynomial multiplication in homomorphic encryption, in this paper, we introduce a novel method that enables integer multiplier-less Number Theoretic Transform (NTT) for computing polynomial multiplication. First, we use a Fermat number as an auxiliary modulus of NTT. However, this approach of using Fermat number scales poorly with the degree of polynomial. Hence, we propose a transformation of a large-degree univariate polynomial into small-degree multi-variable polynomials. After that, we compute these NTTs on small-degree polynomials with Fermat number as modulus. We design an accelerator architecture customized for the novel multivariate NTT and use it for benchmarking practical homomorphic encryption applications. The accelerator can achieve a 1,200× speed-up compared to software implementations. We further discuss the potential and limitations of the proposed polynomial multiplication method in the context of homomorphic encryption.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Fermat numberNTTPolynomial MultiplierFHEHardware Accelerator
- Contact author(s)
-
andrey kim @ samsun com
ahmet mert @ iaik tugraz at
anisha mukherjee @ iaik tugraz at
aikata @ iaik tugraz at
max deriabin @ samsung com
sunmin7 kwon @ samsung com
hc1803 kang @ samsung com
sujoy sinharoy @ iaik tugraz at - History
- 2024-02-26: approved
- 2024-02-23: received
- See all versions
- Short URL
- https://ia.cr/2024/314
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/314,
author = {Andrey Kim and Ahmet Can Mert and Anisha Mukherjee and Aikata Aikata and Maxim Deryabin and Sunmin Kwon and HyungChul Kang and Sujoy Sinha Roy},
title = {Exploring the Advantages and Challenges of Fermat NTT in FHE Acceleration},
howpublished = {Cryptology ePrint Archive, Paper 2024/314},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/314}},
url = {https://eprint.iacr.org/2024/314}
}
