唐春明, 胡业周, 李习习

广州大学数学与信息科学学院, 广州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 的三轮安全多方计算协议……

登录APP查看全文