Free-XOR TFHE via Lazy Bootstrapping

1 Introduction

• PBS is required for every gate in conventional TFHE, so circuit evaluation cost is strongly influenced by how many bootstrappings it requires.PBS evaluates a function on encrypted data while refreshing ciphertext noise.Source: §1 · p. 1
• Prior free-XOR work evaluates XOR by homomorphic addition, but its AND procedure uses two blind rotations and relies on the NTRU hardness assumption.That procedure provides a functionally complete gate set alongside XOR.Source: §1 · p. 1
• The framework evaluates XOR without PBS and all eight symmetric binary Boolean gates with two PBS operations, using an LWE-based construction described as simpler than.The supported gates give identical outputs for inputs (0, 1) and (1, 0).Source: §1 · pp. 1–2
• The proposed evaluation scheme uses two-bit encoding and an index derived from the inputs to select a symmetric gate’s truth-table row.It uses one PBS to compute the index and a second PBS to apply the gate’s truth table.Source: §1 · pp. 1–2
• Experiments report lower circuit evaluation time than standard TFHE gate bootstrapping when XOR gates significantly outnumber symmetric gates.The authors attribute the improvement to PBS-free XOR evaluation, while each symmetric gate requires two PBS operations.Source: §1 · p. 2

Notations.

• The notation section specifies conventions for Boolean encodings, polynomial coefficients, sampling, expectations, Gaussian variables, rounding, and vector inner products.It also defines the complementary error function through the error function.Source: Notations · p. 2

2.1 FHE

• FHE evaluates functions on ciphertexts, while bootstrapping refreshes noisy ciphertexts and supports arbitrarily deep computation.Boolean, arithmetic, and approximate-arithmetic FHE schemes are distinguished by the computations they natively support.Source: §2.1 · p. 2

2.2 TFHE

• TFHE evaluates Boolean circuits over encrypted data and is based on the Learning With Errors problem.The background introduces decision-LWE and search-LWE as two formulations of LWE hardness.Source: §2.2 · p. 3

2.2.2 LWE Encryption Scheme.

• LWE encryption scales a plaintext into Z_q, adds error, and decodes the resulting ciphertext phase to recover the message with overwhelming probability.The error distribution has unbounded support, so correct decoding is not guaranteed for every sample.Source: §2.2.2 · p. 3
• LWE encryption forms a ciphertext by combining the noisy encoded message with the inner product of a random vector and secret key.The ciphertext components are called the mask and body.Source: §2.2.2 · p. 3

Homomorphic Operations.

• Componentwise ciphertext addition implements homomorphic message addition, while accumulated noise can eventually prevent correct decryption and motivate bootstrapping.In TFHE, programmable bootstrapping both reduces noise and evaluates a function on the encoded plaintext.Source: Homomorphic Operations · p. 3

2.2.3 GLWE Encryption Scheme.

• GLWE replaces the LWE space with a polynomial ring and represents the message and error as polynomials encrypted under a polynomial-vector key.The GLWE ciphertext decrypts to a noisy encoded polynomial that is decoded coefficientwise.Source: §2.2.3 · pp. 3–4
• A trivial encryption represents a polynomial without encryption noise by setting the mask to zero and the body to its scaled message.The representation is denoted (0, ΔM).Source: §2.2.3 · p. 4
• Sample extraction constructs an LWE ciphertext encrypting a selected GLWE message coefficient by rearranging ciphertext coefficients.The extracted secret key is obtained by flattening the GLWE secret-key coefficients.Source: §2.2.3 · p. 4

Key Switching.

• Key switching takes a ciphertext under one key and encryptions of that key’s components under another, producing a ciphertext of the same message under the second key.The component encryptions form the key-switching key.Source: Key Switching · p. 4
• The operation homomorphically cancels the original key’s contribution using its encryption under the target key.The paper lists LWE-to-LWE, GLWE-to-GLWE, LWE-to-GLWE, and many-LWE-to-one-GLWE variants.Source: Key Switching · p. 4
• Key switching is denoted KSw(c_k1, KSK) = c_k2, with the output ciphertext under the target key.The key-switching key supplies encryptions of the original key components under the target key.Source: Key Switching · p. 4

Blind Rotation.

• Since X^N = -1, rotations are periodic modulo 2N, and adding N positions negates the resulting polynomial.The negation follows from the ring's negacyclic structure.Source: Blind Rotation · p. 4
• Blind rotation uses encrypted secret-key components to perform conditional polynomial rotations without revealing the encrypted position.The blind rotation key enables these conditional rotations homomorphically.Source: Blind Rotation · p. 4
• The rotation decomposes into an initial rotation by -b, followed by rotations by a_i when s_i = 1 and no rotation when s_i = 0.Blind rotation is described as central and computationally expensive in TFHE.Source: Blind Rotation · pp. 4–5

2.3 Programmable Bootstrapping (PBS)

• Bootstrapping evaluates a target function homomorphically while reducing accumulated ciphertext noise.The resulting ciphertext encrypts the same plaintext, with noise essentially independent of the input ciphertext's noise.Source: §2.3 · p. 5
• A test polynomial encodes a negacyclic function as coefficients so blind rotation and sample extraction can compute its value.Its N coefficients form a lookup table, while the evaluated length-2N sequence is negacyclic.Source: §2.3 · p. 5
• Negacyclicity is structural: a non-negacyclic function on Z2N has no test-polynomial encoding.A function on a domain D ⊆ ZN can instead be extended to a negacyclic function because the domain does not reach the second half of Z2N.Source: §2.3 · p. 5

Recoding Input via Modulo Switching.

