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

基于CPU多核的FHEW并行算法

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

全同态加密算法发展迅猛, 然而效率低下仍是其无法实际应用的关键因素. 为了进一步加快全同态加密算法的运行速度, 本文针对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) (134)
摘要

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

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

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

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

无噪声全同态加密浅析

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

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

全同态加密研究

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

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

同态加密专栏序言

陈克非, 蒋林智
2017, 4(6): 558-560. 全文: PDF (351KB) (840)
摘要
        在希腊语中, ``´ιδι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) (53)
摘要

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) (115)
摘要

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

减轮Fruit算法的Cube攻击

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

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) (138)
摘要

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

常量噪声下带辅助输入的LPN公钥密码

程海涛, 韩刚, 钱海峰
2017, 4(5): 506-516. 全文: PDF (616KB) (170)
摘要

在STOC 2009上, Dodis, Kalai和Lovett研究了(静态的)带有指数级难以求逆辅助输入的LPN (Learning Parity with Noise)问题的困难性, 他们通过引入一个新的假设(被称为带噪声的子空间学习问题, Learning Subspace with Noise)证明了LPN问题在高噪声条件下是准多项式(quasi-polynomial)困难的, 然而他们的结果并未在LPN 的标准假设下得到证明. 本文将介绍Yu(ePrint 2009/467) 以及Goldwasser等人在ITCS 2010上提出的``从子空间中取样(sampling from subspace)''技术, 利用该技术Yu等人(CRYPTO 2016)证明了标准LPN蕴含了一种新的健壮的(抗泄漏)工作模式. 换而言之, 常量噪声(constant-noise)的LPN在带有亚指数级难以求逆的辅助输入时仍具有与标准LPN假设下可比拟的安全性. 更进一步,在亚指数级困难(即),  n为密钥大小)常量噪声LPN假设下, Yu 等人(CRYPTO 2016)基于poly-logarithmic熵源得到一种LPN问题变体, 并进一步构造CPA/CCA 安全公钥加密(PKE)方案和不经意传输(oblivious transfer, OT) 协议, 从而证明了标准LPN蕴含公钥加密. 在此之前(特别是自Alekhnovich发表在FOCS 2003的工作以来), 如何在常量噪声LPN假设下构造PKE和OT一直是未解决的公开问题.

基于联立丢番图逼近的子集和问题启发式求解算法

王保仓, 卢珂
2017, 4(5): 498-505. 全文: PDF (490KB) (160)
摘要

子集和问题是计算机科学中的一个重要问题, 也被应用于公钥密码和伪随机函数的设计. 学界已提出多个求解一般子集和问题的通用求解算法及求解特定子集和问题的特殊求解算法. 本文通过建立子集和问题和联立丢番图逼近问题之间的联系, 提出一种新的子集和问题启发式求解算法. 该算法由给定的子集和问题构造联立丢番图逼近问题, 使用格归约算法寻找该联立丢番图逼近问题的解, 由此构造与原始子集和问题线性无关的新的子集和问题, 从而达到降低原始子集和问题维数的目的; 最后, 通过n-1个联立丢番图逼近问题的解来构造n-1个线性无关的子集和问题, 并通过求解一个由n个变量和n个线性方程构成的方程组来求解原始子集和问题. 基于联立丢番图逼近的子集和问题启发式求解算法为子集和问题研究提供了新的思路.

基于格的后量子密钥交换研究

刘亚敏, 李祥学, 刘晗林
2017, 4(5): 485-497. 全文: PDF (548KB) (357)
摘要

理论上量子算法可高效破解基于整数分解类和离散对数类等经典数论假设的密码体制; 近年来量子计算机的研制进展迅速, 使经典公钥密码面临现实威胁. 因此, 设计后量子密码系统是当前密码学研究以及标准制定中的重要课题. 其中以后量子密钥交换协议的需求最为迫切, 因此成为近年来的热点研究方向. 本文主要关注基于格上的计算困难问题, LWE, 环LWE和模LWE设计的后量子密钥交换协议, 尤其是最基础的无认证密钥交换协议, 包括BCNS15, NewHope/NewHope-Simple, Frodo, Kyber.KE等. 本文将介绍这些协议中的关键技术, 参数选取, 以及通信量, 计算效率和安全性等指标.

基于格的哈希证明系统的构造综述

