Reference Paper ：Bootstrapping in FHEW-like Cryptosystems . This blog is a summary of the paper which is the main reference for the `BinFHE`

implementation in OpenFHE. The main contribution is to realize the homomorphic standardized variant of **TFHE**, that is, to expand the private key sampling range of TFHE from binary to any sampling range, such as ternary , and compared FHEW and TFHE when the private key sampling range is the same. Evaluate the bootstrapping speed, bootstrapping key size and other parameters of the two.

Bootstrapping in FHEW-like Cryptosystems是 OpenFHE 中 BinFHE 实现的主要参考论文。主要贡献在于实现了TFHE 的同态标准化变体，即将 TFHE 的私钥采样范围从 binary 扩展到任意采样范围，比如 ternary ，以及对比了 FHEW 、 TFHE 在私钥采样范围相同时，评估二者的 bootstrapping 速度、bootstrapping key size 等参数。

## Basic Ring LWE

**Annotations**

Let be the th cyclotomic ring, for , and . We identify ring elements with the corresponding coefficient vectors in and .

Encoding of in MSB : encode as .

Decoding arbitrary :

Basic Ring LWE symmetric encryption of (the encoding of) a message under key as：

where is chosen uniformly at random, and is chosen from a discrete Gaussian distribution of parameter . Also marked as or

Decryption of Ring LWE ：

Homomorphic multiplication operation (allowed only when d is small)

## Basic RGSW

**Annotations**

Vector of basis decomposition Ring LWE (also called RLEV):

where the base is usually small enough to support homomorphic multiplication between large ciphertext.

Homomorphic multiplication operation with large with -bounded component polynomials :

**RGSW Ciphertext**：**Magic Properties**:Trivial ciphertext of s : .

No secret information form of :

Also ciphertexts can be equivalently written as

where is the powers-of-B “gadget matrix”. For simplicity, PALISADE implements the RGSW cryptosystem directly using equation (2), but multiplication between RGSW ciphertexts is best analyzed using the modular definition (1).

## Homomorphic Multiplication

Given and one computes

This is an encryption of the product , **with an additional error term** . For this operation to be effective, RGSW encryption is usually restricted to small messages , typically , so that . This multiplication operation has type

Extended component-wise :

## Bootstrapping*

Usually, bootstrapping is processed on ciphertexts having the form where and , and keys are vectors , possibly chosen from a subset of .

The core component : cryptographic accumulator .

- Initialize: , setting the content of ACC to any known value
- Update: ACC , modifying the content of the accumulator from to , where , and is given encrypted under .
- Extract: , returning an encryption of function applied to the current content of the accumulator ACC .

The key for bootstrapping is called evaluation key , refreshing key, bootstrapping key and etc.

**High-level procedure** : decryption by and rounding by .

**FHEW/TFHE Bootstrapping** :

**FHEW**: The AP bootstrapping procedure [4] supports basic updates ACC for arbitrary . Then, ACC is implemented by providing (in the bootstrapping key) encryptions of multiples of the secret key elements , taking the binary expansion of , and then executing ACC for all such that .**TFHE/CGG**I : The GINX bootstrapping procedure [24] supports basic updates ACC where is arbitrary, but is a single bit. Then, for an arbitrary secret , one can execute ACC for all .

Features :

- AP has a time-space trade-off. is written to a base (with digits ), and the bootstrapping key includes encryptions for all and .
- Only support binary expansion of the secret key .

## Ring LWE Accumulators*

The last section does not involve details of the cryptographic accumulator and here we will introduce the designing of Ring LWE accumulators which makes the rounding function trivial and fast.

The main idea of the FHEW accumulators ：work in a cyclotomic ring of order , and represent values as , where is the th cyclotomic polynomial. Since has multiplicative order in , addition in the exponent of is performed modulo . Following [20], we assume is a power of 2 , and use the ring for a sufficiently larger modulus .

The ring is used to implement the RLWE, RLWE’ and RGSW encryption schemes . The smaller modulus is only used for the LWE ciphertext given as input to the bootstrapping procedure.

