Journal of Cryptologic Research
 
引用检索 快速检索 DOI 高级检索
在线期刊
   » 最新录用
   » 网络预发表
   » 当期目录
   » 过刊浏览
   » 按栏目浏览
   » 综述文章
   » 摘要点击排行
   » 全文下载排行
  作者在线投稿
   » 作者投稿/查稿
   » 投稿须知
   » 模版下载
   » 版权协议
  专家在线审稿
   » 审稿登录
   » 审稿政策
   » 自荐为审稿人
密码学报  
  密码学报--2017, 4 (6)   Published: 2017-12-28
选择 | 合并摘要
学术论文

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

袁征, 彭真
密码学报. 2017, 4 (6): 517-527.
全文: HTML (1 KB)  PDF (3937 KB)  ( 138 )
摘要 ( 122 )

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算法全轮分析数据复杂度最优的分析结果.

减轮Fruit算法的Cube攻击 Hot!

孙移盛
密码学报. 2017, 4 (6): 528-536. ;  doi: 10.13868/j.cnki.jcr.000204
全文: HTML (1 KB)  PDF (485 KB)  ( 97 )
摘要 ( 77 )

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算法的轮密钥函数导致的结果, 对轮密钥函数的分析有很好的借鉴意义.

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

张本慧, 解晓娟, 唐元生
密码学报. 2017, 4 (6): 537-544. ;  doi: 10.13868/j.cnki.jcr.000205
全文: HTML (1 KB)  PDF (766 KB)  ( 115 )
摘要 ( 100 )

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

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

丁瑶玲, 李璐, 贾珂婷
密码学报. 2017, 4 (6): 545-557. ;  doi: 10.13868/j.cnki.jcr.000206
全文: HTML (1 KB)  PDF (4243 KB)  ( 53 )
摘要 ( 45 )

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

专栏序言

同态加密专栏序言 Hot!

陈克非, 蒋林智
密码学报. 2017, 4 (6): 558-560. ;  doi: 10.13868/j.cnki.jcr.000207
全文: HTML (1 KB)  PDF (351 KB)  ( 840 )
摘要 ( 364 )
        在希腊语中, ``´ιδι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多核并行算法, 实验结果表明并行算法使得原方案中密钥生成算法的速度得到提高和密文运算的时间也得到缩短.
专栏综述

全同态加密研究 Hot!

李增鹏, 马春光, 周红生
密码学报. 2017, 4 (6): 561-578. ;  doi: 10.13868/j.cnki.jcr.000208
全文: HTML (1 KB)  PDF (746 KB)  ( 200 )
摘要 ( 95 )

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

无噪声全同态加密浅析 Hot!

王励成, 李婧
密码学报. 2017, 4 (6): 579-595. ;  doi: 10.13868/j.cnki.jcr.000209
全文: HTML (1 KB)  PDF (596 KB)  ( 124 )
摘要 ( 53 )

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

专栏论文

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

蒋林智, 许春香, 王晓芳, 陈克非, 王保仓
密码学报. 2017, 4 (6): 596-610. ;  doi: 10.13868/j.cnki.jcr.000210
全文: HTML (1 KB)  PDF (5733 KB)  ( 843 )
摘要 ( 367 )

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

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

杨浩淼, 金保隆, 陈 诚, 吴新沿
密码学报. 2017, 4 (6): 611-619. ;  doi: 10.13868/j.cnki.jcr.000211
全文: HTML (1 KB)  PDF (1074 KB)  ( 134 )
摘要 ( 89 )

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

基于CPU多核的FHEW并行算法 Hot!

杨晓元, 丁义涛, 周潭平
密码学报. 2017, 4 (6): 620-626. ;  doi: 10.13868/j.cnki.jcr.000212
全文: HTML (1 KB)  PDF (481 KB)  ( 75 )
摘要 ( 74 )

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

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