优化的基于错误学习问题的CKKS方案

针对基于错误学习(LWE)问题的CKKS同态加密方案在密态数据计算中存在的密文大、计算密钥生成复杂以及同态计算效率低的缺陷,运用比特丢弃和同态计算密钥重组的方法,提出了一种优化的LWE型CKKS方案。首先,丢弃密文向量的部分低位比特和同态乘法计算中密文张量积的部分低位比特,从而减小了同态乘法过程中的密文规模;其次,针对比特丢弃对同态计算密钥进行重组和优化,从而去除密钥交换过程中powersof2含有的无关扩展项并降低计算密钥的规模和同态乘法过程中的噪声增长规模。在保证原有方案安全性的基础上,所提优化方案使得计算密钥的维度减少,使得同态乘法的计算复杂性降低。分析结果表明,所提出的优化方案在一定程度上降低了同态计算及计算密钥生成过程的计算复杂性,从而降低了存储开销并提升了同态乘法运算的效率。

具有一致秘密和错误的LWE问题及其应用

提出了一种新的带错误学习问题(learning with errors,LWE)的变种,这种变种中的秘密向量和错误向量的每一个分量都是取自于一个小区间上的一致分布,其中,运用了Applebaum等人提出的转换技术.这种技术将一致秘密的LWE样本映射到另一些LWE样本,这些样本的秘密是服从和错误一样的分布,同时只损失了一小部分的样本.这个变种有和标准LWE一样的最坏情形到平均情形的归约性,同时,它去除了标准LWE问题中的高斯抽样算法.基于新的变种,构造了一个密钥相关消息安全的公钥加密方案.方案去除了原来方案中的高斯抽样算法,取而代之的是小区间上的一致分布的抽样算法,从而降低了密钥生成算法和加密算法的开销.

一种新型基于格上LWE问题密钥交换协议的设计

基于格上困难问题设计一种高效、安全的后量子密钥交换协议具有非常重要的理论意义和实用价值。提出了一种新型高效实用的基于格上错误学习问题被动安全密钥交换协议。该协议采用加密机制的构造方式并使用了密文压缩技术,与2016年Bos等人基于错误学习问题并使用Peikert错误调和机制设计的密钥交换协议Frodo相比,通信量只增加了1.09%,但方案复杂度有效降低,计算更加简洁高效,且协议在被动攻击下可证明安全,可有效抵御量子攻击。该协议与现有的基于错误学习问题设计的密钥交换协议相比具有很强的竞争力。

LWE问题实际安全性分析综述

LWE问题被广泛用于设计安全的格上密码方案。为了评估基于LWE的格密码方案在给定具体参数下的安全强度,我们需要研究目前求解LWE问题算法的复杂度。本文以Albrecht等人^([33])2015年的研究工作为基础,概述了求解LWE问题的主流算法及其复杂度,并给出了针对具体LWE实例的评估结果。

LWE问题的分析策略及格基约减算法综述

格公钥密码因其数学困难问题的平均/最坏复杂度等价性、代数结构的线性性和丰富的密码等功能而被普遍认为是最有发展前途的后量子密码。目前有大量格密码算法的安全性基于格上的错误学习(LWE)问题而设计。因此,研究LWE的求解算法对深刻理解格公钥密码算法的安全性至关重要。文章首先针对不同类型LWE问题的不同求解策略进行梳理和比较;其次,归纳整理了目前已有的格基约减算法的基本思想和技术原理;最后,对基于格归约的方法求解LWE问题的研究重点和趋势作了展望。

基于理想格的两方隐私集合交集协议

当前大多数现有的隐私集合交集(PSI)协议的安全性都是基于数论假设,而随着量子计算理论的发展,基于数论假设的PSI协议将变得不再安全。针对该问题,利用格上函数加密的函数策略解密特性,通过二进制分解将参与方元素设计成符合LWE加法同态的向量形式,提出了一种基于理想格的半诚实安全的两方PSI协议。安全性方面,使用基于环上错误学习问题(RLWE)的函数加密系统来构造PSI协议,实现了抗量子的安全性。效率方面,协议的通信复杂度为O(w+v),与参与方元素成正比,保证了较高的通信效率;并且利用理想格,减小了公钥的大小,提高了存储效率,降低了通信成本。

一个LWE上的短公钥多位全同态加密方案

目前全同态加密的效率亟待提高,为了提高全同态加密的效率,提出一个LWE(learning with errors)上的短公钥多位全同态加密方案.方案中从离散高斯分布上选取LWE样例,并且将高斯噪音与之相加,导致LWE样例从2nlogq下降到n+1,使得方案的公钥长度变短.详细给出了该方案的噪音增长分析与安全性证明;此外,对目前密钥交换技术进行了优化,并且针对多位全同态加密,给出了密钥交换优化版本的形式化描述;最后,针对目前全同态加密的实践应用,给出了分析全同态加密具体安全参数的方法.分析了该方案与BGH13方案的具体安全参数,数据显示该方案的具体参数长度要优于BGH13方案.