来齐齐, 杨波, 禹勇, 陈原, 顾小勇
2017, 4(5): 474-484. 全文: PDF (1015KB) (283)
摘要

自从2002年Cramer和Shoup首次提出哈希证明系统(Hash Proof System)的概念以来, 人们逐渐发现了其所蕴含的巨大密码学价值. 作为对某一个NP语言的特殊非交互式零知识证明系统, 哈希证明系统在密码学理论的发展过程中有着不可替代的作用. 到目前为止, 对哈希证明系统的研究依然是密码学界一个热点话题. 尤其是随着后量子密码时代的到来, 对具有抗量子计算攻击特性的哈希证明系统的研究显得更为重要. 本文首先概述了哈希证明系统的概念、密码学用途及在传统困难假设下的一般化构造方法. 然后分别给出哈希证明系统、基于身份哈希证明系统和基于属性哈希证明系统的形式化定义以及各个定义中的关键点. 最后, 着重对基于格困难问题构造哈希证明系统的研究现状进行了总结和梳理,分析了一些具有代表性的已有构造的特点, 并指出当前基于格构造哈希证明系统的研究过程中所面临的一些问题.

后量子密码专栏序言

郁昱
2017, 4(5): 472-473. 全文: PDF (140KB) (379)
摘要
密码技术是信息安全的核心技术, 是网络空间安全的基石. 随着互联网的普及和信息技术的迅猛发展, 密码学的重要性日益凸显. 早期的密码学仅用于军事外交等少数机要通信的应用场景, 所使用的密码算法也主要集中于流密码等对称密码算法. 直到1976年, Diffie和Hellman在《密码学的新方向》中首次提出了公钥密码的思想, 开启了密码学的新时代. 经过40余年的发展, 公钥密码算法取得了巨大成功, 诸多代表性算法(如RSA加密算法、Diffie-Hellman密钥交换协议、ECDSA签名算法)相继问世且被广泛应用于我们的现实生活中, 保障着我们的数据财产安全和个人隐私.
然而随着量子计算理论的发展, 一些经典(图灵机)模型下的困难问题被发现在量子计算模型下可以被有效求解, 如Shor算法能够在量子模型下多项式时间内解决经典的离散对数问题和大整数分解问题. 换而言之, 一旦有足够规模的量子计算机诞生, 这将给现有的公钥密码体系带来灾难性的后果.
虽然量子计算机能否实现或何时实现还存在争议, 但各国政府及研究机构已发起了设计在经典和量子计算模型下安全的各类公钥密码算法的重大研究计划, 从而达到逐步替代现有密码算法以确保信息安全的目的. 目前, 该研究方向已成为一个极重要和活跃的新兴密码学研究方向, 通常被称为``后量子密码学(Post-Quantum Cryptography)''或``抗量子密码学(Quantum-Resistant Cryptography)''. 许多发达国家已着力加强后量子密码的研究, 并设立了各类重大研究支持计划, 如欧盟的SAFEcrypto项目、日本的CryptoMathCREST密码项目等. 此外, 美国国家安全局(NSA)已于2015年8月宣布了抗量子密码算法的迁移计划. 同年, 美国国家标准与技术研究院(NIST)举行了``后量子世界的网络安全研讨会(Workshop on Cybersecurity in a Post-Quantum World)'', 并宣布将于2017开始征集后量子公钥密码算法, 并用3–5年的时间对征集的算法进行评估.
根据底层困难问题的不同, 后量子密码主要可以分为: 基于编码的密码, 基于格的密码, 基于哈希的密码, 以及基于多变量的密码. 除了之外, 近几年还有一些其它抗量子攻击特性的密码体制, 如David Jao 等人基于普通椭圆曲线或超奇异椭圆曲线同源问题提出的密码算法.
在本期《密码学报》``后量子密码''专栏中, 我们刊登了4篇论文, 希望对从事这一研究方向的同行有参考价值.
第1篇论文题目是《基于格的后量子密钥交换研究》. 对后量子密钥交换协议的需求在几种后量子公钥密码原语中是最紧迫的, 而基于格构造的密钥交换协议在参数尺寸和计算效率方面均有不错的表现, 因此广受关注. 该论文主要总结了近年来基于格构造的几类实用化密钥交换协议的发展, 介绍了其中使用的关键技术, 并对它们的计算效率和通信量等指标进行了比较.
第2篇论文题目是《基于格的哈希证明系统的构造综述》. 哈希证明系统是针对于某一个NP语言的特殊非交互式零知识证明系统, 在可证明安全的公钥密码学理论的发展过程中有着不可替代的重要作用. 虽然经过了十多年的深入研究, 该密码学原型依然是多种新型密码学方案和协议构造的基础. 本论文较全面地总结了基于格困难假设构造哈希证明系统的主要研究进展, 并指出了目前相关构造过程中所面临的一些问题.
第3篇论文题目是《基于联立丢番图逼近的子集和问题启发式求解算法》. 子集和问题是计算机科学中的一个重要问题, 也被应用于抗量子公钥密码和伪随机函数的设计. 本文通过建立子集和问题和联立丢番图逼近问题之间的联系, 利用联立丢番图逼近生成子集和问题, 这新生成的子集和问题与原始的子集和问题是线性无关的, 这样就可以构造一个线性方程组. 通过求解这个线性方程组, 进而得到原子集和问题的解.该启发式求解算法为子集和问题研究提供了新思路.
第4篇论文的题目是《常量噪声下带辅助输入的LPN公钥密码》. Learning Parity with Noise(LPN)是著名的解码线性随机码问题, 同时也是Learning With Errors(LWE)在二元域上的简化版. LPN在最坏意义下是NP完全问题, 也是在量子模型下计算困难问题. 该文介绍了如何基于常数噪音的LPN问题构造可证明安全的后量子公钥密码算法.
最后, 我们希望通过该专栏能进一步加深大家对后量子密码的认识与了解, 激发密码工作者对后量子密码的研究兴趣, 并积极投身于后量子密码算法的研究中, 为我国网络空间安全的发展作出贡献.

