Journal of Cryptologic Research
 
引用检索 快速检索 DOI 高级检索
在线期刊
   » 最新录用
   » 网络预发表
   » 当期目录
   » 过刊浏览
   » 按栏目浏览
   » 综述文章
   » 摘要点击排行
   » 全文下载排行
  作者在线投稿
   » 作者投稿/查稿
   » 投稿须知
   » 模版下载
   » 版权协议
  专家在线审稿
   » 审稿登录
   » 审稿政策
   » 自荐为审稿人
热点文章

Grain-128a 认证机制的安全性分析

王鹏, 郑凯燕
2018, 5(1): 94-100. 全文: PDF (537KB) (119)
摘要

Grain-128a是一个基于序列密码的认证加密方案, 泛杂凑函数是其认证部分的核心部件. 之前的研究侧重于寻找其中序列密码的弱点. 本文在假设序列密码是完美的基础上, 以泛杂凑函数的弱密钥分析为切入点, 研究Grain-128a的安全性. 由于这一泛杂凑函数是一个简单的仿射函数, 我们的研究表明其在Grain-128a中存在弱密钥集合, 攻击者可以有效判定泛杂凑函数的密钥是否属于这一集合, 如果密钥属于这一集合, 攻击者可以进行概率为1的伪造攻击. 同时, 我们在弱密钥分析的基础上, 进行密钥恢复攻击. 假设处理的消息是1比特, 我们仅需要1次加密询问和不超过232+l-1次解密询问, 就可以恢复泛杂凑函数l+31比特的密钥, 成功概率为1. 更进一步, 我们可以得到序列密码生成的几乎所有的密钥流, 从而可以进行任意的伪造攻击, 即对任意长度不超过$l$比特的消息, 伪造其密文及相应的鉴别码.  本文最后分析了之所以能进行这些攻击的原因和防止攻击相应的措施.

认证加密算法 FASER 的安全性分析

冯秀涛, 张凡
2018, 5(1): 83-93. 全文: PDF (530KB) (122)
摘要

CAESAR是日本于2013年发起的密码竞赛活动, 旨在面向全球征集对称认证加密算法. FASER是提交到CAESAR竞赛的认证加密算法簇, 它包括两个算法: FASER128和FASER256. 该算法簇基于流密码体制, 即根据输出密钥和初始随机向量生成与明文流等长的伪随机密钥流, 然后用该伪随机密钥流异或明文流进而输出密文流. FASER 包括加密算法和认证算法, 其认证算法于加密算法类似. 本文我们发现FASER的每拍输出字的比特之间有很强的相关性, 根据这种相关性我们给出FASER128 和FASER256的代数攻击. 首先我们给出FASER128加密算法的状态恢复攻击, 其时间复杂度约为229, 数据复杂度约为64个密钥字, 我们将该攻击算法在普通的个人计算机上实现, 该攻击算法在数分钟内即可恢复FASER128的状态. 进一步, 我们给出FASER128的密钥恢复攻击, 其时间复杂度约为236, 该攻击算法在多核计算机上可以并行实现. 例如在32核计算机上可以在几分钟之内恢复出种子密钥. 这表明FASER128不安全. 进一步, 我们的攻击可以很容易地移植到FASER256, 并在文章最后给出了针对FASER256的状态恢复攻击, 其攻击复杂度不超过248. 由于我们的工作, FASER 于2014年被撤销.

认证加密算法研究进展

吴文玲
2018, 5(1): 70-82. 全文: PDF (331KB) (390)
摘要

认证加密算法是能够同时保护数据机密性、完整性、以及数据源认证的对称密码算法, 在现实生活中有着广泛的应用需求. 在CAESAR竞赛的推动下, 认证加密算法研究发展迅速, 推出了一批新算法, 也给出了不少分析结果, 但进展并不顺利. 从现有成果看, 无论是安全目标的凝练刻画, 还是算法设计的理念, 或是分析评估的基本策略, 都呈现出一种五花八门、百家齐放的局面. 本文首先回顾认证加密算法的发展历程, 系统梳理认证加密算法的安全模型; 然后以CAESAR竞赛候选算法为对象, 归类总结认证加密算法的各种设计理念, 介绍各类认证加密算法的优势和最新的安全性评估结果; 最后探讨认证加密算法的发展趋势和存在问题.

认证加密算法专栏序言

胡磊
2018, 5(1): 68-69. 全文: PDF (121KB) (184)
摘要

认证加密算法同时实现两种最基本的安全功能, 即机密性和完整性, 是一类具有广泛应用前景的密码算法. 认证加密算法虽然研究历史很短, 但一直是密码研究的重要对象.

认证加密算法的研究经历了三次高潮.

