![](https://csdnimg.cn/release/download_crawler_static/11168917/bg7.jpg)
5.3 Multiplication
Consider the Multiply function as described in Section 4.3. The first step that outputs the
intermediate ciphertext (c
0
, c
1
, c
2
) defines a function Evaluator::multiply, and causes the
ciphertext to grow in size. The second step defines a function that we call relinearization, im-
plemented as Evaluator::relinearize, which takes a ciphertext of size 3 and an evaluation
key, and produces a ciphertext of size 2, encrypting the same underlying plaintext. Note that
the ciphertext (c
0
, c
1
, c
2
) can already be decrypted to give the product of the underlying plain-
texts (see Section 5.2), so that in fact the relinearization step is not necessary for correctness
of homomorphic multiplication.
It is possible to repeatedly use a generalized version of the first step of Multiply to produce
even larger ciphertexts if the user has a reason to further avoid relinearization. In particular,
let ct
1
= (c
0
, c
1
, . . . , c
j
) and ct
2
= (d
0
, d
1
, . . . , d
k
) be two SEAL ciphertexts of sizes j + 1 and
k + 1, respectively. Let the ciphertext output by Multiply(ct
1
, ct
2
), which is of size j + k + 1,
be denoted ct
mult
= (C
0
, C
1
, . . . , C
j+k
). The polynomials C
m
∈ R
q
are computed as
C
m
=
"$
t
q
X
r+s=m
c
r
d
s
!'#
q
.
In SEAL the function Multiply means this generalization of the first step of multiplication.
It is implemented as Evaluator::multiply.
5.4 Relinearization
The goal of relinearization is to decrease the size of the ciphertext back to (at least) 2 after
it has been increased by multiplications as was described in Section 5.3. In other words,
given a size k + 1 ciphertext (c
0
, . . . , c
k
) that can be decrypted as was shown in Section 5.2,
relinearization is supposed to produce a ciphertext (c
0
0
, . . . , c
0
k−1
) of size k, or – when applied
repeatedly – of any size at least 2, that can be decrypted using a smaller degree decryption
function to yield the same result. This conversion will require a so-called evaluation key (or
keys) to be given to the evaluator, as we will explain below.
In BFV, suppose we have a size 3 ciphertext (c
0
, c
1
, c
2
) that we want to convert into
a size 2 ciphertext (c
0
0
, c
0
1
) that decrypts to the same result. Suppose we are also given a
pair evk =
[−(as + e) + s
2
]
q
, a
, where a
$
← R
q
, and e ← χ. Now set c
0
0
= c
0
+ evk[0]c
2
,
c
0
1
= c
1
+ evk[1]c
2
, and define the output to be the pair (c
0
0
, c
0
1
). Interpreting this as a size 2
ciphertext and decrypting it yields
c
0
0
+ c
0
1
s = c
0
+ (−(as + e) + s
2
)c
2
+ c
1
s + ac
2
s = c
0
+ c
1
s + c
2
s
2
− ec
2
.
This is almost what is needed, i.e. c
0
+ c
1
s + c
2
s
2
(see Section 5.2), except for the additive
extra term ec
2
. Unfortunately, since c
2
has coefficients up to size q, this extra term will make
the decryption process fail.
Instead we use the classical solution of writing c
2
in terms of some smaller base w (see
e.g. [11, 9, 7, 21]) as c
2
=
P
`
i=0
c
(i)
2
w
i
. Instead of having just one evaluation key (pair) as
above, suppose we have + 1 such pairs constructed as in Section 4.3. Then one can show
that instead setting c
0
0
and c
0
1
as in Section 4.3 successfully replaces the large additive term
that appeared in the naive approach above with a term of size linear in w.
This same idea can be generalized to relinearizing a ciphertext of any size k+1 to size k ≥ 2,
as long as a generalized set of evaluation keys is generated in the EvaluationKeyGen(sk, w)