IEEE Computational Intelligence Magazine - August 2022 - 17

A. Encryption Parameters
of the BFV Scheme
The BFV scheme relies on the following set
,,
H np q@ of encryption parameters:
= 6
❏ n: Polynomial modulus degree;
❏ p: Plaintext coefficient modulus;
❏ q: Ciphertext coefficient modulus.
As detailed in Section II-B, ciphertexts and plaintexts are
The core of the BFV scheme is its ability to support the
computation of additions and multiplications between
ciphertexts and ciphertexts as well as between
ciphertexts and plaintexts.
For example, consider a BFV scheme with the parameters
represented by polynomials in the BFV scheme; these parameters
define the order of the BFV polynomials and the range
of values for their coefficients. Specifically, the parameter n
must be a positive power of 2 and represents the degree of
the cyclotomic polynomial ().xn
()
U
n xx 1n
Rx x (on which the RLWE problem is based).
ppZ
=
Un
In particular, the polynomial
U =+ represents the polynomial modulus. The
plaintext modulus p is a positive integer that represents the
module of the coefficients of the polynomial ring
[]/( )
Finally, the parameter q is a large positive integer (larger than
p) that results from the product of distinct prime numbers. It
represents the modulo of the coefficients of the polynomial
ring in the ciphertext space.
The setting of these parameters as well as their effect on the
noise budget are described and commented on in the rest of
the section.
B. Encoding and Decoding
Throughout the remainder of this section, raw messages ms are
considered unsigned integers. Each number can be transformed
into a BFV polynomial by means of the encoding step. Formally,
in the BFV scheme the encoding step
mmC= H
()
aims to transform m into an n-degree polynomial defined
as follows:
mc xcxc=+g++ 0
n-1
n-1
1
1
in
01f
,, ,
(1)
whose coefficients cis are modulus p, that is, cpN ,
=- where n and p are the polynomial modulus
i ! =
degree and the plaintext coefficient modulus, respectively, as
defined in Section II-A. Several methods for encoding numbers
into polynomials are available in the literature (e.g., integer
encoding and fractional encoding [18]); however, this section
focuses on encoding based on binary representation [19],
which is a widely used encoding mechanism for natural numbers.
The basis of the method is the ability to initially encode m
into an n-bit binary representation. These n bits are considered
the n coefficients
defined in Eq. (1). Hence, c {, }01i
6ccn 10- f
=
,, @ of the n-degree polynomial
with 01f
in
CH
-
=,,
.
Noteworthily, the corresponding decoding step ()m1
based
on binary representation simply refers to the evaluation of the
polynomial m for x = 2:
mm m 2
==CH
-
1() ().
n = 16, p = 7 and q = 874 and assume that one wishes to
encode the following two raw messages: m 71
The binary representation of m 71
= and m 22
mm .xx 111
2
==CH()
++
Similarly, when considering m ,22 = the corresponding plaintext
is
mm x22
==CH
() .
C. Encryption and Decryption
In the BFV scheme, a plaintext m is transformed into a ciphertext
mu
by means of the encryption step (, ),Em kp
H
where kp is
H
the public key. The corresponding decryption step (, )Dm ks
transforms the ciphertext mu into a plaintext m with the priu
vate
key ks.
The public and private keys, which are crucial for the
encryption and decryption steps of the BFV scheme, are generated
by the user before the encryption phase. Specifically, the
secret key ks corresponds to an n-degree polynomial whose
coefficients are randomly selected in the set {, ,}.101ks,
the public key kp is a couple ^h of n-degree polynoGiven
kk
,pp
pp ps qn
== -+ U ,
^ 01h ^6
@
01
mials, which are defined as follows:
kk ,( ),kake a
h
(2)
where a is an n-degree polynomial whose coefficients are randomly
selected in the set {, ,}q01f -
==
over the integers [20].
The encryption step
u = H
mE (, )mkp
aims to transform the plaintext m into the ciphertext m ,u
is a couple (, )mm
01
u PP
01
mm m
ku e
==
=+ ++
U
p01 n,q
q
12
n
; E
p
q
·mk ue
,
E
,
p
@U
cm;
6
which
PP of n-degree polynomials defined as follows:
(, )
(3)
where e1, e2 are n-degree polynomials computed as e, while u is an
n-degree polynomial computed as ks. Notably, in Eq. (3), the sum
operator " + " refers to the sum between polynomials, whereas the
AUGUST 2022 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 17
and e is an n-degree
N 032nv
= .
= over n = 16 bits is
60000000000000111 ;@ hence the corresponding plaintext
becomes
polynomial whose coefficients are randomly selected from a
discrete and bounded Gaussian distribution (, .)
IEEE Computational Intelligence Magazine - August 2022

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