Paper 2024/2032
Carousel: Fully Homomorphic Encryption with Bootstrapping over Automorphism Group
Abstract
Fully Homomorphic Encryption (FHE) enables the secure computation of functions on ciphertexts without requiring decryption. Specifically, AP-like HE schemes exploit an intrinsic bootstrapping method called blind rotation. In existing blind rotation methods, a look-up table is homomorphically evaluated on the input ciphertext through iterative multiplication of monomials. However, the algebraic structure of the multiplicative group of monomials imposes certain limitation on the input plaintext space, as it can bootstrap only a fraction of the input plaintext space. In this work, we introduce a new FHE scheme, Carousel, that solves this problem. The key idea of our approach is to utilize the automorphism group instead of monomials. More specifically, the look-up table is encoded into a single polynomial that can be rotated via a series of homomorphic multiplications and automorphisms. We instantiate Carousel with subring encoding proposed by Arita and Handa (ICISC ’17) and provide a proof-of-concept implementation. Our benchmark result shows that Carousel can bootstrap 4-bit integer under 30ms.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Homomorphic EncryptionLearning With ErrorsFHE
- Contact author(s)
-
intak hwang @ snu ac kr
minsh @ snu ac kr
y song @ snu ac kr - History
- 2025-06-25: revised
- 2024-12-16: received
- See all versions
- Short URL
- https://ia.cr/2024/2032
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/2032, author = {Intak Hwang and Seonhong Min and Yongsoo Song}, title = {Carousel: Fully Homomorphic Encryption with Bootstrapping over Automorphism Group}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/2032}, year = {2024}, url = {https://eprint.iacr.org/2024/2032} }