一种新型抗功耗分析的电流平坦化电路有效性研究

顾勇, 王晨旭, 周童, 管旭光, 罗敏
2017, 4(5): 458-471. 全文: PDF (4689KB) (117)
摘要

差分功耗分析是一种有效的密码芯片侧信道攻击方法, 攻击者通过监测芯片的功耗曲线就可以分析出芯片内的密钥, 对密码设备的安全性造成了严重威胁. 为提高密码芯片抗功耗分析攻击的能力, 本文提出了一种基于功耗平衡原理的新型电流平坦化电路, 该电路独立于密码算法实现, 不影响密码芯片的原有设计流程. 电流平坦化电路增加了电路的可配置性控制电流, 实现了平坦电流的分级灵活控制, 减小了系统相对功耗, 又能够灵活适配于具有不同峰值电流的密码芯片, 使电流平坦化电路的应用变得更加灵活, 增强了系统的鲁棒性. 电流平坦化电路由可配置电流检测模块、可配置参考电压模块、电流补偿模块、基准电流模块、折叠共源共栅放大器、无源低通滤波器六部分组成. 本文采用SMIC 65 nm CMOS工艺对电路进行了设计与实现, 芯片核心电路面积0.071 mm2, 功耗小于5 mA. 实测结果表明: 该电路能在较宽的频率范围内有效工作, 2.17 ns响应时间及时隐藏密码芯片的电流变化, 平坦化电流值0--32 mA 可配置调节, 电源端的电流波动衰减可达96%.

高效防重放体域网IBS方案

黄一才, 张星昊, 郁滨
2017, 4(5): 447-457. 全文: PDF (899KB) (83)
摘要

对体域网中广播消息的认证是防止传感器节点接收攻击者恶意控制指令的关键步骤, 数字签名是解决消息认证的有效方法. 由于体域网层次结构及节点计算和存储资源的限制, 无法支撑基于数字证书的公钥密码体制. 基于身份的数字签名更适合在人为操作较少的传感器网络中实现, 但当前随机预言机模型下的IBS方案在现实场景中的安全性还存在争议, 而标准模型下的IBS方案往往计算量较大. 因此, 基于Paterson方案提出一种高效的体域网IBS方案, 并在标准模型下将方案的安全性归约于CDH问题假定. 首先对Paterson方案、$\text{李}$-姜方案和谷方案中存在的问题进行了分析和研究; 其次, 在体域网通信模型下, 设计了一种新的参数构造方式, 结合在线/脱线联票机制, 不仅降低了方案的在线计算量, 更大大减小了签名算法的公开参数规模, 且安全性证明在询问阶段不会中止; 最后, 通过理论分析和实验测试证明了签名的不可伪造性和方案的效率. 与以往标准模型下可证安全的签名方案相比, 该方案具有更高的效率, 更适合体域网等资源受限的应用场景.

