基础

生成可逆矩阵对的算法

  • 输入:矩阵维数
  • 输出:一对互逆矩阵(\(I_1,I_2\))

一种高效的同态加密方案及其应用-解读-LMLPHP

算法的目的是构造一对互逆矩阵, 同时由于每一步中的置换参数都是随机生成的, 所以可使矩阵的
元素不具备任何特征, 可以通过改变随机变换的次数来调整效率和随机性.

密钥交换技术

来源于BGV方案,作用是将一组密文 - 私钥转换到一组新的密文 -私钥, 同时保证解密正确性.

  • 输入:密钥\(S\)
  • 输出:新密钥\(S'\)和矩阵\(M\)

一种高效的同态加密方案及其应用-解读-LMLPHP

假设原始的密钥和密文为\(S\)\(c\),则经过密钥交换后输出满足:新密钥和新密文为\(S'\)\(c'=Mc+e \approx Mc\),其中\(e\)很小可以忽略,可以看出密钥交换产生的新密文,噪音增加了一点。

正确性

一种高效的同态加密方案及其应用-解读-LMLPHP

其中\(I\)\(m*m\)的单位矩阵。

同态方案

密钥生成

  • 输入:参数m
  • 输出:私钥\(S\)和公钥\(M\)

一种高效的同态加密方案及其应用-解读-LMLPHP

其中,矩阵\(wI\)视为明文向量对应的私钥进行了一次密钥转换, 得到公、私钥,所以,假设\(wI\)对应的明文为\(c\)\(S'\)对应的明文为\(c'=Mc\),则:

\[Sc'=SMc=wIc \to SM/w=I\]

加密

  • 输入:公钥\(M\),明文\(x\)
  • 输出:密文\(c\)

一种高效的同态加密方案及其应用-解读-LMLPHP
加密过程中除计算新密文外, 还引入了一个噪声向量, 从而使得加密结果形式上满足 LWE 问题.

解密

  • 输入:私钥\(S\),密文\(c\)
  • 输出:明文\(c\)

一种高效的同态加密方案及其应用-解读-LMLPHP

其中\(\left \lceil a\right \rfloor_q\)表示对向量或矩阵\(a\)中各元素在模\(q\)的域中取最近整数.(四舍五入)。

解密正确性的参数要求

为保证解密的正确性, 需要对算法中的各参数做出限制. 下面分析解密过程:
一种高效的同态加密方案及其应用-解读-LMLPHP

要保证解密正确性需要限制\(|Se/w|< 1/2\) , 其中符号\(|a|\)表示向量或矩阵\(a\)的元素的最大绝对值. 将该限制条件进一步加强, 然后展开得到:
一种高效的同态加密方案及其应用-解读-LMLPHP

所以噪声\(e\)的上限:
一种高效的同态加密方案及其应用-解读-LMLPHP

在该限制条件下, 可以保证解密正确. 在实际应用中, 噪声往往会随着同态计算的进行而不断增大, 而
当噪声足够大时, 就会造成解密失败. 所以在实际应用中, 可以噪音上限的公式中, 得到一个密文可
以进行的同态计算深度\(L\), 然后再应用中加以限制, 以此来保证同态计算的结果可以顺利解密.(Leveled-FHE)。

同态计算

加法

1、用同一公钥\(M\)加密两个等长的明文向量\(x_1,x_2\)有:
一种高效的同态加密方案及其应用-解读-LMLPHP
2、将上面两式相加有:
一种高效的同态加密方案及其应用-解读-LMLPHP

只需给噪声向量 \(e_1, e_2\)合适的限制条件即可得到:
一种高效的同态加密方案及其应用-解读-LMLPHP

只要满足:\(|S(e_1+e_2)|<1/2\),就可以解密正确。

线性变换

1、根据解密结构\(x=\left \lceil Sc/w\right \rfloor_q\)可得:\(Gx=G\left \lceil Sc/w\right \rfloor_q=\left \lceil GSc/w\right \rfloor_q=Dec(GS,c)\),即密文\(c\)可以看作是明文\(Gx\)在公钥\(GS\)下加密的。
2、然后利用密钥交换技术,将\(GS\)作为输出,得到新密钥\(S'\),及\(M'=Trans(GS)\),此时\(S'\)对应的新密文为\(c'=M'c+e'\),根据密钥交换的性质有:

\[S'c'=S'(M'c+e')=S'M'c+S'e'=GSc+S'e' \approx GSc\]

3、用新密钥\(S'\)对新密文解密:
一种高效的同态加密方案及其应用-解读-LMLPHP

可以看出上面的噪音不仅有第一次加密时引入的噪声\(e\), 还有密钥转换过程中引入的新噪声\(e'\)以及因进行线性变换而引入的噪声\(|GSe+S'e'|\). 将上面解密过程展开有:
一种高效的同态加密方案及其应用-解读-LMLPHP

所以解密正确的条件是:
一种高效的同态加密方案及其应用-解读-LMLPHP
随着计算深度的增加噪声的大小也快速增大, 直至无法正确解密.

总结一下流程:
现在给出一个密文\(c\),想计算其线性变换\(Gc\),然后解密后相当于对应的明文\(x\)做线性变换\(Gx\)
1、将密文\(c\),对应的私钥\(S\),变为\(GS\),作为密钥交换的输入
2、密钥交换输出新私钥\(S'\),得到新密文\(c'\)
3、用新私钥\(S'\)解密新密文\(c'\)得到明文\(Gx\)

加权内积

关于加权内积没看太懂。

安全性分析

密钥安全

密钥安全就是不能根据公钥\(M\)推测出私钥\(S\)或者在一定程度上模拟出解密过程,即不能仅从公钥和密文就可以解出明文!

分析

观察公钥\(M=P_mM_t\),是否能从\(M\)中推断出\(P_m\)或者\(M_t\)?
因为\(P_m\)是一个随机可逆矩阵,想直接构造出\(P_m\)是困难的。可行的办法就是\(P_m^{-1}M=M_t\),即需要知道\(P_s\),可以尝试随机取\(P_s\),但矩阵规模很大时,很难选取,所以选择合适的矩阵规模,是影响方案安全性的重要参数。

语义安全

模拟方案是否满足IND-CPA(不可区分的选择明文攻击):
一种高效的同态加密方案及其应用-解读-LMLPHP
若攻击者能以概率为\(Pr=1/2+\varepsilon\)获胜,则攻击者同样也可以以相同的概率求出\(x\)
已知$ c_i,M_i,c_i=M_ix+e_i,0 \leq i<n$
该问题明显就是LWE问题了,LWE问题被Regev证明是困难的,所以该方案的安全性规约到LWE困难问题上

04-25 18:10