Conversion Between (R)LWE

参考文献:

  1. [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping[J]. Cryptology ePrint Archive, 2018.
  2. [BGGJ20] Boura C, Gama N, Georgieva M, et al. Chimera: Combining ring-lwe-based fully homomorphic encryption schemes[J]. Journal of Mathematical Cryptology, 2020, 14(1): 316-338.
  3. [CDKS21] Chen H, Dai W, Kim M, et al. Efficient homomorphic conversion between (ring) LWE ciphertexts[C]//International Conference on Applied Cryptography and Network Security. Cham: Springer International Publishing, 2021: 460-479.
  4. [LHH+21] Lu W, Huang Z, Hong C, et al. PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption[C]//2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021: 1057-1073.

[MS18] 为了实现均摊 FHEW 自举,提出了 Ring packing 技术:将多个 LWE 密文(行矢)堆叠为

(

A

,

b

)

(A,b)

(A,b),然后按列转化为多项式

a

j

(

x

)

,

b

(

x

)

a_j(x), b(x)

aj(x),b(x),使用 Key-Switch 执行同态线性解密

A

E

(

s

)

+

b

Acdot E(s)+b

AE(s)+b私钥被加密在多项式的常数项),最终获得打包了

μ

(

x

)

=

j

μ

j

x

j

mu(x)=sum_j mu_jx^j

μ(x)=jμjxj 的单个 RLWE 密文。虽然它是 Coeff Packing 的,但是 [MS18] 中的同态 InvDFT 的目标是加速同态的多项式乘法(线性解密部分),而非 SIMD 打包并行。但是其中的 SwK 是对于 LWE 私钥的各个分量分别用 RLWE 加密的

R

L

W

E

s

(

s

i

g

j

)