基于抽象解密结构的全同态加密构造方法分析

为什么能够在格上构造全同态加密?密文矩阵的本质及构造方法是什么?该文提出一个重要的概念:抽象解密结构。该文以抽象解密结构为工具,对目前全同态加密构造方法进行分析,得到抽象解密结构、同态性与噪音控制之间的关系,将全同态加密的构造归结为如何获得最终解密结构的问题,从而形式化地建立全同态加密构造方法。最后对GSW全同态加密方法分析,提出其密文矩阵是由密文向量堆叠而成。基于密文堆叠法,研究密文是矩阵的全同态加密的通用性原因,给出密文矩阵全同态加密与其它全同态加密之间的包含关系。

全同态加密具体安全参数分析

为了保证全同态加密的安全使用,以及衡量分析全同态加密方案的效率,提出一个计算分析LWE上全同态加密具体安全参数的通用方法,该方法同样适用于环LWE上的全同态加密.该方法分为两步:第一步,根据同态计算的电路深度L,以及全同态加密方案解密正确性条件与噪音增长关系,计算出所需的模q;第二步,在给定安全等级下,我们引入了敌手的优势,根据区分攻击获得LWE问题维数n与模q之间的函数关系,计算出满足第一步中模q的最小维数n.从而分析计算出全同态加密的具体安全参数.该方法具有模块化特征,可以根据最新的格密码攻击进展替换相应的内容,从而获得最新的全同态加密具体安全参数.最后利用提出的方法对两个全同态加密的代表方案进行了具体安全参数的分析与比较,这也是首次给出这两个方案的具体安全参数.数据显示目前LWE上的全同态加密参数尺寸过大,与实际应用还有距离.

一种基于格的属性多重加密方案

为提高属性加密系统的运行效率和加解密的安全性,提出采用格理论代替双线性对来减少加解密过程的运算量。根据格上的密文策略属性加密方案和属性动态多重加密方案,给出一种属性多重加密方案。该方案能同时加密多条消息,提高系统运行效率并且抵抗量子密码的攻击。对方案的正确性进行严格推导证明,并利用可证明安全将方案的安全性规约到学习错误困难问题中。分析结果表明,该方案是正确并且可行的。

格基不经意传输协议

利用一个基于错误学习问题的陷门单向函数,在格上设计了一个3轮不经意传输协议。假设错误学习问题是困难的,证明协议实现了对接收者和发送者隐私性的保护。分析表明,协议中只使用小整数的模乘和模加运算,具有很高的计算效率;协议使用限制明密文扩展技术有效缩短了传输消息的长度,提高了协议的通信效率。

RAKA：一种新的基于Ring-LWE的认证密钥协商协议

后量子时代,基于格理论的公钥密码被认为是最有前途的抵抗量子计算机攻击的公钥密码体制.然而,相对于格上公钥加密体制和数字签名方案的快速发展,基于格上困难问题的密钥协商协议成果却较少.因此,现阶段如何构建格上安全的密钥协商协议是密码学领域具有挑战性的问题之一.针对上述问题,基于环上带错误学习问题困难假设,采用调和技术构造了一种新的认证密钥协商协议RAKA(authenticated key agreement protocol based on reconciliation technique),该方案采用格上陷门函数技术提供了单向认证功能,并且在Ring-LWE假设下证明是安全的.与现有的基于LWE的密钥协商协议相比,该方案的共享会话密钥减小为2nlog q,效率更高;同时,由于该方案的安全性是基于格上困难问题,因此可以抵抗量子攻击.

格上高效的完全动态群签名方案

为降低完全动态群签名加入和撤销机制的复杂性,将动态群签名思想引入NGUYEN等人提出的格上群签名方案,提出一种改进的完全动态群签名方案。在改进方案中,用户产生自己的签名密钥而不是由群管理员产生,当用户加入群时,群管理员验证用户身份并为其颁发证书,用户成为群成员后用自己的签名密钥和证书进行签名。若群成员有不合法行为或想退群,则群管理员和群成员均可执行群成员的撤销操作,使群成员退出该群。由于方案中群成员的签名密钥由自己生成,因此能够抵抗群管理员的陷害攻击。在随机预言模型下,基于错误学习问题和非齐次小整数解问题证明改进方案的安全性。分析结果表明,该方案能够减少加入和撤销机制的计算代价,且密钥长度和签名长度与群成员数量无关,适用于大群组的签名系统。

理想格上可证明安全的不经意传输协议