• To recode an LWE ciphertext encoding Δm + e ∈ Zq into index range [0, 2N), modulus switching changes modulus q to 2N by scaling and rounding each component.Consequently, the encoded message is rescaled from Δ = q/p to ˜Δ = 2N/p.Source: Recoding Input via Modulo Switching · p. 5
• The switched error combines scaled input noise with modulus-switching rounding error, modeled as independent uniform errors on [-1/2, 1/2].The rounding-error model gives each error mean 0 and variance 1/12.Source: Recoding Input via Modulo Switching · pp. 5–6
• Decoding is correct when the total error magnitude is below N/p, and the analysis uses a Gaussian model to assess failure probability.The target negligible failure probability and the parameters determine the required plaintext modulus.Source: Recoding Input via Modulo Switching · p. 6

Designing Test Polynomials.

• Test-polynomial design adapts the Zp input and output encodings to the Z2N function implemented by the polynomial.The 2N indices are partitioned into blocks assigned scaled outputs; non-negacyclic functions use the preceding construction.Source: Designing Test Polynomials · p. 6

2.3.2 How PBS Works.

• PBS modulus-switches the input, blind-rotates the test polynomial, extracts its constant coefficient, and key-switches the result back to the input key.The resulting ciphertext encrypts h(m); the sample-extracted ciphertext is already modulo q, so no modulus switch back from 2N is needed.Source: §2.3.2 · p. 6

2.3.3 TFHE Boolean Circuits.

• TFHE evaluates standard Boolean gates by applying PBS to a linear combination of shifted-encoded inputs and a corresponding lookup table.The OR combination adds q/8, while the AND combination subtracts q/8 from the sum of the encoded inputs.Source: §2.3.3 · pp. 6–7, Table 1 · p. 7, Table 2 · p. 7

3 Free-XOR Gate Bootstrapping Framework

• Addition modulo 4 evaluates XOR without bootstrapping; the analysis bounds chained XORs by noise and gives about twenty million XORs below failure probability 2^-40.For a target failure probability of 2^-40, the supplied example gives about twenty million chained XORs.Source: §3 · p. 7

3.1 Supporting Other Boolean Gate Types

• The index identifies the truth-table row, supporting eight symmetric gates whose outputs match on (0,1) and (1,0); the other eight gates distinguish those inputs.Supported gates include AND, NAND, OR, NOR, XOR, XNOR, FALSE, and TRUE.Source: §3.1 · pp. 7–8

3.1.1 Encoding.

• A two-bit mapping preserves free XOR through addition modulo 4, while a modulo table groups the 16 encoded input pairs into four equivalent chunks.The index function computes the truth-table index from the mapped inputs.Source: §3.1.1 · p. 8, Table 4 · p. 8

Padding Bit and Headroom.

• Non-negacyclic gate functions require a padding bit, so headroom keeps intermediate additions from carrying into that reserved bit.When a nonlinear gate is evaluated, bootstrapping applies its characteristic function modulo 4 over the headroom range.Source: Padding Bit and Headroom · p. 8

Choosing Headroom.

• Headroom must exceed the largest value reached between bootstrappings while remaining small enough to satisfy the bound imposed by modulus-switching noise.A larger headroom permits more additions between bootstrappings, but the modulus-switching error limits its size.Source: Choosing Headroom · p. 9

3.2 Gate Bootstrapping for Supported Non-linear Boolean Gates

• For supported non-free gates, Π computes parity and G applies the gate function to the indexed inputs; each gate uses two bootstrappings.The index is formed from twice one input plus the parity of the other, and must remain below headroom to avoid the padding bit.Source: §3.2 · p. 9, Figure 1 · p. 9

4 Implementations and Proof of Work

• The Rust implementation uses TFHE-rs and compiles Bristol Fashion circuits into ciphertext circuits for evaluation.An interpreter evaluates the resulting circuits using valid ciphertext inputs.Source: §4 · p. 9

4.1 Bristol Fashion (BF)

• Bristol Fashion represents gates in topological order, specifying each gate's type and input and output wire indices.The first n wire indices are inputs and the final m indices are outputs.Source: §4.1 · p. 9

4.2 Parameters

• The implementation sets headroom H=16; increasing H can reduce bootstrapping frequency but may require parameter changes and increase polynomial and vector dimensions.Jointly optimizing security, computational efficiency, and bootstrapping frequency remains an open engineering problem.Source: §4.2 · p. 9

4.3 Lazy Bootstrapping

• Lazy bootstrapping tracks each wire's maximum possible value and bootstraps input wires when the estimated output would exceed headroom.The overflow condition depends on gate type; for XOR and XNOR, the input with the larger estimate is bootstrapped first.Source: §4.3 · pp. 9–10, Table 5 · p. 10

4.4 Experimental Results

• Approximately 88% speedup is reported on XOR-only circuits, with diminishing gains as the proportion of symmetric gates relative to FreeXOR gates increases.Table 6 reports elapsed times in seconds and compares the approach with bootstrapping after every gate.Source: §4.4 · p. 10, Table 6 · p. 10

• XOR gates use homomorphic addition without immediate programmable bootstrapping (PBS).The encoding reserves headroom for intermediate results, allowing bootstrapping to be deferred until that headroom is about to overflow.Source: §5 · p. 10
• An indexing function identifies a symmetric gate’s truth-table row, then a second PBS evaluates the gate’s functionality.The first PBS computes the index; the second evaluates the gate based on it.Source: §5 · p. 10
• The approach is most efficient for circuits in which XOR gates significantly outnumber symmetric gates.Source: §5 · p. 10