Paper 2024/2032

Carousel: Fully Homomorphic Encryption with Bootstrapping over Automorphism Group

Intak Hwang, Seoul National University
Seonhong Min, Seoul National University
Yongsoo Song, Seoul National University
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.