第一次高潮是一体式认证加密算法的设计. 2000年之前, 学术界甚至还没有为认证加密给出一个严格的安全性定义, 多数密码研究者的认识仍然停留在``加密 + 认证 = 认证加密"这一初步的认识上, 这期间的学术界一直在探索一体式认证加密算法的设计, 但是都不成功, 这和当时缺乏安全性定义有直接的关系. 随着严格定义的给出, 特别是对密文完整性(INT-CTXT)的刻画, 认证加密才真正开始严密的科学研究. 不同于简单地将加密算法和认证算法组合在一起、一般需要对数据进行两遍处理的组合式设计, 一体式的设计则只需要对数据处理一遍即可同时实现机密性和完整性两种功能. 2000, OCB模式为代表的认证加密工作模式, 第一次完成了一体式的设计, 该模式中一个分组的数据平均只需调用一次分组密码, 较之以前组合式设计的运算效率大为提高. OCB模式在严格的安全模型下被证明是安全的, 即如果底层的分组密码是一个伪随机置换, 那么敌手攻击上层的OCB模式的机密性和完整性的成功概率都是密码意义下可忽略的.

第二次高潮是对认证加密标准化的讨论. 由于认证加密算法的广泛应用, 2000年开始, 各个标准化组织纷纷开始对认证加密算法进行标准化, 其中包括无线局域网络802.11i标准中的认证加密算法、美国国家标准与技术局(NIST)的认证加密算法标准、密钥信息加密的密钥包装(key wrap)标准、IEEE P1619存储加密标准等等. 这一过程极大推动了认证加密算法的发展, 例如密钥包装(key wrap)标准的讨论, 引发nonce误用问题的讨论, 也促成了确定性认证加密概念的提出. OCB模式虽然效率上有很大优势, 但是由于专利限制等原因, 在相关密码标准的制定过程中屡屡受挫, 组合式的GCM模式反而后来居上, 成为标准化过程中最成功的认证加密算法. 在这期间, 涌现出一批有代表性的设计, 例如CCMEAX. 2009, 国际标准化组织(ISO)的认证加密算法标准ISO/IEC 19772将这些认证加密算法全部都包括进去了, 可以看作是这一阶段认证加密算法研究的一个总结.

第三次高潮是近年来的CAESAR竞赛. 2012年开始, 应用最为广泛的认证加密算法GCM模式被发现出现了一些问题. 首先, GCM模式中的泛杂凑函数存在弱密钥; 其次, GCM模式的安全证明存在缺陷. 2014, NIST资助的CAESAR 竞赛应运而生, 使得认证加密算法再一次成为密码学界的研究热点. 这之后, 认证加密的研究更多地偏向应用安全. 例如, 在资源受限的环境下, 认证加密的解密设备可能无法在进行完整性通过后才输出明文, 而是输出完明文之后才给出完整性的判断, 这是所谓的明文未认证发布(release unverified plaintext, RUP)问题. 在这一场景的安全性需求下, 很多认证加密算法的安全性都是有问题的. 又例如, 在线处理数据的认证加密, 之前的研究将其和在线密码(online cipher)绑定在一块. 对于这一特殊的对象, 独立于在线密码的安全模型如何定义才算合理, 仁者见仁智者见智, 众说纷纭.

本期``认证加密算法专栏", 我们刊登三篇各具特色的论文, 希望对国内认证加密算法的研究有所启示.

第一篇是题为《认证加密算法研究进展》的综述文章. 该文回顾了认证加密算法的发展历程和相关的安全模型, 然后以CAESAR竞赛候选算法为对象, 总结了认证加密算法的设计理念, 分类介绍了第三轮评估的15个候选算法. 最后, 该文对认证加密算法的发展趋势和存在问题进行了探讨, 抛砖引玉, 期望更多国内学者参与其中的研究.

第二篇论文, 题为《认证加密算法FASER的安全性分析》, 对提交到CAESAR竞赛的认证加密算法FASER进行了分析. FASER包含两个算法: FASER128FASER256. 该文首先给出FASER128加密算法的状态恢复攻击和密钥恢复攻击, 32核计算机上只需要几分钟时间就可以实时恢复出密钥. 进一步, 该文还给出了FASER256的状态恢复攻击. 由于这一工作, FASER主动退出了CAESAR竞赛.

第三篇论文的题目是《Grain-128a 认证机制的安全性分析》, 该文以弱密钥分析为切入点对认证加密算法Grain-128a进行了研究. 研究表明Grain-128a认证部分的泛杂凑函数存在弱密钥集合, 攻击者可以有效判定泛杂凑函数的密钥是否属于这一集合, 一旦密钥落入这一集合, 就可以进行概率为1的伪造攻击. 这一分析方法和对GCM的弱密钥分析是一脉相承的.

CAESAR竞赛早已接近尾声, 最终获胜算法的公布日期却一再拖延. 无论如何, 认证加密算法的科学研究还将继续下去.

无双线性对的基于证书多域条件代理重加密方案

徐洁如, 陈克非, 沈忠华, 徐晓栋
2018, 5(1): 55-67. 全文: PDF (887KB) (110)
摘要

