本文介绍: 一般地,FHE 需要很大的模数 QQQ,将它写作 Q=∏i=1LqiQ=prod_{i=1}^L q_iQ=∏i=1L​qi​,满足 qi=1(mod2N)q_i=1pmod{2N}qi​=1(mod2N),我们简记 Qi=q1⋯qiQ_i=q_1cdots q_iQi​=q1​⋯qi​,集合 {qi}{q_i}{qi​} 称为 RNS basis,它们的大小至多为 646464 比特我们希望 FHE 的全部运算都是单精度的(现代计算机机器字),也就是全部运算都在 RNS 下完成,而

]PQ)
计算步骤就是 RNS-BV 和 RNS-GHS 的恰当组合

  1. 分解

    c

    1

    c_1

    c1

    D

    ~

    Q

    (

    c

    1

    )

    tilde D_Q(c_1)

    D~Q(c1),并扩展

    P

    Q

    PQ

    PQ

  2. P

    Q

    PQ

    PQ计算

    c

    t

    B

    ct_B’

    ctB

  3. 缩放

    Q

    Q

    Q,再加上

    c

    0

    c_0

    c0,得到

    c

    t

    B

    ct_B

    ctB

具体流程,以及对应复杂度

在这里插入图片描述

Complexities and Size

GHS 选取:BFV 的

k

l

k approx l

kl,BGV 的

k

l

kapprox l’

kl

Hybrid 选取:BFV 的

α

k

,

d

α

l

alpha approx k, dalpha approx l

αk,dαl,BGV 的

α

k

,

d

α

l

alphaapprox k’, dalphaapprox l’

αk,dαl

复杂度为:

在这里插入图片描述

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注