针对理想格相比一般格可以在不降低安全性的基础上减少密钥量、缩短密钥长度、降低运行开销的优点,将理想格上的优势与一般格上的不经意传输协议结合,把2012年欧密会上Peiker提出的格上陷门函数生成算法扩展到理想格上,提出基于理想格上的1-out-of-n不经意传输协议方案。利用理想格上的基于错误学习问题的陷门单向函数,保证了协议发送方和接收方的隐私性,并证明了协议的完备性和安全性。效率方面,协议中使用的计算是小整数的模乘和模加,有很高的计算效率;并且使用理想格有效地限制明密文长度和密钥量,减少了通信成本。

一种全同态加密的安全内积计算方案

在云计算环境下密文top-k检索的众多方法中,该文聚焦于同态加密方法,该公钥加密方法具有不解密就能对密文进行操作的优点。在密文top-k查询中,内积相似性是度量索引向量和查询向量的相似性的最常用的一个指标。该文提出一个安全计算两向量内积相似性的方案,该方案使用基于环上错误学习问题的批处理和打包的同态加密来保护隐私。与其他方法相比,该方案具有通信代价低和计算代价低的优点。

格上随机喻示模型下带关键字检索的公钥加密体制

近年来,基于格的密码体制受到越来越多的关注。这类密码具有诸多潜在优势:抗量子攻击、并行性好、概念简单、安全性所基于的困难问题的随机实例难解性等价于格上公认困难问题最坏情况等。带关键字检索的公钥加密(PEKS)体制是一种具有关键字检索功能的加密机制:用PEKS加密的关键字w的密文和加密消息存储在服务器上,用户向服务器发送一个秘密值Tw,服务器可以搜索出所有包含该关键词w的加密消息,但无法知晓w本身的任何内容。提出了一种基于格的带关键字检索的公钥加密体制,并在随机喻示模型下,基于格上带错误的学习(Learning With Errors)问题的困难性假设证明了新体制的安全性。

格上基于身份的可问责代理重加密方案

针对目前基于格的代理重加密方案中存在密钥滥用和数字证书管理等问题,引入问责机制,提出一种新的基于身份的可问责代理重加密方案。该方案采用用户身份ID计算生成矩阵作为公钥,并使用原像采样算法提取私钥,解决了数字证书管理的问题;使用双方用户公钥计算生成重密钥,提高了加/解密时的计算效率;使用代理商公私钥参与重加密运算,完成问责算法,有效地抑制了代理商和被授权者共谋的行为。安全性分析表明方案满足选择明文攻击安全;在效率方面,方案的计算复杂度和密文开销较小。

循环安全的同态加密方案

全同态加密可以对密文进行有效计算,是实现云计算、大数据以及机器学习中数据隐私安全的一项重要密码技术.利用“自举”技术可以构造全同态加密方案,但是使得运算密钥随着运算电路的深度线性增长,这是全同态加密方案实用性的一个主要瓶颈.然而,如果同态加密方案满足循环安全性,即可以对方案的私钥进行安全的加密,则可以使得运算密钥的规模独立于运算电路的深度.因此,满足循环安全性的同态加密方案是值得研究的一个问题.基于噪声淹没技术,给出了循环安全的公钥同态加密方案,并给出了安全性证明和参数设置;进一步,通过引入拒绝采样技术,给出了优化的循环安全公钥同态加密方案,在增加部分采样算法的代价下,将系统参数从超多项式级降低到多项式级,大大约减方案公钥和密文规模,从而可以有效改善密文运算的计算复杂性,提升同态加密方案的性能.

维度不变的格基代理广播加密方案

为解决量子环境下广播加密的安全和效率问题,结合Agrawal等人提出的维度不变的格基代理生成算法,设计出一种格上基于身份的广播加密方案。该方案采用父格与子格的结构关系来表示系统主私钥与合法用户私钥的对应关系,合法用户可以利用自己的私钥解密广播信息;不同于以往方案,该算法利用系统主私钥生成合法用户私钥的时候,不会增加用户私钥的维度。在随机预言机模型下证明该方案是适应性安全的,其安全性规约到错误学习(LWE)问题。

可撤销属性的格基属性加密方案

针对量子环境下属性加密体制中属性撤销的问题,结合Zhang等提出的格上基于密文的属性加密方案,在格上构建了一个可撤销属性的格基属性加密方案。通过属性撤销列表,在二叉树结构下将未被撤销属性对应的密钥进行更新,从而达到撤销属性的目的。利用Shamir门限秘密共享的思想,实现了门限访问控制策略。该方案在随机预言机模型下是选择性安全的,安全性规约到错误学习问题。分析表明该方案在量子攻击下是安全的,并且支持灵活的门限访问控制策略。