全同态加密算法有哪些（全同态加密：CKKS）
参考文献：
Cheon J H, Kim A, Kim M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]//International conference on the theory and application of cryptology and information security. Springer, Cham, 2017: 409-437. 全同态加密：BGV 全同态加密：BFV CKKS explained seriesCKKS
不论是 LSB 编码的 BGV ，还是 MSB 编码的 BFV ，它们的同态运算都是对
Z
t
\mathbb Z_t
Zt 上明文的精确计算 ，因为密文中的明文空间和噪声空间是分离的 。例如 ，在 BGV 中是t
e
+
m
te+m
te+m ，在 BFV 中是δ
m
+
e
\delta m+e
δm+e 。但是 ，这种精确计算是在同余意义下的 ，如果将明文视为实数 ，那么实际上同态运算时的噪声破坏了明文的 MSB⌊
m
/
t
⌋
\lfloor m/t \rfloor
⌊m/t⌋ ，仅保留了 LSB[
m
]
t
[m]_t
[m]t ，如图：而 CKKS 关注近似计算 ，它使得在密文中的明文空间和噪声空间是不分离的 ，噪声位于明文空间的 LSB 位置 。也就是说 ，在 CKKS 中是
m
+
e
m+e
m+e ，同态运算破坏明文的 LSB ，但不破坏其 MSB 。这也是合理的 ，可以将噪声破坏 LSB 视为浮点运算的精度误差 。类似 BGV 做模切换 ，来使得噪声规模不会指数级增长；CKKS 也要做重缩放（rescaling） ，使得消息规模不会随电路深度而指数级增长 ，同时移除了 LSB 上的部分浮点误差 。如图：Canonical Embedding
符号：
Φ
M
(
x
)
∈
Z
[
x
]
\Phi_M(x) \in \mathbb Z[x]
ΦM(x)∈Z[x] ，M
M
M 次单位根的分圆多项式 ，度数为N
=
ϕ
(
M
)
N = \phi(M)
N=ϕ(M)R
:
=
Z
[
x
]
/
(
Φ
M
(
x
)
)
R := \mathbb Z[x]/(\Phi_M(x))
R:=Z[x]/(ΦM(x)) ，数域Q
[
x
]
/
(
ϕ
M
(
x
)
)
\mathbb Q[x]/(\phi_M(x))
Q[x]/(ϕM(x)) 的子环（离散子群）R
q
=
R
/
q
R
R_q = R/qR
Rq=R/qR ，商环Z
q
[
x
]
/
(
Φ
M
(
x
)
)
\mathbb Z_q[x]/(\Phi_M(x))
Zq[x]/(ΦM(x))S
:
=
R
[
x
]
/
(
Φ
M
(
x
)
)
S := \mathbb R[x]/(\Phi_M(x))
S:=R[x]/(ΦM(x)) ，分圆环（cyclotomic ring） ，其中元素a
(
x
)
a(x)
a(x) 的系数构成向量a
⃗
=
(
a
,
⋯
,
a
N
−
1
)
∈
R
N
\vec a = (a_0,\cdots,a_{N-1}) \in \mathbb R^N
a=(a0,⋯,aN−1)∈RN∥
a
∥
:
=
∥
a
⃗
∥
∞
\|a\| := \|\vec a\|_{\infty}
∥a∥:=∥a∥∞ ，环元素的无穷范数∥
a
∥
1
:
=
∥
a
⃗
∥
1
\|a\|_1 := \|\vec a\|_1
∥a∥1:=∥a∥1 ，环元素的L1 范数Z
M
∗
:
=
{
x
∈
Z
M
:
g
c
d
(
x
,
M
)
=
1
}
\mathbb Z_M^* := \{x \in \mathbb Z_M:gcd(x,M)=1\}
ZM∗:={x∈ZM:gcd(x,M)=1} ，乘法群ξ
M
:
=
e
x
p
(
−
2
π
i
/
M
)
\xi_M := exp(-2\pi i/M)
ξM:=exp(−2πi/M) ，M
M
M 次本原单位根规范嵌入（canonical embedding）
σ
:
S
→
C
N
\sigma: S \to \mathbb C^N
σ:S→CN定义为
σ
(
a
)
:
=
(
a
(
ξ
M
j
)
)
j
∈
Z
M
∗
\sigma(a) := (a(\xi_M^j))_{j \in \mathbb Z_M^*}
σ(a):=(a(ξMj))j∈ZM∗ 其中a
∈
Q
[
x
]
/
(
ϕ
M
(
x
)
)
⊂
S
a \in \mathbb Q[x]/(\phi_M(x)) \sub S
a∈Q[x]/(ϕM(x))⊂S∥
a
∥
∞
c
a
n
:
=
∥
σ
(
a
)
∥
∞
\|a\|_\infty^{can} := \|\sigma(a)\|_\infty
∥a∥∞can:=∥σ(a)∥∞ ，规范嵌入范数（canonical embedding norm）C
R
T
M
CRT_M
CRTM ，M
M
M 次本原单位根ξ
M
j
,
j
∈
Z
M
∗
\xi_M^j,\, j \in \mathbb Z_M^*
ξMj,j∈ZM∗ 上的 Vandermonde 矩阵（可逆） ，使得C
R
T
M
⋅
a
⃗
=
(
a
(
ξ
M
j
)
)
j
∈
Z
M
∗
=
σ
(
a
)
CRT_M \cdot \vec a = (a(\xi_M^j))_{j \in \mathbb Z_M^*} = \sigma(a)
CRTM⋅a=(a(ξMj))j∈ZM∗=σ(a)（规范嵌入是线性变换）∥
U
=
(
u
i
j
)
∥
∞
:
=
max
i
∑
j
∣
u
i
j
∣
\|U=(u_{ij})\|_\infty := \max_{i} \sum_j |u_{ij}|
∥U=(uij)∥∞:=maxi∑j∣uij∣ ，矩阵的无穷范数c
M
:
=
∥
C
R
T
M
−
1
∥
∞
c_M := \|CRT_M^{-1}\|_\infty
cM:=∥CRTM−1∥∞ ，环常数（ring constant） ，仅与M
M
M 有关性质：
∀
a
,
b
∈
S
\forall a,b \in S
∀a,b∈S ，有∥
a
⋅
b
∥
∞
c
a
n
≤
∥
a
∥
∞
c
a
n
⋅
∥
b
∥
∞
c
a
n
\|a \cdot b\|_\infty^{can} \le \|a\|_\infty^{can} \cdot \|b\|_\infty^{can}
∥a⋅b∥∞can≤∥a∥∞can⋅∥b∥∞can∀
a
∈
S
\forall a \in S
∀a∈S ，有∥
a
∥
∞
c
a
n
≤
∥
a
∥
1
\|a\|_\infty^{can} \le \|a\|_1
∥a∥∞can≤∥a∥1∀
a
∈
S
\forall a \in S
∀a∈S ，有∥
a
∥
∞
≤
c
M
⋅
∥
a
∥
∞
c
a
n
\|a\|_\infty \le c_M \cdot \|a\|_\infty^{can}
∥a∥∞≤cM⋅∥a∥∞canGaussian Distributions
定义线性子空间：
H
:
=
{
z
⃗
=
(
z
j
)
j
∈
Z
M
∗
∈
C
N
:
z
j
=
z
ˉ
−
j
,
∀
j
∈
Z
M
∗
}
\mathbb H := \{ \vec z = (z_j)_{j \in \mathbb Z_M^*} \in \mathbb C^N:\, z_j = \bar z_{-j},\, \forall j \in \mathbb Z_M^* \}
H:={z=(zj)j∈ZM∗∈CN:zj=zˉ−j,∀j∈ZM∗}也就是所有满足共轭约束的向量 。可以验证 ，作为内积空间（inner product space）
H
≅
R
N
\mathbb H \cong \mathbb R^N
H≅RN ，关于幺正矩阵（unitary basis matrix ，酉矩阵）
U
=
[
1
2
I
i
2
J
1
2
J
−
i
2
I
]
∈
C
N
×
N
U = \begin{bmatrix} \frac{1}{\sqrt 2}I & \frac{i}{\sqrt 2}J\\ \frac{1}{\sqrt 2}J & \frac{-i}{\sqrt 2}I\\ \end{bmatrix} \in \mathbb C^{N \times N}
U=[21I21J2iJ创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！