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 .