已有的基于证书条件代理重加密(CB-CPRE)方案有效保护了云中的数据, 解决了复杂的证书管理问题和密钥托管问题. 但是现有的基于证书条件代理重加密方案仍然存在着应用方面的缺陷, 只考虑了授权人和被授权人在同一个域内的情况, 而新型云环境中, 域间和域内的用户需要进行数据共享, 不同服务商需要相互协作, 为用户提供云服务. 对此, 本文通过结合多域这一概念, 在已有方案基础上, 提出了基于证书多域条件代理重加密(CB-MD-CPRE)方案的定义及其安全模型, 使得不同域内用户能相互访问数据, 有效解决了上述存在的问题. 且结合椭圆曲线群, 本文进一步构造了一个无双线性对的基于证书多域条件代理重加密方案, 并给出证明过程, 说明了该方案在随机预言模型下满足适应性选择密文攻击下的不可区分安全性. 最后, 通过对比分析本方案和其他相关方案, 可以看到本方案在性能方面有明显的优势, 且计算量较低, 在一定程度上限制被授权人解密权限的同时又支持域间和域内用户交流. 因此, 所提方案更适用于实际的云计算应用场合.

弱半 bent 正交序列集的构造

夏婷婷, 孙玉娟, 解春雷
2018, 5(1): 43-54. 全文: PDF (1056KB) (97)
摘要

扩频通信系统的码序列在近些年一直是备受关注的研究课题之一, 扩频通信序列目前已经被广泛应用于军事以及民用通信. 对于扩频序列, 相关值决定了系统的抗干扰性, 它要求具有良好的互相关性质, 为满足越来越密集的人口通信, 还需要保证每个蜂窝里的用户数量足够大. 本文提出弱半bent布尔函数和弱半bent序列集的定义,并利用Maiorana-McFarland类密码函数构造技术, 构造出弱半bent 正交序列集. 与半bent正交序列集相比, 利用弱半bent序列集可以使单个蜂窝内用户的数量更多. 本文还给出弱半bent序列集的两种优化方案. 第一种优化方案仍然是以增大单个蜂窝用户数为主要目标, 在某些情况下数量比目前最优结果大一倍. 第二种优化方案是用弱半bent正交序列集构造出半bent正交序列集, 使不相邻蜂窝间的用户干扰较弱半bent正交序列集更低, 并且没有减小单个蜂窝内的用户数. 弱半bent正交序列可用于同步CDMA系统的蜂窝用户码, 可以实现用户数量和抗干扰性的较好折中.

基于区块链的密钥更新和可信定位系统

李大伟, 刘建伟, 关振宇, 秦煜瑶, 伍前红
2018, 5(1): 35-42. 全文: PDF (1140KB) (303)
摘要

随着物联网技术发展, 智能设备数量激增, 无线智能物联网设备采用的自组织网络模式具有拓扑动态性、无中心分布性、无固定基础设施等特点, 然而这些特点为通信与定位的安全性带来众多问题. 首先, 为实现无线智能设备的安全通信, 往往采用单双钥加密相结合的方式, 然而一旦设备密钥丢失或泄露, 其密钥更新难以在自组织网络中及时同步; 其次, 在自组织网络中, 多设备之间会话密钥的协商往往需要复杂的交互和运算; 第三, 在城市、野外等复杂环境下, 采用自组织网络模式的智能设备难以接收来自外部足够强的定位信号, 而现有的APS定位算法在缺乏基站等可信第三方基础设施情况下难以确保其定位安全性; 最后, 现有定位算法难以确保无线智能物联网设备所获得的定位信号未遭篡改, 也难以保证网络监控下各移动设备所显示定位的真实性. 针对上述问题, 本系统将无线智能物联网设备之间建立的区块链作为可信基础设施, 记录用户身份对应的密钥更新链, 并便于多用户间会话密钥协商; 基于共识机制实现在无定位信号或弱定位信号下物联网智能设备之间可信相互定位, 并保障设备获取和发出的定位信息真实. 本系统可使用现有安全的密码算法构建, 能够高效安全地实现密钥更新与可信定位, 适宜在实际物联网设备安全通信系统中使用.

基于 LWE 的全同态身份基广播加密方案

冯翰文, 刘建伟, 伍前红
2018, 5(1): 21-34. 全文: PDF (742KB) (147)
摘要

全同态加密方案是一类允许第三方在不知晓解密密钥的前提下对密文进行任意运算的加密方案, 为云计算场景下数据隐私保护提供了有效的密码学工具, 具有重要的应用价值. 在复杂的网络环境下, 消息的接收者往往不是单一的. 如何将一个具备可计算性的密文安全地分享给一个任意选定的接收者集合, 是传统的全同态加密方案尚未解决的问题. 本文结合全同态加密和身份基广播加密的思想, 提出了新的密码学原型——全同态身份基广播加密(identity based broadcast fully homomorphic encryption, IBBFHE), 并基于LWE困难问题假设给出了具体的方案. 数据通过IBBFHE方案加密后允许不具备解密能力的第三方进行同态运算, 且仅能被指定集合内的接收者正确解密, 从而实现了云计算环境下数据的动态群组分享. 本文在LWE假设下, 证明了所提方案的抗半适应性选择身份集合选择明文攻击的安全性. 由于LWE 问题是公认的抗量子攻击难题, 本方案也具备抗量子攻击的安全性.

