基于多密钥全同态加密方案的无CRS 模型安全多方计算*

唐春明, 胡业周, 李习习

广州大学数学与信息科学学院, 广州510006

1 引言

2 准备工作

2.1 记号

对于自然数n, [n] 代表{1,2,··· ,n}. 小写黑体字母a 代表向量, 大写黑体字母A 代表矩阵. a[i] 表示向量a 中第i 个元素, a 的无穷范数用//a//∞表示, //a//∞=maxi(|a[i]|). 矩阵的无穷范数定义与之类似. (a,b) 代表两个向量的内积, (a|b) 表示两个向量的水平连接. 一个n×m 维全为0 的矩阵用0n×m表示. X 代表一个有限域Ω 中的分布, ω ←X 表示ω 从分布X 随机选取.

2.2 定义与定理

3 GSW 全同态加密方案

本节我们回顾GSW 全同态加密方案的构造、同态操作以及噪音分析. GSW 是由一系列概率时间多项式算法组成, 即GSW = (SetUp,KeyGen,Enc,Dec,Eval), 其中Eval 算法包含AddEval, MultEval,ANADEval.

4 无CRS 的多密钥全同态加密方案

4.1 单密钥密文到多密钥密文

易见//ej//∞≤Bχ. 其中tj为参与方Pj的私钥.

引理2 (扩展安全性) 在LWE 假设成立的情况下, 上述扩展过程是选择明文安全的.

下面我们用两个参与方来简要说明上述扩展过程.

4.2 方案的构造

4.2.1 扩展的正确性

4.3 与KLP 方案的对比

从效率上看, KLP 方案的扩展过程需要对随机矩阵R ∈{0,1}m×m中每一个元素用GSW 全同态加密的加密过程进行加密, 然后生成nmN 个n×m 维矩阵用来计算辅助信息X. 而本文中的方案只需要对R 进行一次编码, 之后通过Link 算法即可得到辅助信息X.

从内存上看, KLP 方案每一个参与方在生成扩展密文时需要需要计算存储m2+nmN 个n×m 维矩阵. 而本文中的方案只需计算存储一个m×ml 维矩阵以及N 个n×m 维矩阵即可.

从噪音上看,KLP 方案最终的解密噪音为2(m4+m)mNBχ.而本文中的解密噪音(2+m)mNBχ,远远小于KLP 方案中的解密噪音.

5 基于门限MFHE 的三轮安全多方计算协议

利用上述的门限多密钥全同态加密方案构造一个三轮安全多方计算协议, 该协议既不需要CRS 也不需要复杂的参数设置. 而且三轮的轮数在无CRS 模型中是最低的, 因为协议中没有CRS, 每一个参与方完全独立的生成自己的密钥对, 并在协议开始前分发出去, 这至少需要一轮, 接下来如文献[9] 类似, 构造一个两轮的协议用来生成与发布密文以及计算发布部分解密, 故至少需要三轮来完成整个协议. 该协议在面对一个半恶意的敌手是安全的, 这一类型的敌手要比恶意敌手弱但比半诚实的敌手强. 我们根据文献[7]给出半恶意敌手的定义.

定义8 (半恶意敌手) 一个半恶意的敌手可以腐败任意多个诚实方, 除了标准磁带外, 还拥有一个证据磁带, 该敌手必须将自己代表的诚实方的输入记录到证据磁带上. 敌手可以根据输入和一定的随机性来决定是否忠实的履行协议.

对于一个半恶意的模型, 可以通过理想现实模型来证明其安全性. 即通过一系列游戏来证明理想现实.

5.1 协议的构造

f({0,1})N→{0,1} 是一个可计算函数, d 代表函数f 的电路深度. 假设共有N 个参与方, 用{Pi}i∈[N]表示.

输出: 每个参与方 Pi收到其他参与方的部分解密 {pj}j̸=i, 运行最终解密算法得到: y ←MFHE.FinDec(p1, ··· , pN). 输出y =f(x1,··· ,xN).

5.2 协议的安全性

6 结论

本文基于LWE 假设提出了一个无CRS 模型的多密钥全同态加密方案, 并以此方案为基础, 构造了无CRS 模型的三轮安全多方计算协议, 并且在面对一个半恶意的敌手是安全的. 如第4 节所描述该协议的轮数在无CRS 模型中是最优的, 文中4.3 节将该方案与原有方案做对比, 无论是效率还是内存开销, 本文中的方案都优于原有方案, 而且解密噪音也远远低于原有方案.

该协议接下来需要研究的是如何在一个无CRS 模型中构造一个可以抵抗恶意敌手的安全多方计算协议; 如何在协议执行过程中, 提高数据在传输过程中的安全性以及会话的协同性.