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)
剩余33页未读，继续阅读
极正常
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- 新型矿用本安直流稳压电源设计：双重保护电路
- 煤矿掘进工作面安全因素研究：结构方程模型
- 利用同位素位移探测原子内部新型力
- 钻锚机钻臂动力学仿真分析与优化
- 钻孔成像技术在巷道松动圈检测与支护设计中的应用
- 极化与非极化ep碰撞中J/ψ的Sivers与cos2φ效应：理论分析与COMPASS验证
- 新疆矿区1200m深孔钻探关键技术与实践
- 建筑行业事故预防：综合动态事故致因理论的应用
- 北斗卫星监测系统在电网塔形实时监控中的应用
- 煤层气羽状水平井数值模拟：交替隐式算法的应用
- 开放字符串T对偶与双空间坐标变换
- 煤矿瓦斯抽采半径测定新方法——瓦斯储量法
- 大倾角大采高工作面设备稳定与安全控制关键技术
- 超标违规背景下的热波动影响分析
- 中国煤矿选煤设计进展与挑战：历史、现状与未来发展
- 反演技术与RBF神经网络在移动机器人控制中的应用
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