一种基于格签名算法的数字证书方案

李子臣, 梁斓, 孙亚飞
2018, 5(1): 13-20. 全文: PDF (1229KB) (200)
摘要

随着全球信息化时代的到来, 学习、办公、生活中都离不开网络的使用. 因此网络的安全问题也成为人们关注的焦点. 数字证书的出现很好地解决了网络的身份认证问题, 将用户身份与公钥通过权威第三方机构绑定到一起, 从而证明了用户身份的合法性. 数字证书认证技术更是为我国的电子政务与电子商务的安全保驾护航, 因此, 对数字证书的研究具有很大的意义. 现有的数字证书系统中使用的签名算法大都是基于大数分解或者离散对数, 而随着``量子计算机''的快速发展, 这些签名算法都面临着巨大的安全威胁. 针对这一问题, 提出了一种基于格理论的数字证书方案. 在方案中, 可信第三方证书授权中心(certificate authority, CA)在证书签发过程中使用的签名算法是基于格理论的, 其安全性是基于小整数解困难问题(small integer solution, SIS), 并证明了基于该算法设计的证书是不可伪造的. 这大大提高了证书的安全性. 与传统的RSA、ECDSA证书方案相比较, 本方案不仅可以抵抗量子攻击, 而且在安全比特相同的情况下, 具有更高的签名、验签效率. 与以往的格签名方案相比, 密钥以及签名值的尺寸更短, 便于在证书中存储.

针对诱骗态量子密钥分发方案的PNS攻击研究

李宏欣, 迟洋广, 韩宇, 闫宝, 王伟
2018, 5(1): 1-12. 全文: PDF (4140KB) (223)
摘要

量子保密通信技术的飞速发展, 展现了量子密码在通信领域巨大的应用潜力. 量子密码利用量子的物理属性来保证通信的无条件安全, 然而在实际通信系统中, 光源等设备的不完美性给通信系统带来了安全隐患. 针对使用非理想光源的量子密钥分发系统, 采用分束攻击可以获得通信密钥而不被发现. 本文首先介绍分束攻击的发展现状和基本原理, 然后对一种分束攻击改进方案的关键技术进行了研究. 基于对该方案的分析, 对传统的分束攻击进行进一步改进, 提出一种新的分束攻击方案。新方案针对非相位随机化光源, 根据不同光脉冲强度, 设计了一种计算分数器效率的方法, 该方法使得窃听者能够合理控制接收端计数率保持不变; 同时, 为了使得新方案更加实用化, 将光脉冲强度分为不同的安全区间, 针对每一个安全区间求出一个分数器效率使其保持接收端计数率波动在可接受范围内, 从而提高了攻击效率和攻击能力. 最后应用MATLAB拟合出分数器效率与光强之间的函数关系, 并且通过数值模拟以及数次优化证明了方案的安全性和可行性.

基于CPU多核的FHEW并行算法

杨晓元, 丁义涛, 周潭平
2017, 4(6): 620-626. 全文: PDF (481KB) (207)
摘要

全同态加密算法发展迅猛, 然而效率低下仍是其无法实际应用的关键因素. 为了进一步加快全同态加密算法的运行速度, 本文针对EUROCRYPT 2015上全同态加密算法FHEW存在大量独立矩阵和向量运算, 以及CPU多核适合大量独立数据的运算的特点, 提出并实现了FHEW方案的CPU多核并行算法. 首先, 通过分析比较FHEW算法四个主要过程的特点和运行时间, 发现该算法中最消耗时间是密钥生成过程和同态与非门电路(包含自举过程), 并且该两个过程中涉及大量独立的矩阵和向量运算. 所以, 本文对这两个过程进行了CPU多核并行优化. 其次, 考虑到算法中存在大量离散傅立叶变换和逆变换, 该变换和逆变换消耗大量时间和内存资源, 本文对离散傅立叶变换和逆变换函数中的大部分过程进行并行计算, 从而提升了离散傅立叶函数的运行速度, 进一步提高了方案效率. 最后, 分别运行原始算法和并行算法18次, 得到平均运行时间. 实验结果表明, 在相同的环境下, 密钥生成算法的运行时间由13,029 ms降至2434ms, 效率提高了4.35倍; 一次同态与非门电路运算的运行时间由298.5ms 降至81ms, 效率提高了2.68 倍.

一种高效的同态加密方案及其应用

杨浩淼, 金保隆, 陈 诚, 吴新沿
2017, 4(6): 611-619. 全文: PDF (1074KB) (220)
摘要

