Welcome to the resource topic for 2024/1376
Title:
FDFB$^2$: Functional Bootstrapping via Sparse Polynomial Multiplication
Authors: Kamil Kluczniak, Leonard Schild
Abstract:Fully homomorphic encryption schemes are methods to perform compu-
tations over encrypted data. Since its introduction by Gentry, there has been a
plethora of research optimizing the originally inefficient cryptosystems. Over time,
different families have emerged. On the one hand, schemes such as BGV, BFV, or
CKKS excel at performing coefficient-wise addition or multiplication over vectors
of encrypted data. In contrast, accumulator-based schemes such as FHEW and
TFHE provide efficient methods to evaluate boolean circuits and means to efficiently
compute functions over small plaintext space of up to 4-5 bits in size.
In this paper, we focus on the second family. At a high level, accumulator-based
schemes encode the range of a function f in the coefficients of a polynomial, which
is then encrypted in a homomorphic accumulator. Given an input ciphertext, the
coefficients of the encrypted polynomial are homomorphically rotated, such that there
is a correspondence between the constant term of the result and the message contained
in the ciphertext. In the end, it is possible to derive a ciphertext of the constant term
encrypted with regard to the same encryption scheme as the input ciphertext. To
summarize, by appropriately encoding the function f on the accumulated polynomial,
we can compute f on the plaintext of the input ciphertext, where the output ciphertext
has its noise magnitude independent of the input ciphertext. However, by default, it
is necessary to impose restrictions on the type of functions we evaluate or drastically
limit the plaintext space that can be correctly processed. Otherwise, the procedure’s
output will be incorrect and hard to predict.
In this work, we describe two novel algorithms that have no such restrictions. Furthermore, we derive an algorithm that enables a user to evaluate an arbitrary amount
of functions at a computational cost that differs only by a constant amount compared
to a single function. Our methods lead to an evaluation that is between 15 and 31%
faster than previous works while also being conceptually simpler.
ePrint: https://eprint.iacr.org/2024/1376
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .