基于格的伪随机函数研究综述

伪随机函数是密码学领域最基本的原语之一,其自提出以来便备受关注.近几十年间发展起来的格理论在密码领域取得了很多重要的应用成果,特别是格上很多困难问题被普遍认为具备抵抗量子攻击的特性,在后量子密码方案设计中处于核心地位.对于格上伪随机函数的研究正式起始于Banerjee、Peikert和Rosen在2012年欧密会上发表的工作.此后,密码学家们围绕如何基于格困难问题设计伪随机函数方案开展了大量研究,特别是在提升伪随机函数方案的安全性、效率和并行性,以及扩展伪随机函数的功能方面取得了诸多成果.本文对格上伪随机函数的研究现状进行综述:总结了伪随机函数的通用构造方法以及格上伪随机函数依赖的底层困难问题;整理了现有基于格困难问题设计的伪随机函数方案,重点关注这些方案在提升安全性、效率或并行性方面采用的技术以及取得的成果;整理了格上具备扩展功能的伪随机函数的研究进展,包括具有密钥同态性质的伪随机函数、约束伪随机函数、水印伪随机函数以及可验证伪随机函数.

新形态伪随机函数研究

随着云计算模式的普及应用,对密文数据的安全外包计算的研究已是必然趋势,由此,潜在的密文数据的安全计算和隐私保护问题愈加受到业界和学界的关注。新形态伪随机函数(Pseudorandom Function,PRF)作为解决密文安全计算与检索的重要工具之一,已是当前密码学的研究热点。当前,以密文安全计算为目标,结合全同态加密(Fully Homomorphic Encryption,FHE)与格密码、门限密码、安全多方计算(Multiparty Computing,MPC)和PRF等密码学原语,对新形态伪随机函数的研究主要集中在三方面:1)格基限制隐藏的PRF可验证性研究;2)格基受限PRF适应性安全研究;3)格基多点隐私可穿刺PRF应用性研究。因此,文章从PRF的可验证性、安全性和应用性三方面,较为全面地介绍当前重要的研究成果。

基于伪随机函数的RFID系统双向认证协议

移动RFID系统中,读写器与后台数据库之间不再通过有线方式通信,而采用无线方式通信,但也存在一定的安全隐患问题。为确保通信数据的安全,提出一种基于伪随机函数的移动RFID双向认证协议。协议确保标签、读写器、后台数据库三方均进行认证,从而保障通信的安全性;采用字合成等位运算,在一定程度上能够减少总的计算量;三方认证,使得移动RFID系统具备更为广泛的运用价值。安全性及性能分析表明,所提协议具有较高的安全性及较低的成本。

基于短整数解问题的伪随机函数新构造

伪随机函数是构造密码原型的重要工具。基于短整数解问题,在格上设计出2个伪随机函数,第一个利用树状伪随机综合器的思想,达到并行化效果,第二个虽是串行构造,但降低了公钥尺寸。二者均具有小模数,而且是可证明安全的。与A Banerjer,C Peikert和A Rosen 3人提出的方案(EUROCRYPT 2012)相比,此提出的伪随机函数具有渐少的密钥量;在构造方法上,由于避免了凑整技术的使用,伪随机函数的生成效率得到了提高。

一种分级代理的受限伪随机函数构造方案

受限伪随机函数的概念于2013年分别是由Boneh和Waters、Kiayiaset等以及Boyle等提出的,是指由主密钥k可以派生出一个受限密钥ks,在定义域的受限集合S上利用主密钥k和该受限密钥均可计算出相同的伪随机函数(PRF)的值。基于Boneh和Waters方案中展示的基于比特固定结构的受限伪随机函数方案,给出了基于分级代理的受限伪随机函数的构造方案,该方案的受限集合大小不受分级层数的影响,在标准模型下基于多线性判定性Diffie-Hellman假设(MDDH)证明了其安全性。本方案在实际环境中可用于分级或代理下广播加密的加密密钥或者非交互式环境中协商的会话密钥。

基于单向伪随机函数的移动RFID系统认证协议

针对移动RFID系统认证中可能出现的成本、效率、安全问题,设计了一种基于单向伪随机函数的移动RFID认证协议。协议在满足Gen-2标准的前提下,综合采用位替换运算、异或运算和单向伪随机函数加密通信信息;协议充分利用标签、读写器、后端数据库三方共享密钥和三方通信信息,对信息进行加密传输和加密认证,降低系统成本;通过实现完整三方认证与密钥更新工作,避免协议遭受假冒、去同步化等攻击行为。最后,给出协议GNY理论逻辑证明以及安全、性能分析,表明新协议的可行性与安全性。

基于伪随机函数的移动射频识别认证协议

为解决移动射频识别(RFID)中阅读器和后端服务器之间因无线传输出现的安全问题,提出一种基于伪随机函数的移动RFID双向认证协议。该协议满足EPC Class-1 Generation-2行业标准,且实现了标签、阅读器和后端服务器之间的双向认证,并通过GNY逻辑证明了其安全性。该协议能有效抵抗追踪、重放、同步化等攻击,而且它将主要计算转移到后端服务器,因此能降低标签的运算量和标签成本。

基于伪随机函数的RFID双向认证协议

针对在物联网应用中,现有的RFID安全认证协议存在安全缺陷和认证效率低等问题,提出了一种改进的基于PRF的RFID双向认证协议,通过对读写器产生的随机数进行加密的方法,来解决原协议存在的安全隐患问题;采用随机数使标签保持信息的新鲜性。通过和已有的此类安全认证协议进行安全性比较,结果表明改进的协议不仅具有防跟踪、抗暴力破解、防重放攻击等特点,而且保证了标签没有大幅增加计算量。

约束伪随机函数的构造及应用研究

本文提出了约束伪随机函数PRF构造的密钥空间、域和作用范围集合,通过具有双变量函数构造约束PRF的随机多项式时间算法和确定多项式时间算法,提出了用于最佳密钥长度广播加密的位固定约束PRF构造安装函数和附加算法函数,采用形式化方法分析了约束PRF的密钥安全属性,并将随机密钥事件函数的优势性忽略不计以保证约束PRF的安全属性,应用位固定约束PRF构造广播加密密钥系统,广播加密系统的接收密钥、实时或随机密钥库的密文具有最佳密文长度。

一个关于MAC伪随机性与不可伪造性的注记

文献[1]证明了XOR-MAC的伪随机性,即XOR-MAC的标签生成算法和随机函数不可区分,进而宣称给出了XOR-MAC的安全性新证明.本文通过对Wegman-Carter MAC的研究,说明了随机的或者带状态的MAC的伪随机性并不意味着MAC的安全性,即不可伪造性.

基于哈希挑战和随机翻转的WSN通信安全

为保证无线传感器网络(WSN)通信中数据的机密性和可靠性,提出一种基于随机数据翻转和变色龙哈希挑战的轻量级安全传输方法。数据加密和签名保护过程都只需要进行最基本的比特翻转操作,计算效率更高。通过安全性分析和仿真实验验证了该方案的有效性,实验结果表明,与传统安全方案相比,当20%的传感器数据被攻击者利用中间人攻击进行干扰时,AFC的数据融合错误概率能够保持在5%到10%,而窃听者的错误概率始终接近50%。

基于中国剩余定理的NFC安全认证算法

针对近场通信技术在应用中出现的安全隐患问题,给出一种基于中国剩余定理的算法。算法利用中国剩余定理实现对传送信息进行加密,中国剩余定理基于数学中大素数分解难题,使得攻击者无法进行破解;所有信息加密过程中混入随机数,用于保证消息的新鲜性;算法在进行信息更新时采用伪随机函数计算,因伪随机函数具备的单向性,使得攻击者无法分析出有用隐私信息。将不同算法对比安全分析,表明该算法能够抵抗重放攻击、异步攻击等多种攻击。通过性能角度及仿真实验对多个算法进行分析,结果表明该算法计算时间复杂度低于其他算法。

抗恶意敌手的线性门限隐私集合交集协议

门限隐私集合交集(TPSI)是安全多方计算中的一种特例,其在机器学习、共享拼车、指纹识别等多个领域有广泛的应用。然而,目前存在的方案均基于计算复杂度较高的算法,并且仅在半诚实模型下实现,导致协议计算开销较大且无法抵抗恶意敌手的攻击。为了解决以上问题,首先提出了一个向量不经意匹配测试(VOMT)协议,并基于VOMT和布谷鸟哈希设计了一个高效的半诚实TPSI协议。此外,结合VOMT与对称密钥加密方案构造出向量不经意解密匹配测试(VODMT)协议,并基于VODMT与不经意伪随机函数设计了一个可以抵抗恶意敌手的TPSI协议。随后,分别在半诚实模型和恶意模型下证明了协议的安全性,并分析得出两个协议的计算复杂度和通信复杂度均为线性。在集合大小为4096时,提出的两个协议的在线运行时间分别为0.81 s和1.81 s,而先前的工作则需要5627 s,所以两个协议均是高效的。

基于格的最优轮数口令认证秘密共享协议

口令认证秘密共享将口令认证和秘密共享相结合,是一个贴合实际用户需求的分布式方案。该协议允许一个用户在多个服务器间共享秘密,并且只需要记忆一个简短口令即可在后续同时完成身份验证以及秘密恢复。协议安全性保证只要敌手控制的服务器不超过阈值,敌手就不能从协议中窃取任何有关口令和秘密的信息。口令认证秘密共享方案最初基于离散对数及其变体的假设,不能抵抗量子攻击,因此找到量子安全的构造成为亟需解决的问题。ROY等人提出一种恶意安全且量子安全的构造,但其通信轮数并非最优,在有恶意敌手干扰的情况下,轮数甚至不再是常数。针对轮数优化问题,文章利用可验证不经意伪随机函数原语,给出了基于格的最优轮数的量子安全构造并严格证明了其安全性。此外,协议保证多数诚实服务器场景时,诚实用户一定能在最优轮数内成功恢复正确的秘密,具有很强的鲁棒性。

一个基于合成泛hash函数族的消息认证码

为有效认证多个字符串,提出一个输入可为字符串向量的消息认证码:VHMAC。VHMAC基于泛hash函数族的合成。为高效处理字符串向量,定义一个并行的泛hash函数族,其结果输入另一泛hash函数。将普通消息认证码的安全性定义扩展到输入为字符串向量的情形。在底层分组密码是伪随机置换的假设下,证明了VHMAC的安全性。此外,VHMAC还具有可预处理性和可并行运算性。

高性能两方隐私集合求交技术研究及应用探索

隐私集合求交(Private Set Intersection,PSI)是一种保护数据隐私的集合计算技术,允许互不信任的各方协同计算私有数据的交集,且不透露交集以外的任何信息。PSI技术被广泛研究和应用,主要从提升性能和探索新型应用场景两个方面发力。首先详细梳理两方PSI的研究进展,分析和评估业界先进的算法协议;其次以卫星互联网新型应用场景为例,探索提出高性能两方PSI应用方案,实验测试不同数据类型在多种网络环境下的性能,给出新型场景下的PSI实践范式。最后进行总结与展望,给出了PSI的发展思考与建议。

一种基于SQL的元组集随机抽取算法

提出了一种基于SQL语句的从数据库中随机读取随机记录集合的算法。该算法摒弃了贯用的通过复杂的客户端编程实现随机过程的做法,通过对SQL语言中的伪随机函数和反转函数进行组合,只用一条SQL语句就可以实现随机过程,算法实现简单,资源占有率低、效率高,具有很强的通用性和实用性。

标准PRF假设下基于立体几何变换的轻量级混淆电路协议

混淆电路(Garbled Circuit,GC)是安全两方计算(Secure Two-Party Computation,S2PC)的重要基础协议.为保证安全性,GC协议需要调用加密算法对电路中的门信号进行加密混淆.当前,GC协议构造每个二元门(如与门)需调用4次加密算法,标准伪随机函数(Pseudorandom Function,PRF)假设下,每个二元门的混淆表至少包含2个密文.如何有效降低加密算法调用次数与混淆表规模,是GC协议提升性能的主要研究问题.本文在标准PRF假设下,提出了一种基于立体几何变换的轻量级混淆电路协议SGT-GC,根据每类二元门信号逻辑设计了专门的立体几何变换,并替代传统的加密算法实现混淆门的构造.其中,对于每个二元混淆与门(AND Gate),首先将其4种可能的输入组合(00,01,10,11)转换为三维空间中不共圆的4个点坐标P00、P01、P10、P11,经过逻辑值为FALSE的三个点(P00,P01,P10)构造圆,然后在经过圆心的圆平面法线上取任意点C,i并满足该点到P00、P01、P10的距离相等且不同于到逻辑值为TRUE的点P11的距离.则该随机点Ci即可作为二元与门混淆表中的交换信息,其通信成本变成1,且不再需要额外的加密算法调用.对于二元混淆异或门以及一元非门,本文也进行了专门的设计并给出了详细的协议过程与数学论证.本文所提出的SGT-GC协议中,每个混淆表中仅需1个共享交换信息,且不需调用任何额外加密算法,避免了多次调用复杂的加密算法所造成的计算成本及传输混淆表中多条密文所造成的通信成本.安全性证明表明,本文所提协议在半诚实模型下满足隐私性、不经意性和可认证性.

多方隐私集合交集计算技术综述

随着互联网、大数据等新技术的快速发展,越来越多的分布式数据需要多方协作处理,隐私保护技术由此面临更大的挑战。安全多方计算是一种重要的隐私保护技术,可为数据的安全高效共享问题提供解决方案。作为安全多方计算的一个重要分支,隐私集合交集(PSI)计算技术可以在保护参与方的数据隐私性前提下计算两个或多个参与者私有数据集的交集,按照参与方数目可分为两方PSI和多方PSI。随着私人数据共享规模的扩大,多于两个参与方的应用场景越来越常见。多方PSI具有与两方PSI相似的技术基础但又有本质的不同。该文首先讨论了两方PSI的研究进展,其次详细梳理多方PSI技术的发展历程,将多方PSI技术依据应用场景的不同分为传统多方PSI技术以及门限多方PSI技术,并在不同场景下按照协议所采用密码技术和功能进行更细致的划分;对典型多方PSI协议进行分析,并对相关密码技术、敌手模型以及计算与通信复杂度进行对比。最后,给出了多方PSI技术的研究热点和未来发展方向。