多密钥全同态加密的研究现状与发展趋势.pdf
《多密钥全同态加密的研究现状与发展趋势.pdf》由会员分享,可在线阅读,更多相关《多密钥全同态加密的研究现状与发展趋势.pdf(11页珍藏版)》请在文库网上搜索。
1、第 卷第 期 年 月南 京 邮 电 大 学 学 报(自 然 科 学 版)():多密钥全同态加密的研究现状与发展趋势祁正华,何菲菲,张海桃,谭小辉南京邮电大学 计算机学院,江苏 南京()摘要:全同态加密是隐私保护的一种技术,可以使数据在密文状态下进行运算且运算结果解密之后与在明文状态下的运算结果一致。多密钥全同态加密允许在不同密钥下加密的密文之间进行同态操作。加密方案中存在密钥交换、密文扩展等影响运算效率的多项式函数,而且投入实际应用的方案需具备良好的计算效率。以同态加密的 个发展阶段为分水岭,分别梳理每一阶段的多密钥全同态加密的基本构造流程并分析学者们对其进行的核心优化方法。最后简要讨论多密钥
2、全同态加密方案面临的问题并展望未来可能的优化方向。关键词:全同态加密;容错学习问题;近似特征向量中图分类号:文献标志码:文章编号:(),()收稿日期:;修回日期:本刊网址:基金项目:国家自然科学基金()资助项目作者简介:祁正华,女,博士,副教授,引用本文:祁正华,何菲菲,张海桃,等多密钥全同态加密的研究现状与发展趋势南京邮电大学学报(自然科学版),():(),;,:;全同态加密(,)的思想源于“隐私同态”,由 等在 年首次提出。指在不解密的情况下对密态数据进行各种运算,其结果在解密后与对明文进行相应运算的结果是一样的(见图)。同态加密的本质是图 所示的交换图表。真正从根本上解决了将数据及操作委
3、托给第三方时的保密问题。图 同态加密交换图 随着 和 相继被破解而双双陨落,基于格的密码学成为后量子时代抗量子密码的重要组成部分。方案大多是以格上困难问题作为基础,从而 也是后量子密码(,)的组成之一。目前,基于格的逐渐成为欧美国家在密码领域争夺的“战略制高点”,能够在大数据与云计算等新型服务模式下发挥重要作用。年,由 实验室的 构造了第一个真正意义的 方案,方案的设计是基于理想格()上的有界编码问题(,)和稀疏子集和问题(,)。年,等提出 方案,首次利用容错学习(,)假设实现了 并在 假设下实现了。方案采用重线性化技术和密钥交换技术降低了密文的噪声,优化了 提出的方案,但同时由于密钥交换技术
4、需要在公钥生成阶段引入额外的信息,也因此使 得 方 案 的 存 储 开 销 增 大。年,等又提出了 方案,该方案同样也使用了密钥交换技术,但不需要压缩解密电路,提高了算法的计算效率,同时也降低了方案的安全性假设。之后,等首次利用近似特征向量的方法,提出了密文形式为矩阵的 方案(方案),且该方案未使用密钥交换技术,因此减少了存储开销,同时由于矩阵相乘不会改变维数,进而不会使得密文相乘的噪声大幅增加。以上方案都是单密钥加密方案,不能满足不同密钥密文之间的运算,安全多方计算(个参与方共同计算一个函数,计算完毕后每个参与方只知道自己的输入输出)在全同态加密方面得不到应用。年,等提出了第一个多密钥全同态
5、加密()方案,支持对不同用户(不同密钥)的密文进行任意的同态运算,且运算之后的结果由参与计算的所有用户联合解密,可以较好地解决多用户密文联合计算的问题。该方案建立在一个与 相关的非标准假设上,但该方案的复杂度太高,且复杂度随着用户的增长呈指数增长。年,等基于 方案构造了一个 方案,方案的安全性可以规约到 问题,该方案是第一个建立在标准假设上的多密钥全同态加密方案。年,等简化了 等的方案,同样是基于 方案、安全性归约到 问题假设,不同之处在于 等扩展了方案的结构,使得扩展之后的方案可以进行一轮交互的分布式计算,但不足之处在于该方案只允许单跳运算。为了解决这个问题,等构造了拥有多跳的,不必提前获得
6、参与方的信息,且与 等构造的方案相比,方案生成的密文尺寸更短。与此同时,等同样基于 方案设计出了多跳的,它允许参与方动态的加入,可支持任意数量的运算以及多项式级别的参与方参与运算。为提高多跳的 的同态运算效率,荀艳梅等基于 等的 方案并结合密钥策略属性基全同态加密,构造了一个多跳多策略属性基全同态短密文加密方案,且该方案的密文扩展更容易实现。年,等基于 方案构造 方案,方案对密文长度进行了缩减,提高了运算效率,同时也提出了一个直接解密协议,解除了计算密文只能由所有参与方的私钥解密的限制,但也只限于理论层面,还未投入到实际应用。为了再次提高全同态加密方案的计算效率,同年,等基于 方案提出了一个
7、方案,首次对全同态加密进行了概念验证。基本概念 符号说明对于一个自然数 ,表示,表示小于 但最接近于 的整数,表示大于 但最接近于 的整数,表示对 四舍五入近似取整,表示整数集,表示模 剩余类。表示向量中的第 个元素,表示矩阵中第 行第 列的元素,表示矩阵和向量的水平连接,表示两个向量的内积。对于分布,表示 从分布 中均匀取值。对于向量 (,),范数是指 ,无穷范数是指 (,),范数是指 ,若无下标则记为 范数。令()为分圆多项式,则 ()()表示分圆多项式环,环中元素可表示为 。相关定理定理 容错学习问题()。对于一个秘密向量,在 上的 分布,指的是均第 期祁正华,等:多密钥全同态加密的研究
8、现状与发展趋势匀选取 ,选取 ,输出(,)。定理 判定性容错学习问题()。设(,)为 个相互独立的采样,每个采样都是按照以下两种方式生成的:()从 中随机取样;()从分布,中取样。问题是指判定(,)中的每个样本是从哪种方式中取样的。定理 环上容错学习问题(,)。对于一个秘密向量 ,分布,是指定义为 上按如下方式生成的概率分布,随机选取 ,服从概率分布,计算(,)。定理 判定性容错学习问题()。判断(,)是从分布,中采样还是从 中采样。定理,问题是指难以区分以下两个多项式,一是多项式 ,其中 且在 上可逆,;二是在 上随机均匀采样得到多项式。定理 一个整数上的分布,如果 (),称该分布是 有界的
9、,其中()是一个可忽略函数。定理 设 (,),矩阵 ,则对任意的,均存在一个随机有效的可计算函数:,使(),同时 为关于参数()的亚高斯随机向量,且 。例如,若(),有 矩阵 存在 (),且 。定理 很容易扩展到矩阵上,如定理 所示。定理 设 (,),矩阵 ,则对任意的 ,均存在一个随机有效的可计算函数:,使(),同时矩阵的任意行向量 均为关于参数()的亚高斯随机向量,且 。例如,若 ,矩 阵同 定 理,存 在,且 ,或 。关键技术模交换技术():模交换技术可以将模 下的密文 转换成较小的模()下密文,保证在同样私钥正确解密条件下,噪声规模减小 倍,即 (,):输入 和一个更小的模数,输出的一
10、个密文无限接近于 ()且满足 。密钥交换技术():将对应的密文由(解密密钥为)转换成为密文 (解密密钥为)。比 特 分 解 技 术:比 特 分 解 技 术 是 指 用()和()这两个函数对数据进行比特位展开。令 ,则其具体表达分别为(,):输入多项式 (,)和 模,输 出(,),其中,为 进行二元比特分解之后的第 比特。(,):输入多项式 (,),输 出(,)。对于多项式,容易验证(,),(,),。例如,若 (,),(,),则(,)(,)。(,)(,)(,),(,),。自举()技术:当同态操作进行至噪声达到阈值而无法再进行操作时,将此时的密文与对应私钥的密文进行同态解密的操作。即将自己解密函数
11、作为 算法中的输入函数,将达到噪声上限的密文与该密文解密秘钥中的每一位加密结果作为 算法中的输入密文,则执行 算法会生成一个与该密文对应相同明文的“新鲜”密文,从而可以继续进行密文同态运算。当密文再次达到噪声上限时,可以再进行一次同态解密运算,依次递归,在 安全假设下,即可获南京邮电大学学报(自然科学版)年得纯 方案。自举后可以得到支持继续同态操作的低噪声密文。自举是目前最有效的消减密文噪声的操作,也是迄今为止实现全同态加密的唯一途径。自举算法的形式化描述如下:设加密方案中存在两对密钥对(,)和(,)、明文为,则令 为 关于 的密文、(,)表示用 逐比特加密 得到,并将 添加至加密方案的公钥中
12、。令解密电路为,自举算法执行流程如图 所示。图 自举算法执行流程图 格上困难问题格是指 维空间 具有周期性结构的点的集合。近似最短向量问题:定义格的任意一个格基,近似因子 (),则近似最短向量问题是指找到一个非零格基向量,使得对于任意的非零,()成立。近似最近向量问题:给定格的一个格基、目标向量,找出一个格基向量,使得对于任意的,成立。定义格 的逐次最小量为()(,)其中,(,)表示以原点为球心、为半径的闭球,()表示格 生成的线性空间。最短线性无关向量问题:寻找格中 个线性无关向量,使得对于任意的 ,()成立。全同态加密及多密钥全同态加密基于全同态加密的多密钥全同态加密的发展过程同全同态加密
13、一样分为 个阶段,下面分析各阶段的核心方法。以 的突破性工作为基础这一阶段全同态加密方案构造的思路是:首先构造一个部分()方案,即方案仅支持低多项式次数的密文同态计算。然后,在稀疏子集和问题的假设下,通过“压缩解密电路”使方案变成“自举的”,从而通过迭代调用自举技术,对随着同态运算达到噪声阈值的新密文进行同态解密来约减噪声,使其允许至少再进行一次同态运算,最后在循环安全性假设()下获得真正意义上的 方案。在同态运算过程中噪声的主要来源是同态乘法运算,其产生的噪声呈指数级别增长。为解决噪声增长过快问题,需要将密文和密钥重新按位加密,之后再将得到的密文输入同态解密电路中,但这要求当同态运算电路深度
14、大于解密电路深度时要通过压缩电路和逐比特加密降低噪声来实现全同态,这也限制了同态解密技术的使用。由此可见,这一阶段仅实现单密钥全同态加密过程就十分复杂,因此,多密钥全同态加密不适合基于此阶段的方案进行构造。此 阶 段 的 代 表 性 方 案 有 ()、()、()等。基于 和 的多密钥全同态加密方案 这一阶段全同态加密方案的构造思路是先构造一个层次型的同态加密方案,再通过一定的技术手段达到无限运算。层次型的加密方案在进行同态乘法运算时同样会使得噪声呈指数级别的增长,例如,维的数据进行一次同态乘法之后会产生 维的噪声,两次同态乘之后会产生 维的噪声,因此需要对噪声做一定的处理才能达到全同态。年 等
15、提出了用密钥交换技术来解决维数膨胀问题,用模交换技术控制噪声从而使其达到全同态,在一定程度上摆脱了对自举的依赖,但最终要实现无限次的运算还需要自举技术。此阶段出现的方案有()、()等。以这一阶段的方案作为基础方案构造的多密钥全同态加密方案可分为 型和 型两大类。型的 是最早被提出的,型的 是最晚被提出的。型 的构造及优化作为首个被提出的多密钥加密方案类型,对后来 的构造起着至关重要的作用,型多密钥加密方案的基本构造过程如下。()初始化():安全参数为,选择 整 数 (),定 义 分 圆 多 项 式 环 (),其中 为 的幂次阶分圆多项式,为 的幂次。定义多项式环 ,中上第 期祁正华,等:多密钥
16、全同态加密的研究现状与发展趋势界为 ()的错误分布。定义一系列递减的模数 ,令 ,。()密钥生成(,):产生公钥、私钥和同态计算密钥,其中 为运算深度。()加密(,):将明文数据加密为 的形式,其中 为公钥,。()同态运算(,):此阶段需要计算密钥的参与,用计算密钥结合模交换技术或密钥交换技术进行同态运算。()解密(,):其中 为经过同态计算产生的新鲜密文。其安全性基于,和,问题。当前对 型 的优化主要是抑制噪声的增长速度、优化方案的安全性或在同态计算时减少计算密钥的交换次数甚至消除计算密钥的交换等。李瑞琪等便利用工具向量(,),:,其中 为基,)和比特分解技术构造了一个同态运算过程不需要计算
17、密钥的层次型的 型,提高了方案的运算效率,构造的方案相比原方案密钥的生成方式没有改变,只是在加密过程中先对“”进行加密,其具体的优化过程如下。(,):随机抽取 组,用于计算(,)来得到 个“的密文”,然后将 个 的密文组成一个向量,最后输出密文 。(,):用联合私钥 (其中,为用户的私钥)进行解密,可得明文 (,)。此时对进行同态运算之后的密文进行解密便可不再需要计算密钥,直接用私钥与密文做内积即可得到明文。下面以解密同态乘()为例进行论证,使用 解密 时需计算,因此可令 得到的矩阵为,可得(,)(,)()已知 ,因此可得、,又知 、,、,是“”的密文,因此 ,所以可得 ,因此同态乘法运算过程
18、不需要计算密钥的参与得证,同态加法运算过程同理。除直接对同态运算过程优化外,还可采用间接方式。例如,车小亮等通过改变 型加密方案的底层结构对其安全性和效率进行了优化,将现有方案底层的分圆多项式环扩展到素数次分圆多项式环上,可以抵御更多的子域攻击。然后通过扩展密文维度消除密钥交换技术,并结合模交换技术构造一个高效的层级的 型。其具体的优化过程如下。对安全性的优化:只是将原方案中的分圆多项式用素数次分圆多项式替代,其他多项式时间算法不 变。定 义 素 数 次 分 圆 多 项 式 环 为()和 ,参数 和 ()为素整数。根据文献可知,素数次分圆多项式可以抵抗更多的子域攻击。对效率的优化:上面对安全性
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 密钥 同态 加密 研究 现状 发展趋势