IEEE Computational Intelligence Magazine - August 2022 - 18

operator " · " represents the pointwise multiplication between a
scalar value and a polynomial (i.e., all of the coefficients of m are
multiplied by the factor
6qp ,@ which represents the floor of the
division between q and p). Note that this factor is larger than one
since q is larger than p. The two polynomials representing mu
are
of order n and with coefficients that are modulus q.
Some noise is injected into the ciphertext by e1, e2, and u. In
particular, u is a " mask " that actually hides the message in the
ciphertext. Notably, these noise terms are randomly selected
every time the encryption step is activated, and thus, they are
responsible for guaranteeing the probabilistic encryption ability
of the encryption scheme, which is a relevant property from a
security point of view [21].
The decryption step of a ciphertext mu
operates as follows
[14], [19]:
Dm , []km
q
H == +
^hu ss ,q
;; mm k
+
,
p PP U01 n mE
(4)
p
where :6 h is the round operation. In the decryption phase,
mm k
6PP @s01 nU q is scaled by the factor pq . All of the coefficients
are modulus p (after being rounded).
For the sake of clarity, the role of the secret key in the
decryption step requires further elaboration. Expanding Eq. (3)
w.r.t. the public key ks leads to:
ucm;
6
maku eu e
s
=- -+ ++
U
12 q
n
; E ,.
p
q
·maue
,
E
q
The encoded message m, multiplied by 6qp ,@ is included in
the first term of the ciphertext, suitably hidden by a mask
(
-ak ),us
eu e1
and perturbed by noise ().-+ The mask is also
present in the second term (i.e., au) of the ciphertext together
with the noise (e2). The core of the decryption phase resides in
the ability of the user to encrypt m by means of ks and by the
fact that ks can be multiplied for the second term m1
P of the
ciphertext. Intuitively, multiplying m1
P with ks and summing
with m0
P removes the mask u from the raw message m, as long
as the error terms-accumulated during the pipeline of homomorphic
operations-are not too big. An example of this
encryption/decryption phase is presented in Section II-F.
D. Homomorphic Operations in the BFV Scheme
The BFV scheme allows the computation of additions and
multiplications between ciphertexts, between ciphertexts and
plaintexts, and between plaintexts. The addition and multiplications
in the BFV scheme are as follows:
❏ " modulus x 1n
+ " , where the polynomial that is the outcome
of the operation is modulus the cyclotomic polynomial
()
U =+n xx ;1n
❏ " coefficient modulus " p;
where the operands are plaintexts;
❏ " modulus x 1n
U =+n xx ;1n
+ " , where the polynomial that is the outcome
of the operation is modulus the cyclotomic polynomial
()
18 IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | AUGUST 2022
n
@Un,
while the decoding of mm leads to ()=
Note that, with modulus x 1n
12
)
operations
7
/ m ,
i =1
1
% m2
1
i
16
=
(5)
(6)
introduce an " overflow " in the processing, thereby leading to
incorrect results. In fact, when one of the coefficients of the
polynomial becomes equal to or larger than p at the end of the
processing, an incorrect result will be obtained due to the
modulo p operation. In particular, in Eq. (5), all of the coefficients
of the polynomial become 7 at the end of the processing.
Hence, when the modulo 7 operation is applied, the coefficients
become 0 leading to the following incorrect result:
6 ++ =+ +
77 70 00
2
xx xx .
@7
By contrast, in Eq. (6), the problem is related to the modulo
U operation performed on the polynomial. Indeed, the
degree of the polynomial becomes 16 during the last multiplication,
leading to the following loss of information:
6 16@U16 =- 1.
x
When an overflow occurs in the processing, the final
decrypted value will differ from the correct one. The overflow
issue, described here on additions and multiplications between
two plaintexts, also affects the operations that comprise ciphertexts,
which are described as follows.
The addition between two ciphertexts (e.g., m1
P and m2
P) is
as simple as computing their element-wise sum (recall that a
ciphertext is a couple of polynomials):
PP 66@@RR RR
mm ,.mm mm00 nn
12 12 12
+= ++
UU
,,
qq
11
`j (7)
By contrast, the multiplication between two ciphertexts
produces a three-term ciphertext:
2
C
H
-
)
1 mm 1412
.
+ and p, the following two
❏ " coefficient modulus " q;
where at least one of the two operands is a ciphertext.
Now, this example continues with m 71
=
becomes, in polynomial form,
[]
16
C +=H
-
and m 22
=
considering
the addition and multiplication of these two plaintexts
in the BFV scheme. In particular, the addition of mm
12
+
mm xx21+= ++U12 ,7
2
,
while the corresponding decoding of mm becomes
1 () .mm 912
12
+
Similarly, the multiplication of m1 and m2
becomes
[]U12 ,7
16
mm xx x,
) =+ +
32
IEEE Computational Intelligence Magazine - August 2022

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