缩减轮数的Keccak区分器攻击

刘新光, 周界, 于红波
2017, 4(5): 431-446. 全文: PDF (1911KB) (171)
摘要

2012年, Keccak在SHA-3算法竞赛中脱颖而出成为SHA-3算法标准. 自此之后对Keccak算法的分析成为研究热点. 本文探究的是对缩减轮Keccak杂凑函数的差分区分器攻击. 在已有研究中, Sourav 和Meier等提出了一种6轮的Keccak区分器, 该区分器基于TDA算法、Double Kernel结构和Keccak内部置换的差分传播特性, 得到的区分器复杂度为252. 本文在上述结果的基础上, 首先改进了Willi Meier等提出的差分路径, 得到了一个更优的6轮差分区分器, 该结果为目前已知最好的6轮差分区分器, 数据复杂度为228; 接着文章探究7轮的差分区分器,按照新的差分路径, 文章得到了新的7轮差分区分器, 但是因为在差分路径中Keccak内部函数的扩散作用, 增大了得到该差分路径的数据复杂度. 文章通过对于S盒性质的分析, 提出了一种S盒控制技术, 通过忽略一些对结果中的偏置位没有影响的S盒, 能够很好地降低得到该区分器的数据复杂度, 从而保证在7轮之后的输出中存在偏置位, 得到了一个复杂度为268的7 轮Keccak 区分器.

广义多项式函数单圈性判定的一个新证明

瞿成勤, 周学广
2017, 4(5): 423-430. 全文: PDF (356KB) (162)
摘要

T-函数是由Klimov和Shamir在2002年提出的一类新的非线性函数, 这种函数软硬件实现速度快、效率高, 而且所生成的序列线性复杂度高、稳定性强, 故有望代替线性反馈移位寄存器, 成为新的序列密码设计的非线性驱动环节. 多项式函数作为一类密码学中常用的T-函数, 其可逆性、周期性一直是相关研究中的重要问题, Klimov利用函数的代数正规型给出了多项式函数是单圈的充分条件, 同时借助于``bit-slice''方法和参数的概念给出了广义多项式函数是置换的充分条件. 进一步地, 刘卓军等借助于徐克舰的2-adic整数的乘法公式,给出了函数单圈性的判定定理. 本文利用1-Lipschitz函数模2-微分理论, 发展使用模4-微分确定遍历变换的技术, 并结合``bit-slice''方法, 给出函数遍历性判定的一种新方法, 进而给出了此类函数单圈性判定定理的一个新证明.

对PICO和RECTANGLE的零相关线性分析

马楚焱, 刘国强, 李超
2017, 4(5): 413-422. 全文: PDF (1177KB) (31)
摘要

混合整数线性规划是一种解决优化问题的常用方法. 2012 年, Mouha 等人首次将该方法应用于密码算法的安全性评估, 成功实现了对活跃S盒数下界的求解. PICO和RECTANGLE均为SPN型结构的轻量级分组密码算法, 目前对于这两种算法的零相关线性分析研究尚待完善. 本文首先针对PICO算法的零相关线性逼近问题, 建立基于混合整数线性规划的模型并进行路径搜索, 找到大量7 轮PICO算法的零相关线性逼近, 优于设计者给出的4轮零相关线性逼近. 进一步地, 通过构造7 轮多维零相关线性区分器, 对含白化密钥的10 轮PICO算法进行密钥恢复攻击. 该攻击能够恢复共50比特轮子密钥, 其时间复杂度为268.7次10轮PICO 加密, 数据复杂度为263.3个已知明文, 存储复杂度为242.3字节. 最后, 本文针对RECTANGLE算法的零相关线性逼近问题, 采用类似方法进行搜索, 同时借助算法本身的传播性质, 找到了208条8轮RECTANGLE的零相关线性逼近, 并给出了11 轮RECTANGLE 的零相关线性攻击. 该攻击可恢复共44比特轮子密钥, 其数据复杂度为263个已知明文, 时间复杂度为2107次11轮RECTANGLE 加密运算.

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