随着云计算与大数据技术的发展, 人们越来越关心数据的隐私保护. 如何在隐私保护的前提下完成云计算或大数据分析成为一个热门的研究课题. 同态加密方案允许在密文态下进行计算, 从而可以在不泻露数据内容的情况下完成计算, 理论上可以满足隐私保护计算的需求. 自从 Gentry的工作后, 学者们提出了许多全同态密码方案, 但由于这些密码方案进行同态计算的效率很低而难以实际应用. Zhou 提出的 VHE (vector homomorphic encryption)加密方案可以比较高效地进行整数向量的同态计算, 该方案是 Brakerski 的 PVW方案的整数扩展, 但比 PVW 方案有更强的计算能力. 但该方案存在一些安全问题, 导致其在实际应用中面临诸多安全威胁. 本文介绍了一种 VHE 的改进方案, 该改进方案比原 VHE 方案效率更高, 并且其安全强度更高. 本文对该改进方案做出了初步的安全分析, 试图给出其安全性描述. 为了验证加密方案的同态计算效率, 本文还基于改进后的方案构建了简单的邮件搜索应用, 相较于原本的 VHE 方案, 运算效率明显提高, 加密数据时的内存需求也大大减小, 使得该方案有了被应用在一般配置的计算机上的可能.

(全)同态加密在基于密文计算模型中的应用

蒋林智, 许春香, 王晓芳, 陈克非, 王保仓
2017, 4(6): 596-610. 全文: PDF (5733KB) (1208)
摘要

随着云计算和大数据的快速发展, 存储在云平台上数据的保密性、用户的隐私保护和数据商业利用一直是困扰学术界和产业界的难题.  如何在保证数据机密性和用户隐私的基础上, 实现数据的有效利用? (全)同态加密算法出现和快速发展为解决这个难题提供了一种有效方案选择. 文章中首先介绍了云平台中存储数据安全性、用户隐私保护和数据商业利用这三者之间的关系和实现这三者之间平衡的重要性. 接着, 文章给出了基于理想格的Gentry原始方案、基于RLWE 的BGV方案和FV方案的效率比较和分析. 在上述的比较和分析中, 文章给了具体的参数设置, 详细地分析了秘钥生成时间、加解密时间和密文同态操作时间. 通过分析发现, 基于RLWE的somewhat同态加密方案为很多涉及实际问题的计算模型和算法给出了比较高效的解决方案. 文章最后给出了基于BGV方案的两个somewhat同态加密应用案例, 并且给出相关的效率分析. 相关方案的效率分析和实验结果表明基于RLWE的somewhat同态加密方案是解决数据保密性、用户的隐私保护和数据商业利用的最有效方案.

无噪声全同态加密浅析

王励成, 李婧
2017, 4(6): 579-595. 全文: PDF (596KB) (233)
摘要

全同态加密无疑是当前国际密码学界的前沿热点课题之一. 自从Gentry发表第一个全同态加密方案以来, 已经有不少全同态加密方案被提出: 或基于不同的平台给出新的实现, 或进行效率方面的改进, 等等. 纵观这些全同态加密方案, 不难发现大多数均是基于``噪声''技术的: 一方面, 噪声在相关方案的底层密码学困难问题之所以困难方面扮演了很重要的角色; 另一方面, 对噪声累积的抑制往往也是方案构造的核心技术之一. 噪声这把双刃剑似乎成为构造全同态绕不开的一个工具, 噪声的引入和对噪声累积的抑制也往往成为制约全同态加密方案性能进一步提升的固有障碍. 能否设计出无噪声的全同态加密呢?尽管有许多人认为无噪声的全同态加密均是不安全的, 然而在没有严格证明这样的否定性结论之前, 对于无噪声全同态加密方案的探索始终是一个有意义的课题. 事实上, 人们确实已经提出了不少无噪声的全同态加密方案, 但目前仍没有一个可以在可证明安全框架下严格做到安全可行的方案. 本文主要围绕我们已知的无噪声全同态加密体制的设计思想和方案的安全性展开讨论.

全同态加密研究

李增鹏, 马春光, 周红生
2017, 4(6): 561-578. 全文: PDF (746KB) (386)
摘要

随着云计算模式的普及应用, 数据存储和计算服务的外包已经成为必然趋势, 由此带来的数据安全和隐私保护问题愈加受到业界和学界的关注. 全同态加密(fully homomorphic encryption, FHE)体制, 可在不泄露敏感信息的前提下完成对密文的处理任务, 有着与生俱来的保护用户数据安全和隐私的特性. 此外, 由于格密码具有可抵抗量子攻击和同态运算的特性, 这使得基于格的全同态加密研究备受关注, 成为近年密码学界研究的热点问题. 当前, 对全同态加密的研究主要集中在两方面, 一方面是方案的设计及性能的提升, 另一方面则是其潜在应用的探索. 因此, 本文从全同态加密所经历的三个阶段、基于格的全同态加密体制设计和全同态加密面临的问题及发展趋势等方面, 较为全面地介绍了自Gentry (STOC 2009)提出首个全同态加密体制后, 近几年来的重要研究成果.