RLWE_{s'}(s_i cdot g_j)

RLWEs(sigj),规模大、速度慢。计算过程中不需要用到同态旋转(主要的开销是秘钥切换),仅仅是对于

E

(

s

)

E(s)

E(s) 的同态线性运算。

[BGGJ20] 提出的 Chimera 也使用类似的堆叠技术,将 TLWE 打包转换到 RLWE 密文上。不过它将堆叠出的矩阵

C

=

(

A

,

b

)

C=(A,b)

C=(A,b) 直接乘以 InvDFT,于是

(

I

n

v

D

F

T

C

)

s

=

I

n

v

D

F

T

(

μ

(

x

)

)

(InvDFT cdot C) cdot s=InvDFT(mu(x))

(InvDFTC)s=InvDFT(μ(x)),这就将各个

μ

j

mu_j

μj 编码到了明文槽。它的 SwK 也是各个私钥分量分别被加密在系数上

R

G

S

W

s

(

s

i

)

RGSW_{s'}(s_i)

RGSWs(si),规模很大(GB 级别)

[CDKS21] 提出了新的 LWE 的 Key-Switch 技术(后文简记 KS),将 LWE 密文嵌入到 RLWE 密文上,对应的 SwK 将LWE 私钥作为单个多项式做 RLWE 加密

R

L

W

E

s

(

s

(

x

)

g

j

)

RLWE_{s'}(s(x) cdot g_j)

RLWEs(s(x)gj),从而极大的提高了 KS 的速度(两个数量级)。需要使用分圆域的自同构的某些特殊性质,消除一些杂项。推广这个 KS 过程,可以获得 LWE 打包到 RLWE 的过程,不过它也是 Coeff Packing 的(还应该使用 Coeff-to-Slot 过程将它们编码到明文槽)。令

N

N

N 是 RLWE 的维度,打包

n

=

N

n=N

n=N 个 LWE 密文,复杂度为

O

(

N

)

O(N)

O(N)同态自同构

O

(

N

)

O(N)

O(N) 次同态数乘。

之后的 Pegasus 也使用密文堆叠技术,对于私钥

s

s

s 的密文做线性变换,来实现 LWE-to-RLWE 过程。同态线性变换过程中,采取对角线乘法(旋转+阿达玛),LWE 私钥作为一个整体被加密在明文槽上

R

L

W

E

s

(

E

c

d

(

s

,

Δ

)

)

RLWE_{s'}(Ecd(s,Delta))

RLWEs(Ecd(s,Δ)),规模大大减小(MB 级别),同态解密的结果直接在明文槽上。令

N

N

N 是 RLWE 的维度,打包

n

=

N

n=N

n=N 个 LWE 密文,复杂度为

O

(

N

)

O(sqrt{N})

O(N

)同态旋转(由若干个自同构组成,完全分裂的二的幂分圆环只需要一个),

O

(

N

)

O(N)

O(N) 次同态数乘。

Conversion Between RLWE

Tower of Cyclotomic

m

=

2

L

+

1

m=2^{L+1}

m=2L+1 是二的幂,

N

=

ϕ

(

m

)

=

2

L

N=phi(m)=2^L

N=ϕ(m)=2L 也是二的幂,分圆域

K

=

Q

(

ζ

m

)

Q

[

X

]

/

(

X

N

+

1

)

K=mathbb Q(zeta_m) cong mathbb Q[X]/(X^N+1)

K=Q(ζm)Q[X]/(XN+1),分圆整数环

R

=

Z

[

ζ

m

]

Z

[

X

]

/

(

X

N

+

1

)

R=mathbb Z[zeta_m] cong mathbb Z[X]/(X^N+1)

R=Z[ζm]Z[X]/(XN+1),为了区分不同维度我们记为

K

N

,

R

N

K_N,R_N

KN,RN

根据代数理论,域扩张

K

/

Q

K/mathbb Q

K/Q 都是 Galois 扩张,Galois 群

G

a

l

(

K

/

Q

)

Z

m

=

{

1

,

3

,


,

2

N

1

}

Gal(K/mathbb Q) cong mathbb Z_m^*={1,3,cdots,2N-1}

Gal(K/Q)Zm={1,3,,2N1},自同构:

τ

d

:

ζ

m

ζ

m

d

,

d

Z

m

tau_d: zeta_m to zeta_m^d, forall dinmathbb Z_m^*

τd:ζmζmd,dZm
域的迹:

T

r

K

/

Q

:

a

K

τ

G

a

l

(

K

/

Q

)

τ

(

a

)

Q

Tr_{K/mathbb Q}: a in K mapsto sum_{tau in Gal(K/mathbb Q)} tau(a) in mathbb Q

TrK/Q:aKτGal(K/Q)τ(a)Q
根据代数知识,

T

r

K

/

Q

Tr_{K/mathbb Q}

TrK/Q

Q

mathbb Q

Q-线性映射,并且满足

  • T

    r

    K

    /

    Q

    (

    1

    )

    =

    [

    K

    :

    Q

    ]

    =

    N

    Tr_{K/mathbb Q}(1)=[K:mathbb Q]=N

    TrK/Q(1)=[K:Q]=N

  • T

    r

    K

    /

    Q

    (

    X

    i

    )

    =

    0

    ,

    i

    0

    Tr_{K/mathbb Q}(X^i)=0, forall i neq 0

    TrK/Q(Xi)=0,i=0

对于分圆塔:

K

=

K

N

K

N

/

2

K

1

=

Q

K=K_N ge K_{N/2} ge cdots ge K_1=mathbb Q

K=KNKN/2K1=Q
其中

K

n

,

n

=

2

l

K_n,n=2^l

Kn,n=2l 可以作为

K

N

K_N

KN 的子域(

R

n

R

N

R_n le R_N

RnRN 类似),设置

Y

=

X

N

/

n

Y=X^{N/n}

Y=XN/n

K

n

=

{

i

[

n

]

a

i

Y

i

:

a

i

Q

}

K

N

K_n = left{sum_{i in [n]} a_i Y^i: a_i in mathbb Qright} subseteq K_N

Kn=

i[n]aiYi:aiQ

KN
基于分圆塔,可以将迹分解

T

r

K

/

Q

=

T

r

K

2

/

K

1

T

K

N

/

K

N

/

2

Tr_{K/mathbb Q} = Tr_{K_2/K_1} circ cdots circ T_{K_N/K_{N/2}}

TrK/Q=TrK2/K1TKN/KN/2
易知,相邻的域扩张的次数为

2

2

2仅包含一个非凡自同构(另一个是恒等映射):

G

a

l

(

K

2

l

/

K

2

l

1

)

=

{

τ

1

K

2

l

,
  

τ

2

l

+

1

K

2

l

}

,
  

1

l

L

Gal(K_{2^l}/K_{2^{l-1}}) = {tau_1|_{K_{2^l}},,, tau_{2^l+1}|_{K_{2^l}}},,, 1 le l le L

Gal(K2l/K2l1)={τ1K2l,τ2l+1K2l},1lL
其中的

τ

2

l

+

1

K

2

l

tau_{2^l+1}|_{K_{2^l}}

τ2l+1K2l 是自同构映射

τ

2

l

+

1

G

a

l

(

K

/

Q

)

tau_{2^l+1} in Gal(K/mathbb Q)

τ2l+1Gal(K/Q) 限制在

K

2

l

K

N

K_{2^l} subseteq K_N

K2lKN 上,容易验证它是

K

2

l

K_{2^l}

K2l

K

2

l

1

K_{2^{l-1}}

K2l1-自同构。进一步的,简记

n

=

2

l

n=2^l

n=2l

Y

=

X

N

/

n

Y=X^{N/n}

Y=XN/n

K

n

/

Q

K_n/mathbb Q

Kn/Q 的扩张元,那么有:

T

r

K

n

/

K

n

/

2

(

Y

i

)

=

{

2

Y

i

,

2

i

0

,

2

i

Tr_{K_{n}/K_{n/2}}(Y^i) = left{begin{aligned} 2Y^i, &&forall 2mid i\ 0, &&forall 2nmid i\ end{aligned}right.

TrKn/Kn/2(Yi)={2Yi,0,∀2i∀2i
因此,映射

μ

K

n

T

r

K

n

/

K

n

/

2

(

μ

)

K

n

/

2

mu in K_n mapsto Tr_{K_{n}/K_{n/2}}(mu) in K_{n/2}

μKnTrKn/Kn/2(μ)Kn/2,记号

a

b

a|b

ab 表示 “恰好整除”,

  1. 将系数

    μ

    [

    i

    ]

    ,

    (

    2

    N

    /

    n

    )

    i

    mu[i], (2N/n)|i

    μ[i],(2N/n)i加倍

  2. 将系数

    μ

    [

    i

    ]

    ,

    (

    N

    /

    n

    )

    i

    mu[i], (N/n)|i

    μ[i],(N/n)i清零

  3. 元素

    μ

    K

    n

    K

    N

    mu in K_n subseteq K_N

    μKnKN 的其他系数本来就是零,保持

我们定义

[

N

]

=

{

0

,

1

,


,

N

1

}

[N]={0,1,cdots,N-1}

[N]={0,1,,N1}一组划分(子域的系数索引),

I

k

:

=

{

i

[

N

]

:

2

k

i

}

,
  

0

k

<

L

I_k := { i in [N]: 2^k|i },,, 0 le k< L

Ik:={i[N]:2ki},0k<L
特别地设置

I

L

=

{

0

}

I_L={0}

IL={0},容易验证

[

N

]

=

k

I

k

[N] = bigcup_k I_k

[N]=kIk

对于

d

=

2

l

+

1

,

1

l

L

d=2^l+1, 1le l le L

d=2l+1,1lL,简记

i

=

2

k

j

I

k

i=2^kj in I_k

i=2kjIk,其中

j

j

j 是奇数,

i

d

=

2

k

+

l

j

+

2

k

j

=

{

2

k

(

2

l

j

+

j

)

I

k

0

k

L

2

k

j

=

i

(

m

o

d

2

N

)

,

k

>

L

l

2

L

+

2

k

j

=

N

+

i

(

m

o

d

2

N

)

,

k

=

L

l

i cdot d = 2^{k+l}j + 2^kj = left{begin{array}{ll} 2^k(2^lj+j) in I_k &forall 0 le k le L\ 2^kj = i pmod{2N}, &forall k>L-l\ 2^L+2^kj = N+i pmod{2N}, &k=L-l\ end{array}right.

id=2k+lj+2kj=

2k(2lj+j)Ik2kj=i(mod2N),2L+2kj=N+i(mod2N),∀0kLk>Llk=Ll
因此,

τ

d

:

ζ

i

ζ

i

d

tau_d: zeta^i to zeta^{icdot d}

τd:ζiζid 是对各个索引

I

k

I_k

Ik 做了符号置换(signed permutation),

i

I

k

,

r

I

k

,

τ

d

(

X

i

)

=

±

X

r

forall i in I_k,exist r in I_k,tau_d(X^i) = pm X^r

iIk,rIk,τd(Xi)=±Xr。特别地对于

k

L

l

k ge L-l

kLl 的那些

I

k

I_k

Ik

τ

d

(

X

i

)

=

{

X

i

,

i

k

>

L

l

I

k

X

i

,

i

I

L

l

.

.

.

o

t

h

e

r

w

i

s

e

tau_d(X^i) = left{begin{aligned} X^i, &&forall i in bigcup_{k>L-l}I_k\ -X^i, &&forall i in I_{L-l}\ ... &&otherwise end{aligned}right.

τd(Xi)=

Xi,Xi,...ik>LlIkiILlotherwise
因此,映射

μ

K

N

μ

+

τ

d

(

μ

)

K

N

mu in K_N mapsto mu+tau_d(mu) in K_N

μKNμ+τd(μ)KN

  1. 将系数

    μ

    [

    i

    ]

    ,

    2

    L

    l

    +

    1

    i

    mu[i],2^{L-l+1}|i

    μ[i],2Ll+1i加倍

  2. 将系数

    μ

    [

    i

    ]

    ,

    i

    I

    L

    l

    mu[i], i in I_{L-l}

    μ[i],iILl清零

  3. 其他系数的变化较为复杂

LWE-to-LWE

LWE 密文

(

b

,

a

)

Z

q

1

+

N

(b,a) in mathbb Z_q^{1+N}

(b,a)Zq1+N,私钥

s

Z

N

s in mathbb Z^N

sZN,线性解密获得相位(不考虑纠错),

μ

0

=

b

+

a

,

s

(

m

o

d

q

)

mu_0 = b+langle a,s rangle pmod q

μ0=b+a,s(modq)
执行 KS 时,抽象思路是

K

=

{

L

W

E

s

(

s

i

)

}

K={LWE_{s'}(s_i)}

K={LWEs(si)},然后同态解密获得

L

W

E

s

(

μ

0

)

LWE_{s'}(mu_0)

LWEs(μ0),但是这么做的复杂度太高了。[CDKS21] 提出了一种新的 KS 过程:

  1. a

    a

    a 转化为多项式

    a

    (

    x

    )

    =

    ι

    (

    a

    )

    R

    N

    ,

    q

    a(x) = iota(a) in R_{N,q}

    a(x)=ι(a)RN,q,其中的映射

    ι

    :

    Z

    N

    R

    N

    iota: mathbb Z^N to R_N

    ι:ZNRN 是将向量作为多项式系数

  2. s

    s

    s 转化为多项式

    s

    (

    x

    )

    =

    τ

    1

    ι

    (

    s

    )

    R

    N

    s(x) = tau_{-1} circ iota(s) in R_N

    s(x)=τ1ι(s)RN,其中的

    τ

    1

    tau_{-1}

    τ1 是因为多项式乘积是向量反卷积

那么,获得的

(

b

,

a

(

x

)

)

R

N

,

q

2

(b,a(x)) in R_{N,q}^2

(b,a(x))RN,q2 可以视为

s

(

x

)

s(x)

s(x) 加密的 RLWE 密文,容易验证

μ

(

x

)

=

b

+

a

(

x

)

s

(

x

)

R

N

,

q

mu(x) = b+a(x)s(x) in R_{N,q}

μ(x)=b+a(x)s(x)RN,q它的常数项

μ

[

0

]

mu[0]

μ[0] 恰好就是

μ

0

mu_0

μ0

因此我们可以使用

K

=

{

R

L

W

E

s

(

s

(

x

)

g

i

)

}

K={RLWE_{s'}(s(x) cdot g_i)}

K={RLWEs(s(x)gi)} 作为 SwK,执行 RLWE 的秘钥切换,最后提取出常数项对应的 LWE 密文。其中的

g

=

(

g

1

,


,

g

d

)

g=(g_1,cdots,g_d)

g=(g1,,gd) 是 Gadget Vector,可使用 [BGV12] 的 Base decomposition 或者 [BEHZ16] 的 Prime decomposition(用于兼容 RNS 系统)。

具体算法为:

在这里插入图片描述

LWE Key-Switch 的噪声为

e

k

s

=

g

1

(

c

1

)

,

e

e_{ks} = langle g^{-1}(c_1), e rangle

eks=g1(c1),e,其中

e

χ

σ

e gets chi_sigma

eχσ 是 SwK 的噪声。为了兼容 RNS 系统,我们使用素数分解

g

1

:

a

{

[

a

]

q

i

R

N

,

q

i

}

g^{-1}: a mapsto {[a]_{q_i} in R_{N,q_i}}

g1:a{[a]qiRN,qi},那么可以计算出

e

k

s

e_{ks}

eks 各个系数的方差

V

k

s

1

12

N

σ

2

i

q

i

2

V_{ks} le frac{1}{12}Nsigma^2 cdot sum_i q_i^2

Vks121Nσ2iqi2
易知 LWE-to-LWE 的噪声就是 Key-Switch 的噪声。

LWE-to-RLWE

上述的 LWE-to-LWE 过程中,产生的

c

t

ct'

ct 并非是有效 RLWE 密文(相位只有常数项是有意义的,其他位置都是无效数据)。[CDKS21] 使用迹

T

r

K

/

Q

Tr_{K/mathbb Q}

TrK/Q 来消除

X

i

,

i

0

X^i,i neq 0

Xi,i=0 的系数,只保留常数项(缩放因子

N

N

N)。

直接计算

T

r

K

/

Q

Tr_{K/mathbb Q}

TrK/Q 需要分别计算各个

τ

d

,

d

Z

m

tau_d, din mathbb Z_m^*

τd,dZm,共计需要

N

N

N 个自同构映射(每一次都需要做 KS 过程)。因此,借助分圆塔将

T

r

K

/

Q

Tr_{K/mathbb Q}

TrK/Q 分解,成为

L

=

log

N

L=log N

L=logN 个相邻分圆域的迹

T

r

K

2

l

/

K

2

l

1

Tr_{K_{2^l}/K_{2^{l-1}}}

TrK2l/K2l1 的组合,这样就只需要计算

log

N

log N

logN 个非凡自同构。

具体算法为:

在这里插入图片描述

为了消除

N

N

N 缩放因子,可以预先对输入的 LWE 密文缩放

[

N

1

]

q

[N^{-1}]_q

[N1]q 因子,从而上述算法的输出自然地消除了它们。

因为自同构

τ

d

tau_d

τd 是保长的,因此不会导致噪声过度膨胀。同态迹的噪声是

V

a

r

1

3

(

(

N

n

)

2

1

)

V

k

s

Var le frac{1}{3}((frac{N}{n})^2-1) cdot V_{ks}

Var31((nN)21)Vks
选取

n

=

1

n=1

n=1,LWE-to-RLWE 的噪声就是

V

a

r

1

3

(

N

2

1

)

V

k

s

Var le frac{1}{3}(N^2-1) cdot V_{ks}

Var31(N21)Vks

LWEs-to-RLWE

假如我们希望将相位是

μ

j

,

j

[

n

]

mu_j, j in [n]

μj,j[n] 的多个 LWE 密文打包到单个 RLWE 密文中:直接使用上述的转换得到

c

t

j

ct_j

ctj,然后计算

c

t

=

j

[

n

]

c

t

j

Y

j

,

Y

=

X

N

/

n

ct' = sum_{j in [n]} ct_j cdot Y^j, Y=X^{N/n}

ct=j[n]ctjYj,Y=XN/n,那么它的相位就是:

μ

=

N

j

[

n

]

μ

j

Y

j

R

n

R

N

mu' = N cdot sum_{j in [n]} mu_j Y^j in R_n subseteq R_N

μ=Nj[n]μjYjRnRN
然而上述算法的计算效率和噪声增长都不算好。[CDKS21] 提出了 FFT-style 递归算法:假设

n

=

2

l

n=2^l

n=2l,为了计算

μ

mu'

μ,可以将

μ

j

mu_j

μj 分为大小

2

l

1

2^{l-1}

2l1 的两组,分别计算出

μ

e

v

e

n

=

N

/

2

j

[

n

/

2

]

μ

2

j

Y

2

j

R

n

/

2

μ

o

d

d

=

N

/

2

j

[

n

/

2

]

μ

2

j

+

1

Y

2

j

R

n

/

2

begin{aligned} mu_{even}' &= N/2 cdot sum_{j in [n/2]} mu_{2j} Y^{2j} in R_{n/2}\ mu_{odd}' &= N/2 cdot sum_{j in [n/2]} mu_{2j+1} Y^{2j} in R_{n/2}\ end{aligned}

μevenμodd=N/2j[n/2]μ2jY2jRn/2=N/2j[n/2]μ2j+1Y2jRn/2
但是实际上我们只需要计算出

μ

e

v

e

n

,

μ

o

d

d

R

N

mu_{even},mu_{odd} in R_N

μeven,μoddRN,使得它们的

Y

2

j

Y^{2j}

Y2j 系数组成了

μ

e

v

e

n

,

μ

o

d

d

R

n

/

2

mu_{even}',mu_{odd}' in R_{n/2}

μeven,μoddRn/2,然后将

μ

o

d

d

mu_{odd}

μodd 旋转

Y

Y

Y 加到

μ

e

v

e

n

mu_{even}

μeven 上,并使用自同构

τ

d

,

d

=

2

l

+

1

tau_{d}, d=2^l+1

τd,d=2l+1 来消除

μ

o

d

d

mu_{odd}

μodd 那些恰好被旋转到

μ

e

v

e

n

mu_{even}'

μeven 位置上的杂项

μ

=

(

μ

e

v

e

n

+

Y

μ

o

d

d

)

+

τ

d

(

μ

e

v

e

n

Y

μ

o

d

d

)

mu = (mu_{even} + Y cdot mu_{odd}) + tau_d(mu_{even} - Y cdot mu_{odd})

μ=(μeven+Yμodd)+τd(μevenYμodd)
由于

Y

μ

o

d

d

-Y cdot mu_{odd}

Yμodd 的有效系数

μ

2

j

+

1

-mu_{2j+1}

μ2j+1 是在

Y

2

j

+

1

Y^{2j+1}

Y2j+1 上,因此

τ

d

tau_d

τd 将它们取反为

μ

2

j

+

1

mu_{2j+1}

μ2j+1 ,而那些被旋转到

Y

2

j

Y^{2j}

Y2j 的杂项

e

-e

e 则保持不变,正好和

Y

μ

o

d

d

Y cdot mu_{odd}

Yμodd 添加到

μ

e

v

e

n

mu_{even}

μeven 上的杂项

e

e

e 相互消除。最终,相位

μ

R

N

mu in R_N

μRN 的那些

Y

j

Y^j

Yj 的系数恰好是

N

μ

j

N cdot mu_j

Nμj,只要再消除其他的杂项就可以得到

μ

R

n

mu' in R_n

μRn,这里可以使用

T

r

K

N

/

K

n

Tr_{K_N/K_n}

TrKN/Kn 来消除它们。

具体算法为:

在这里插入图片描述

这个算法 Step 2 需要

n

1

n-1

n1 次自同构,step 3 需要

log

(

N

/

n

)

log(N/n)

log(N/n) 次自同构,均摊成本为

n

+

log

(

N

/

n

)

1

n

frac{n+log(N/n)-1}{n}

nn+log(N/n)1,只要打包的 LWEs 够多

n

=

Ω

(

log

N

)

n=Omega(log N)

n=Ω(logN),均摊成本仅为

O

(

1

)

O(1)

O(1)(但是打包

n

2

10

n ge 2^{10}

n210 个 LWEs 的延迟应该挺高了?)

注意到

μ

j

mu_j

μj 是打包在系数上的,一般 FHE 可能需要使得消息是打包在明文槽里的,这可以使用 [GHS12] [HS15] [HHC19] 的 Coeff-to-Slot 技术进行转换。[CDKS21] 说这些转换的速度特别快(真的么?秒的量级吧,不算快),因此主要开销还是在 LWEs-to-RLWE 上面。

可以证明 LWEs-to-RLWE 的噪声也是

V

a

r

1

3

(

N

2

1

)

V

k

s

Var le frac{1}{3}(N^2-1) cdot V_{ks}

Var31(N21)Vks

Lightweight Communication

三种转换的效率和噪声:

在这里插入图片描述

优势:

  • 原始的 KS 过程,对于前两个参数,执行时间为

    203

    203

    203

    1628

    1628

    1628 毫秒,因此嵌入到 RLWE 后的效率提升了

    2

    2

    2 个数量级(例如

    1.03

    1.03

    1.03 毫秒)

  • 噪声仅为

    O

    (

    log

    N

    )

    O(log N)

    O(logN)-bit,因此可以使用 LWE 密文,留出足够的噪声空间,

    b

    Z

    q

    b in mathbb Z_q

    bZq 的大部分空间都可用于存储消息(例如

    389

    23

    389-23

    38923 比特)

对于云计算场景,我们使用对称版本的 LWE 加密方案,那么多个密文的

a

j

Z

q

N

a_j in mathbb Z_q^N

ajZqN 完全可以被替代为随机种子,

a

j

=

P

R

F

(

s

e

e

d

,

j

)

a_j=PRF(seed,j)

aj=PRF(seed,j),这导致了 Rate 高达

1

o

(

1

)

1-o(1)

1o(1) 的对称加密。在同态运算之前,需要同态解密,因为 LWE-based 是 FHE 友好的(只需要部分的同态解密,不必纠错),直接使用上述的 LWEs-to-RLWE 就可以转化为合适的 FHE 密文(这三种转换都是保护相位的,通用于任意的 FHE 方案)

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>