IEEE Computational Intelligence Magazine - August 2022 - 19

PP c;; mm
) =
mm
12
;
;
;
;
q
p
q
p
q
p
R
R
RRmE
12
00
HE operations (additions and multiplications) applied on
,
U qn,
() ,
.
mm mm12 12
mm mER m
12
11
U qn,
01 10RRR mE
+
U qn,
(8)
Having a three-term ciphertext is not a problem, given that
all of the procedures (decryption, addition, and multiplication)
can be modified to work on ciphertexts of arbitrary dimensions.
However, the larger the ciphertexts, the larger their
memory and computational footprint. To address these problems,
the BFV scheme supports an operation called relinearization
[14] which receives as input a ciphertext with size k and
returns a ciphertext with size k - 1, 2 the minimum dimension
allowed. Although relinearization slightly increases the noise in
the ciphertext and requires some additional keys, relinearizing
the ciphertext after every ciphertext-ciphertext multiplication
is generally recommended.
E. Noise Budget
As detailed in Eq. (3), the BFV scheme (similar to other HE
schemes presented in the literature) injects noise into ciphertexts
during the encryption step. This is necessary to guarantee
the probabilistic encryption property of the BFV scheme since
encrypting the same plaintext through two different activations
of the encryption step would lead to two different ciphertexts.
The drawback is that, during homomorphic addition and multiplication
on the ciphertext, noise is added as well as multiplied.
This might lead to a critical scenario where, during
processing, one of the coefficients of the ciphertext is rounded
to an incorrect value during decryption (as in Eq. (4)), hence
failing the decryption phase.
Noise handling is a crucial point in the BFV HE scheme. A
correct evaluation of the number (and type) of operations
allowed on the ciphertexts is crucial in the design of HE-based
processing systems. This is exactly where the noise budget (NB)
comes into play. While providing a formal definition of the NB
is outside of the scope of this paper (see [19] for details), one
can intuitively define it as an indicator of the number of operations
that can be performed on a ciphertext before its decryption
will fail.
Interestingly, the NB is a property of a ciphertext that varies
during the processing pipeline. It is measured as a positive integer
and depends on the parameters H of the BFV scheme. The
NB is initially allocated to the ciphertext immediately after the
encryption step. In general, increasing n will increase the
amount of NB available in a freshly encrypted ciphertext. By
contrast, increasing p and q will increase NB consumption during
homomorphic operations. Identifying the values of H that
guarantee the correct processing of the ciphertexts while
reducing computation and memory complexity is crucial for
HE-based systems, particularly for those that implement deep
learning solutions. This aspect is addressed in Section III.
the ciphertext decrease the NB. As presented in Table III, the
types of operations and operands significantly affect the
amount of reduction to the NB. It is crucial to highlight that
the decryption step on ciphertexts must be conducted before
the NB reduces to 0; otherwise the decryption will fail. Computing
the NB is highly complex, but specific HE tools are
available for its estimation (see [19] for details).
Table IV depicts the effects of H, operations, and operands
on NB consumption. As previously mentioned, the initial NB
increases with n, thus increasing the number of subsequent
operations that can be computed on the ciphertexts. On the
other hand, increasing p will increase the NB consumption of
the HE operations.
F. Example
This section presents an example application of the BFV
scheme. The basic operations of the scheme are implemented
in Python through the scientific computation library NumPy
[22]. The code used in this example has been made available to
the scientific community in the public repository specified in
the Section I.
First, this study defines the encryption parameters H of the
BFV as follows:
n = 16
p = 7
q = 124112
theta = (n, p, q)
TABLE III Noise Budget (NB) consumption, on the basis of
the computed homomorphic operation.
OPERATION
Ciphertext-ciphertext multiplication
Ciphertext-ciphertext addition
Ciphertext-plaintext multiplication
Ciphertext-plaintext addition
NB CONSUMPTION
High
Medium
Low
Very low
TABLE IV Example of NB consumption, using two different
configurations of H = (n, p). The value for q is set
automatically according to the SEAL library [19].
NOISE BUDGET
CIPHERTEXT
Freshly encrypted m1
R
Freshly encrypted m2
R
RR+
mm
RR)
mm
R+
mm
12
mm
R)
12
12
12
H= 2048 15162 (, )
30
30
29
5
30
29
H= 4096 151262
81
81
80
52
81
81
(, )
AUGUST 2022 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 19
IEEE Computational Intelligence Magazine - August 2022

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2022