同态加密专栏序言

陈克非, 蒋林智
2017, 4(6): 558-560. 全文: PDF (351KB) (1201)
摘要
        在希腊语中, ``´ιδιo''表示相同, 而``σχ´ηµα''表示态. ``同态''(homomorphism)在不同的领域被广泛地使用. 在抽象代数中, 同态定义为保留域和代数集合之间所有代数结构的映射. 映射仅仅是一个函数, 即一个操作, 它从域集合中获取输入并输出在一定范围内的一个元素(例如: 加法、乘法). 在密码学领域, 同态表示一种加密算法类型. 同态加密(homomorphic encryption, HE) 是一种加密方案. 在这种加密方案中, 它允许第三方(比如云服务器和服务提供商等)对加密的密文消息执行一定计算功能, 同时计算的结果保留加密状态. 从本质上来说, 这样的同态加密就对应于抽象代数中的一个映射. 比如加法HE方案, 对于两个明文消息m1m2, E表示加密函数, 第三方可以在不知道m1m2的情况下获得E(m1+m2)(E(m1+m2) = E(m1)+ E(m2)).
        通常, 加密是保护任何敏感信息隐私的关键机制. 然而, 在没有事先加密的情况下, 传统的加密方案不能对加密数据进行同态操作(homomorphic evaluation). 换句话说, 用户必须牺牲自己的隐私来使用云服务, 如文件存储、共享和协作. 此外, 在结束与用户之间的服务关系后, 不受信任的服务器、服务提供商和云服务提供商可以长期保存在为用户提供服务期间保留的用户信息. 这恰恰是用户隐私关注的重点. 最完美的情况是在用户数据保持加密的状态下, 第三方可以对加密数据进行不受任何限制的计算操作. 从密码学发展角度来看, 术语homomorphism由Rivest, Adleman和Dertouz-ous在1978年首次使用. 其后, 在全球范围内, 大量的密码学学者都围绕着这个问题来设计可以执行任意次计算操作的同态加密算法.
        推动同态加密方案出现的动机非常简单: 假设有这样一个计算需求. 客户端C首先加密用户拥有数据m, 然后将加密的数据发送到云端服务器S. 当客户端需要对自己加密的数据进行某个操作f(x)时, 用户将函数f(x)发送到云端S. 云端服务器S使用homomorphic evaluation对加密数据执行同态操作, 即, 在不知道明文数据具体值的情况下完成函数f(x)的计算. 计算结束后, 云服务器将计算结果返回给客户端C. 最后, 客户端$C$使用自己拥有的私钥解密返回的计算结果并获得f(m). 同态操作在云端服务器S中完成. 整个操作过程在不需要用户解密私钥的情况下, 云服务器S对加密数据执行任意次数加法和乘法操作.
早期, 能够执行加密数据计算/操作的方案是1982年提出的Yao混淆电路. 然而, 在计算中, Yao 混淆电路方案的密文尺寸会随着计算电路中每个门计算线性增长. 这样会导致Yao的方案计算效率太低, 而且大量的交互计算也导致协议的通信量太大. 直至2009年, 天才密码学学者Gentry在他的博士论文中给出了首个详细的且具有突破性的全同态加密方案(fully homomorphic encryption scheme, FHE). 前期, 密码学学者给出了大量的同态加密方案, 主要包括: Rivest et al. 1978, Goldwasser和Micali 1982, Yao 1982, ElGamal 1985, Benaloh 1994, Naccache 和Stern 1998, Okamoto和Uchiyama 1998, Paillier 1999, Sander et al. 1999, Damgard和Jurik 2001, Boneh et al. 2005, Kawachi et al. 2007和Ishai和Paskin 2007等方案. 这类方案只能执行一种同态加密操作(同态加法或者同态乘法), 或者只能执行非常有限次数的两种同态操作. 根据对同态加密操作可以执行的类型(同态加法和同态乘法)和执行同态操作次数, 我们可以将同态加密方案分为以下三种类型: (1)部分同态加密(partially homomorphic encryption). 这类方案只允许对密文执行一种同态操作或者只能执行非常有限次数的两种同态加密操作. (2) somewhat同态加密. 这种类型的方案来源于Gentry论文中的思想. 在构造全同态加密方案时, Gentry首先构造可以执行一定次数的同态加法和同态乘法操作的方案. 满足这样条件的同态加密方案称为somewhat同态加密. (3) 全同态加密方案(FHE). 在somewhat同态加密方案的基础上, Gentry使用压缩解密电路的Bootstrapping技术实现了可以执行任意次同态加法和同态乘法操作的FHE方案. 所有的FHE方案都不对两种同态操作有任何次数限制.
        构造各种同态加密方案的最终目的是为了获得可以执行无限次同态计算且实用的全同态加密方案. 在Gentry解决了全同态加密方案构造这个公开难题以后, 许多新的且效率更高的全同态加密方案被构造出来. 新构造的全同态加密方案主要是针对以下几个方面: 更小的密钥尺寸, 更短的密钥生成时间、加密和解密时间、同态操作效率更高和更小的密文尺寸以及能够支持更多的其它密文操作. 从Gentry原始方案的根本无法应用到可以满足应用需求的基于RLWE的somewhat同态加密方案. 从最初的单比特加密到基于Double-CRT密文编码和SIMD的同态并行操作, 同态加密方案的效率在不断提高. 从最初的基于普通计算平台(普通台式机和笔记本等)到基于专有硬件平台(graphics processing-GPU, application-specific integrated circuit, ASIC和field-programmable gate array, FPGA等), 各种效率优化算法(FFT和NTT等)也不断促进全同态加密方案在解决实际问题中的应用. 从单一的只满足同态计算的全同态加密方案, 到多密钥的全同态加密方案、基于身份和属性的全同态加密方案和安全多方计算的全同态加密方案等等. 全同态加密应用的效率和具有的功能都得到了不断地提升.
        全同态加密虽然给我们解决实际问题中的密文计算提供有效的解决方案. 但是, 同态加密算法的密文具有malleability特性, 因此云服务器可以修改加密数据. 构造具有更高安全性(CCA, CCA1 和CCA2)的全同态加密方案也是密码学界面临的重要挑战.