**Points**

- The ciphertext modulus is only used for LWE ciphertext!
- RLWE, RLWE’ and RGSW modulus is .
- Polynomial quotient : where
- Embed the ring into

**FHEW/CGGI accumulators**

Store the value as . And the programmable function must satisfy :

If the function is known in advance, the value can be alternatively stored as

If only an LWE ciphertext is needed at the end of the computation, one can set the accumulator :

The final version in practice :

**Init ACC and Extract LWE Ciphertext**

### FHEW : AP Update

The update operation is the most complicated and expensive in bootstrapping and it differs among the two homomorphic cryptosystems. This section focuses on the FHEW ACC Update.

In , each secret value is encrypted as

The updating process where :

- Decompose with base :
- ACC for , using the RLWE RGSW RLWE multiplication operation.

**Combine things together , how does cryptographic accumulator change during bootstrapping with LWE ciphertext being **?

Init ACC ( Init LUT polynomial, rotated by ):

From a homomorphic perspective :

Update ACC times, in each step:

From a homomorphic perspective :

After n times update :

Extract the constant , from a homomorphic perspective :

since the LUT maps all valid in mega-case to .

### TFHE/CGGI : GINX Update

In , each secret value is encrypted as :

Decompose : each secret value needs to be expressed as a subset-sum . (with ) where is an appropriate subset of ( if is sampled in , ).

For any such , the secret encryption function is defined as

The update operation is computed by sequentially updating

for , where

A faster version which takes only one homomorphic multiplication is :

**Combine things together , how does cryptographic accumulator change during bootstrapping with LWE ciphertext being **?

Init ACC ( Init LUT polynomial, rotated by ):

From a homomorphic perspective :

Update ACC times, in each step:

From a homomorphic perspective :

After n times update :

Extract the constant , from a homomorphic perspective :

since the LUT maps all valid in mega-case to .

### Summary

The two bootstrapping processes differ in the update operation.

- The FHEW/AP decomposes the ciphertext with certain pre-determined base . Thus , we do not require the secret key distribution to be binary . Here we briefly discuss the time-space trade-off.
- The bootstrapping decomposition base is large : then the bootstrapping key size will be smaller but the product increases thus increasing the bootstrapping time !
- The secret key distribution has no influences in the the bootstrapping key size and running time.

- The TFHE/GINX decomposes the secret key with subset . Specifically, the initial TFHE utilizes the binary distribution which maximally eliminates the running time but sacrifices the security level. All the variants of TFHE relies on the CMux gate with the choice bit being the secret and therefore, they demands the private key to be encrypted bit by bit which means the plaintext of must belong to .

Some parameters

- , small (LWE) modulus;
- , lattice parameter for the LWE scheme;
- , RLWE/RGSW modulus used in the core bootstrapping procedure based on an accumulator;
- , LWE/RLWE modulus used for key switching;
- , ring dimension for RLWE/RGSW;
- , gadget base for digit decomposition in each accumulator update, which breaks integers into digits;
- , gadget base used for key switching, which breaks integers into digits;
- , gadget base in FHEW/AP (not used in TFHE/GINX), which breaks integers into digits.

## Homomorphic Rounding and Bitwise Gate

We conclude with a discussion of the function used by the extraction function at the end of bootstrapping.

**NAND Gate**

- The NAND of two ciphertexts and .
**Homomorphic Addition**: obtain an encryption of with noise less than .**Bootstrapping**: ciphertext is homomorphically decrypted using the bootstrapping procedure .

Rounding functions implemented by the function ( Look-Up table ) :

- Rounds to the closest multiple of , then
- maps , (and, for completeness, also )
- finally multiplies the resulting bit by the scaling factor . (Remember that the extraction procedure returns an LWE ciphertext modulo . A ciphertext modulo can be obtained using key/modulus switching.)

Other bitwise gates :

The process :

## Implementation Results

The latest acceleration updated in 2022 Oct (paper).