在《密码学报》``同态加密专栏'', 我们共刊登5篇从不同角度探讨同态加密方案的论文, 希望这些论文能给从事同态加密研究的同行提供一定参考. 同时, 对以下审稿人的辛勤工作表示感谢: 唐春明(广州大学), 王骞(武汉大学), Kan Yang (University of Memphis), 唐强(新泽西理工大学), 王安(北京理工大学)和王华群(南京邮电大学)等.
        (1) 第一篇论文的题目是《全同态加密研究》. 这是一篇关于全同态加密的综述性文章. 文章从三个方面介绍了近几年全同态加密发展过程中的重要成果: 1)全同态加密所经历的三个阶段, 2) 基于格的全同态加密体制设计和3) 全同态加密面临的问题及发展趋势.
        (2) 第二篇论文的题目是《无噪声全同态加密浅析》. 全同态加密方案是基于噪声来掩盖明文消息的概率加密方案. 噪声对于全同态加密方案至关重要, 但是噪声也影响着同态加密方案的效率. 这是一篇关于无噪声全同态加密的综述性文章. 文章主要围绕我们已知的无噪声全同态加密体制的设计思想和方案的安全性展开讨论. 在详细分析各种无噪声全同态加密方案构造方法的基础上, 也指出了无噪声全同态加密方案在安全性方面的不足.
        (3) 第三篇论文的题目是《(全)同态加密在基于密文计算模型中的应用》. 同态加密的应用和效率一直是密码学界和工业界关心的问题. 在详细分析实际中计算需求基础上, 此篇论文分析了现有的三种类型的同态加密方案在应用中的优势和缺陷, 并给出了Gentry原始方案、BGV和FV 三种同态加密方案的效率分析和实验结果. 在此基础上, 文章详细给出了基于BGV的somewhat同态加密方案的两个实际应用案例.
        (4) 第四篇论文的题目是《一种高效的同态加密方案及其应用》. 此篇介绍了一种VHE的改进方案, 该改进方案比原VHE方案效率更高, 并且其安全强度更高. 文章还基于改进后的方案构建了简单的邮件搜索应用.
        (5) 第五篇论文的题目是《基于CPU多核的FHEW并行算法》. 利用特殊的硬件实现全同态加密方案的效率优化是实现全同态加密应用的一种重要途径. 此篇文章提出并实现了FHEW方案的CPU多核并行算法, 实验结果表明并行算法使得原方案中密钥生成算法的速度得到提高和密文运算的时间也得到缩短.

基于不可能差分的SHA3-512约减轮区分攻击

丁瑶玲, 李璐, 贾珂婷
2017, 4(6): 545-557. 全文: PDF (4243KB) (105)
摘要

Keccak算法是一族具有海绵结构的杂凑函数, 由Bertoni等人设计, 是SHA3标准征集活动的最终获选算法. 对该算法的分析主要分为三类, 分别是对约减轮压缩函数的分析、对消息认证码和认证加密方案的分析以及对置换函数的区分攻击. 本文研究了Keccak算法的不可能差分性质, 给出了基于不可能差分特征的区分攻击方法. 我们发现在轮函数运算过程中, 位于同一列的两比特在经过线性层时异或值保持不变, 基于此性质我们构造了4轮置换函数的不可能差分特征. 考虑到不同版本中消息和摘要的长度各不相同, 并且会影响输入输出差分的选择, 我们筛选出了符合SHA3-512版本约束条件的不可能差分特征. 最后, 利用在非线性层的逆运算中, 当输入值满足一定条件时, 某些比特的输出差分与输入差分相等这一性质, 我们给出了4轮SHA3-512不可能差分区分攻击. 当数据量达到28.21个消息时, 将SHA3-512与随机函数区分开的成功率达到99%, 对应的时间复杂度为28.21次压缩. 我们以SHA-512作为随机函数, 实验验证了上述理论结果. 同等轮数下, 我们的攻击复杂度优于其他方法.

无条件安全的公平秘密共享方案

张本慧, 解晓娟, 唐元生
2017, 4(6): 537-544. 全文: PDF (766KB) (186)
摘要

秘密共享是现代密码学领域的一个重要分支, 是信息安全和数据保密中的重要手段, 在数字签名、安全多方计算、纠错码等领域有着重要的应用, 同时也被广泛应用于政治、经济、军事、外交. 现有的多数秘密共享方案都是基于Shamir的方法构造. 在Shamir的(t,n)门限方案中, 分发者将共享的秘密在n个参与者中分享, 使得其中任意t个或者更多个参与者合作可以恢复共享的秘密而少于t个参与者却不可以. 但是在Shamir 方案的秘密重构阶段, 如果t个参与者中有恶意的参与者出示虚假的子秘密而其余参与者都出示真实的子秘密, 即使这种攻击行为可以被检测到, 但不能阻止恶意的参与者获得正确的秘密, 而诚实的参与者却获得错误的秘密, 这对诚实参与者是不公平的. 针对这类攻击行为, 本文构造了一个公平的门限秘密共享方案, 并基于四种攻击模型(同步非合谋攻击、异步非合谋攻击、同步合谋攻击及异步合谋攻击)证明方案的安全性与公平性. 该方案无须任何密码学假设是无条件安全的, 这使得方案更加高效实用.

减轮Fruit算法的Cube攻击

孙移盛
2017, 4(6): 528-536. 全文: PDF (485KB) (155)
摘要

Cube攻击是由Dinur和Shamir在2009年的欧密会上提出的一种代数攻击方法, 它旨在从目标加密算法中提取关于未知变量的线性关系, 而难点是在寻找有效的Cube. 超轻量级序列密码具有速度快, 功耗低, 便于硬件实现等优点, 市场对超轻量级序列密码的需求很大, 使得密码学界对超轻量级序列密码算法的研究更加深入. 2015年Armknetcht等人对轻量级序列密码提出了一个新的设计方向, 在每轮密钥流比特的生成过程中重复使用初始密钥比特, 并基于此想法设计了一个超轻量级序列密码算法Sprout, 使得内部状态大小与密钥大小相同, 打破了超轻量级序列密码设计的瓶颈. Fruit是2016年由 Ghafari等设计的一种超轻量级流密码, 其设计目的是在保证内部状态很小的同时能避免时间-存储-数据折衷攻击. 本文对减轮的流密码Fruit作Cube攻击, 在随机选取Cube方法的基础上提出一些寻找Cube的新想法, 并最终对减轮的83轮(最高可到86轮)Fruit算法做Cube攻击求得80个密钥中的17个密钥, 比穷尽搜索降低了217的复杂度. 并发现找到的线性多项式只与密钥的后17比特有关, 没有发现关于密钥前63比特的线性表示, Fruit算法的轮密钥函数导致的结果, 对轮密钥函数的分析有很好的借鉴意义.

轻量级分组密码PRINCE算法的Biclique分析

袁征, 彭真
2017, 4(6): 517-527. 全文: PDF (3937KB) (266)
摘要

PRINCE算法是Rechberger等人在2012年亚密会上提出的一个对合轻量级分组密码算法, 广泛应用于资源受限的设备. PRINCE算法的分组长度为64比特, 密钥长度为128 比特. 算法基于FX结构, 一部分密钥用于核心算法PRINCEcore, 剩余的密钥用作PRINCEcore 前后的白化密钥. PRINCEcore算法也是一个分组密码算法, 保持PRINCE算法主要的加密过程. Biclique分析是一种新的分组密码分析方法, 受到密码学者的广泛关注. Abed等人利用Biclique攻击方法给出了全轮PRINCEcore算法的攻击结果, 计算复杂度为262.72次加密, 数据复杂度为$2^{40}$个选择密文. 受其启发, 我们也给出了PRINCE 算法抗两类Biclique分析的结果. 本文中, 我们首先介绍了平衡Biclique和星型Biclique的结构, 以及Biclique密码分析的一般流程; 其次, 我们简单介绍了PRINCE 算法的结构. 然后, 我们对Abed的方法进行改进, 构建了一个1轮的平衡Biclique结构, 计算复杂度为262.69, 数据复杂度为232个选择明文, 二者均优于之前的攻击结果. 最后, 我们也构建了一个基于星型的Biclique结构, 攻击的计算复杂度为263, 而数据复杂度仅需一个明密文对, 这是目前为止对PRINCEcore算法全轮分析数据复杂度最优的分析结果.

Page 1 of 12 222 records
版权所有 © 密码学报
技术支持: 北京玛格泰克科技发展有限公司