期张明武等高效弹性泄漏下安全公钥加密体制 ,/+9$/+&):488&+&,8,&18&+:8&99+:8&4'8 8&8/8& 9,1' :&8&:8&, &8/**8 1&4:,:+8' &):9-8/'89,+/),'18,.9+&):488&+&,8*):&9

Size: px

Start display at page:

Download "期张明武等高效弹性泄漏下安全公钥加密体制 *,/+9$/+&):488*&+&,8,&18*&+:8*&99+:8*&4*'8 8&8/8& 9,*1' :&8&:8*&, &8/**8 1&4:,:+8*' &):9-*8/'89,+/),'18,*.9+&):488*&+&,8*):&9"

瞬窦
5 years ago
Views:

1 第卷第期年月计算机学报!"#$ %&' & " 高效弹性泄漏下安全公钥加密体制张明武陈泌文何德彪杨湖北工业大学计算机学院武汉波陕西师范大学计算机学院西安中国科学院信息工程研究所信息安全国家重点实验室北京武汉大学软件工程国家重点实验室武汉摘要公钥密码体制中要求算法和公钥是公开的而密钥必须是严格保密的但在实际应用系统中攻击者可以从保密密钥和加密系统内部通过侧信道攻击等手段获得部分密钥一旦密钥被泄漏传统的可证明安全将无法归约弹性泄漏密码体制用于解决密钥随机数或内部中间状态等存在泄漏情况下的可证明安全问题该文提出一种应对密钥弹性泄漏的公钥加密方案达到抗泄漏条件下的自适应选择密文安全性在 &1 方案的基础上利用密钥衍射和消息认证码提高系统计算效率同时有效降低密钥长度并通过随机提取器达到密钥的弹性泄漏容忍在保持提取器性能不变的条件下降低密钥的长度提高了密钥允许的泄漏率分析显示本方案能容忍 ( 的密钥泄漏率密钥生成加密和解密分别相当于和个单指数计算量和其他方案比较泄漏率密钥长度和计算量等效率都有一定改善关键词密钥弹性泄漏公钥加密选择密文攻击密钥衍射函数中图法分类号 $# 号 #!"#$%&'%" 2 "*134 "*3 56*& 726&!"#$%#&' '''!"#' '#''#'#'(%%)'*#+,% '#''#-'(%%&'!"#&' "'89*8*&':4;'*++:8&1:/*8*,4*98/8,+8,)4,8;,',8&9*-/*+/8/:&;',+4*8-*''&,*,*1';*8&,+8*,'9$/8 *,*8*,+&))&',,4)98/88/,+8,*8'+&):488*&,99&),, &:48&8'9,*,9&'8/+:8&1:/*+'1&*8/),98/:4;'*+, :4;'*+9+;'98&8/:&,,*;'8+,&-*:+8*+',,8),)8+, &),*9.+/',4+/,+&'9;&&88+,8*)8+,9:&-9*,,*:8*&,+&;8*,&)*&)8*&&)8/,+8,&8/,88,&+:8&,,8) 1.,*'*8:8&,,8) :&*9,::&+/8&&;8*8/:&;',+4*8*8/:,+&'1&,+89&),,9*8',888/*,::-:&:&,,+4'1.,*'*8:4;'*++:8*&*-/*+/9*8*&4+8*&9),,148/8*+8*&+&9 4,98&*):&8/*+*+6,*9,,8&19&),,8+8&*,',&4,98&8&'8 8/'198/84&8+8&8/,*.&,+8*,94+998/'18 收稿日期最终修改稿收到日期 ( 本课题得到国家自然科学基金湖北省自然科学基金! 信息安全国家重点实验室开放基金和湖北工业大学高层次人才项目资助张明武男年生博士教授中国计算机学会! 高级会员主要研究领域为密码技术隐私保护和网络安全协议 )*'+,)-./11)*'+&) 陈泌文男年生硕士研究生主要研究方向为网络与信息安全何德彪男年生博士副教授主要研究方向为信息与网络安全杨波男年生博士教授主要研究领域为密码学与信息安全

2 期张明武等高效弹性泄漏下安全公钥加密体制 *,/+9$/+&):488*&+&,8,&18*&+:8*&99+:8*&4*'8 8&8/8& 9,*1' :&8&:8*&, &8/**8 1&4:,:+8*' &):9-*8/'89,+/),'18,*.9+&):488*&+&,8*):&9 ('$" '1,*'*+:4;'*++:8*&+/&,+*:/888+9*8*& 4+8*& ) 引言传统公钥密码体制要求密钥对所有可能的攻击来说是完全保密的只有公钥和密码算法是完全公开的但在实际开放式系统中攻击者可以通过侧信道攻击获得有关密钥的部分信息如通过检测关机后的内存获得部分存储于内存的敏感信息 ( 通过时间攻击获得密钥或随机数的分布通过检测电磁辐射获得通讯信道的数据等传统应对侧信道攻击的方法是通过检测到可能的攻击然后提高硬件抵抗攻击的能力或改进算法强度但是这些手段不能从根本上容忍敏感信息弹性泄漏的产生从而达到既有方案的可证明安全性弹性泄漏密码体制 1.,*'*8:8& 1:/ 允许攻击者在获得密码系统中部分不可公开的敏感信息的条件下实现其可证明安全 ( 性该概念最早由 * 等人于年提出并设计出公钥密码体制中密钥泄漏及可证明安全的密钥弹性泄漏加密方案为了能模拟可能的侧信道攻击允许攻击者自由选择一个满足可能条件的泄漏函数为了模拟实际的泄漏设定攻击者能够访问泄漏预言机 1+' 从而获得关于密钥的任何多项式时间可计算函数的输出前提是所设计的泄漏函数不能获得完整的秘密钥否则攻击者能力与一个合法用户等价在具体的泄漏弹性密码方案中需要考虑不同类型的泄漏函数以设计抵抗不同攻击的安全方案最典型的泄漏函数有种方法表达输出有界泄漏函数 6&499 1 这类泄漏允许攻击者获得密钥中任何部分信息只要保证对密钥的输出长度不超过系统预先设定的界密钥熵泄漏 8&: 1 它允许攻击者获得比密钥更长的信息但要保证密钥仍存在一定量的最小熵辅助输入泄漏 4*'*:48 1 允许获得密钥有关的任何输出但要保证该泄漏函数在多项式时间上不可逆一种简化的泄漏模型是密钥暴露该模型中泄漏函数是简单的密钥或密码内存的子集与基于密钥暴露的密码相比弹性泄漏函数可定义为自适应的任意可计算的函数如攻击者根据公钥或已有的泄漏知识来定义新的密钥泄漏函数因而具有更强的攻击能力 & 和 1 在 )/&4: 提出哈希证明系统,/#&&,8)# 的基础上提出有界泄漏模型下的公钥加密方案并容忍 # 安全下 ( 的泄漏率和安全下的泄漏率后来 '- 等人改进文献的工作构建了边界检索模型的泄漏弹性泄漏公钥加密方案采用在硬件上不同的存储区域来组织密钥并要求多个密钥存储模块不能同时被泄漏可达到 ( 的泄漏率 '- 等人首次提出在有界提取模型下密钥弹性泄漏模型并构造在基于格二次剩余双线性对等多种安全假设下的加密方案 '* 和 * 提出熵安全的密钥弹性泄漏方案仅达到 # 安全性为容忍弹性泄漏往往会增加密钥或密文的长度同时也会增加系统的计算复杂度 & 和 741 给出直接利用 # 安全的公钥系统构造安全的方案它采用双重加密体制并引入零知识证明用以保证两次加密是针对同一明文其抗泄漏性在文献中也得到证明但糟糕的效率影响到在实际中的应用改进系统的性能同时提高系统密钥泄漏容忍的能力这是研究人员不断研究的热点 * 等人在文献的基础上提高了公钥加密系统的泄漏率 *4 等人改进 # 的构建方法来提高明文消息空间 14 等人采用高效的哈希函数提高公钥加密系统的计算效率文献中提出了利用对偶系统加密技术容忍密钥有界泄漏并支持不同策略函数的表达所提出的方案在双线性群中构造密钥和密文及计算代价都比 ( 较大 * 等人提出结合哈希证明系统和一次性有损过滤器来构造安全的公钥加密方案

3 计算机学报年 8/ 等人借助于通用参考串模型设计了基于连续泄露模型下的交互式证明系统本文设计一个适应性选择密文安全的密钥弹性泄漏公钥加密方案在 &1 方案基础上引入密钥衍射和消息认证码提高系统的计算效率同时有效降低密钥和密文的长度并通过随机提取器达到密钥的弹性泄漏容忍在保持提取器性能不变的条件下降低密钥长度同时可以提高密钥允许的泄漏率在 ( 的密钥被泄漏的情况下所提出的方案仍是可证明安全的比文献中的方案所容忍泄漏率提高了比文献中基于 5 假设的方案泄漏率提高本文第节介绍基础知识及相关基础理论第节给出弹性泄漏语义安全性的模型及定义第节给出方案的设计思想和详细构造并对方案的性能作分析和比较第 ( 节给出方案抗弹性泄漏安全性的形式化证明第节给出本文方案的实际应用第节对本文工作小结并提出今后的研究方向预备知识 *) 基本知识本文中定义为密码系统的安全参数 / 是密钥泄漏界定义为对参数在计算上可忽略的函数有限域 1 <= 设表示二进制串表示的长度除特别指明外本文中所有对数 '&1 的基为为对方案的设计安全性证明和性能分析提供理论分析给出相关基础概念与定义定义 ) 最小熵设是在概率总体上选取的随机变量随机变量的最小熵定义为 <='&1) #< 最小熵表示在没有附加信息的条件下可以猜出随机变量的概率 #< = 这里 < 对攻击者来说最好以最大的概率预测出该随机变量值的可预测性表示为 ) #< 例如对于二进制上长的随机变量 #< < 对 #<< 的最小熵是但其香农熵是? '&1 密码系统中对于秘密信息的分布我们要求具有较大的最小熵随机且均匀分布引理 ) 设是两个随机变量则?'&1 证明 <='&1) #<<# # <='&1) #<#<#< # ='&1) #< <?'&1 证毕根据随机变量的平均情况下关注随机变量的最坏情况在给定的条件下关于的平均条件最小熵定义如下定义条件最小熵在已知下的条件最小熵定义为 '&1( # # 引理设是随机变量 / 不大于 / 长度的二进制串则 / / 该引理表明对一随机变量泄漏 / 比特信息量将会减少其最小熵最多是 / 由引理可知对任意函数有如下引理引理 + 对任意函数 / =/ 例如公钥 #@<% % 则公钥 #@ @=#@<'&122 是群的阶这种密钥格式表明公钥泄漏密钥的信息量不超过密钥的一半定义 + 统计距离若随机变量则与的统计距离定义为 5 < # <=# < <) # )=# ) ) 若两个变量的统计距离最多是称两个变量是. 接近的记为! 是均匀独立的随机变量记 *<5!*<5! 熵的大小代表对应变量的不确定性统计距离则能界定变量之间的相似性或不可区分性二者结合有助于构造安全密码协议并进行定量的可证明安全性能分析引理, 对任何随机变量及任一函数 55

4 期张明武等高效弹性泄漏下安全公钥加密体制 ( 证明显然对任意函数的信息量不大于全部即对任意变量的最大可能性是泄漏全部的证毕定义, 计算性不可区分对任一概率多项式时间算法 ) 两个概率总体满足 #)< =#) < 则称和对算法在安全参数上是计算不可区分的引理 - 区分引理设和 1 是概率分布上的事件 1< 1 则 # = # #1 证明 # =# <# 1?# 1= # 1=# 1 <# 1=# 1 #1 证毕 * 提取器与剩余哈希定义 - 提取器 8+8& 设是均匀分布的随机变量总体对变量其中从上随机选取且! 和 3 是分别从和上均匀选取的随机变量若 583! 称函数 8A 是提取器若提取器的种子 3 是可以公开的称该提取器为强提取器引理. 对任意若 8 是一个最坏条件下的 ='&1 的提取器则 8 也是平均条件下的? 强提取器定义. 泛函哈希 *,',/*1 一个哈希函数 4A3 对任意 5 满足 # < 5 3 称该函数是泛函哈希函数泛函哈希的构造设 4<<1 2 3<1 2 哈希函数定义为 < 则该函数对任意 2 和是一个泛函哈希函数易证明该构造满足泛函哈希的性质泛函哈希的构造设 6 是一个阶为 2 的乘法群 %%%6 函数族 6? 是一个泛函哈希族即 4 <1 2 <6? 3<6 %%%<% % 引理 / 剩余哈希引理 8&,/ )) 设是泛函哈希族! 是从上随机均匀选取的变量对任意及有 5! 槡 = 5! = 槡该引理表明任意泛函哈希函数可以构造平均条件下的提取器 8A 其中用于种子 '&1='&1? 推论 ) 基于的强提取器若 4A 3 是一个泛函哈希函数则该函数也是一个的提取器这里 <'&13?'&1? 剩余哈希引理表明任何近似泛函哈希族可以构造一个强提取器设是随机变量是大小为 * 输出长度 <='&1 对任意定义 8< 则 8 是一个种子长度是 * 输出长度是的强提取器该实例中种子用于选择哈希函数而提取器的输出是哈希函数输入定义 / 消息认证码一个消息认证码 " 由两个概率多荐式时间算法 "+% 组成算法 "+ 和消息作为输入输出一串 81 算法 % 消息和串 81 作为输入输出拒绝或接受一个消息认证码满足 < *+ 泄漏函数泄漏模型是以泄漏函数的方式体现在密码系统中不同应用场景要求有些函数在多项式时间是可计算的有些函数是在多项式时间内是不可计算的例如一个函数族 1 是单向的满足样本化从函数族中容易样本化一个函数可计算性给定容易计算单向性给定以不可忽略的优势在原像样本空间找出原像在计算上是不可行的无论何种泄漏模型我们要求敌手从已知的泄漏密钥中获得完整的密钥是不可行的敌手对秘密的泄漏获得是通过泄漏预言机得到为保证敌手不能获得整个秘密如解密密钥随机数中间结果等必须保证敌手只能从泄漏源获得这些秘密的部分信息本文中考虑密钥的泄漏泄漏模型对泄漏函数的输出不做限定只保证输出是有界的在保证同一密钥输出界的前提下敌手甚至可以通过多次采用不同的泄漏函数来获得同一密钥的输出

5 计算机学报年定义有界泄漏函数对任意函数其中 / 称该函数为有界泄漏函数也称缩界泄漏函数 + 弹性泄漏语义安全性定义 1 泄漏预言机泄漏预言机 7 和泄漏界 / 为输入其中 / 发起的最多 / 比特的信息超过 / 比特预言机返回为提供敌手自适应性的泄漏预言机询问允许敌手对同一密钥进行多次泄漏询问要求所获得的泄漏总量不超过系统设定的泄漏界 / 即可为实现同一密钥的多次泄漏询问可设计一个队列来记录所询问过的密钥及其泄漏总量我们给出公钥加密方案的安全性自适应选择密文不可区分性其安全性高于单向安全性在定义中的弹性泄漏安全性是在允许敌手进行密钥泄漏预言机询问 7 和密文解密预言机询问 7 5+ 条件下的密文不可区分性定义 ) 自适应选择密文不可区分性敌手获得接收者公钥 #@ 并具有密文解密询问的能力选择两消息且 8 <8 挑战者随机抛币并调用加密算法创建密文 $<+ #@ 8 敌手试图猜测密文 $ 中的消息 8 若敌手无法以不可忽略的概率优势猜出的取值我们称该方案是选择密文不可区分性定义 )) 自适应弹性泄漏安全性对任意多项式时间算法 )<) ) 一个公钥加密方案 <@+5+ 在泄漏函数族上算法在如下交互模型中获得的优势 )*" )/ 是可忽略的则该方案是弹性泄漏语义安全的该抗泄漏交互游戏模型如下挑战生成 #@@@ 并把 #@ 发送给 ) ) 选择泄漏函数 / 并发送给根据泄漏预言机 7 ) 选择密文 $ 并发送给挑战者 ( 根据解密预言机 7 5+ 应答对 $ 的自适应性解密钥询问 ) 自适应选择不同重复上面或不同密文 $ 重复 ( 这种重复次数可以是安全参数的多项式次数泄漏询问结束后 ) 选择并发送给两个挑战消息 8 8 随机抛币调用加密算法生成 $+ #@ 8 并将密文发送给 ) 算法基于已有的知识判定并输出 5 作为对随机抛币的猜测形式化弹性泄漏安全模型游戏定义如图 :)/ #@@@/ 88') #@-*8/8<8 $+#@8 -*8/ 5< ) 7 5+ $' )*" ) /< 9 #5< = 图弹性泄漏安全试验模型该安全模型中允许敌手可以执行适应性地进行泄漏预言机询问即它可以得到公钥后再自适应地选择泄漏函数同时允许敌手进行适应性地进行解密询问事实上敌手可以把公钥作为泄漏函数的硬核泄漏函数构造与公钥有关为避免在 ) 阶段敌手通过编码挑战密文从而形成特殊的泄漏函数从而区分密文中的消息明文我们不允许在 ) 阶段敌手进行泄漏预言机询问, 方案,*) 方案构造思路本方案中引入抗碰撞的哈希函数 $ 和一个消息认证码 " 来实现同时为达到抗泄漏性我们引入一强提取器 8$ 用于实现把部分密文组件映射到 1 2 上生成两个子密钥一个用于加密的会话密钥一个用于内部认证其中内部认证用于保证密文的不可延展性认证方式采用消息认证码 " 来实现 '&12 满足对任意 " 算法 + 的输出与一个 '&12 长泄漏界为整个密码系统生存周期允许泄漏的最大值

6 期张明武等高效弹性泄漏下安全公钥加密体制的随机串对系统安全参数来说在计算上是不可区分的即下面的概率优势是可忽略的 # +@5!"<= " # + < '&12 密钥衍射函数的输出分为两个子密钥和我们实例化以为认证密钥的消息认证码 "6 A 这里 '&12 生成基于任意满足条件的密钥算法在给定若干个关于消息及其认证码 81<" 询问输出的情况下生成一个新的有效认证码在计算上是不可行的即 #+581<" 5 81" 6 A 根据消息认证码安全标准 " 的输出 81 在 ;*8, 时是安全的即 < 它比一般的群元素长度要小对因素分解的有限域 ;*8, 标准安全时阶 '&12<( 椭圆曲线时 '&12< 在位安全下因式分解困难假设中 '&12<( 椭圆曲线中 '&12<(,* 具体方案设明文 8 的长度是 6 是满足判定性 5**. ') 假设 55 假设阶为 2 的群接下来给出安全的密钥弹性泄漏公钥加密方案构造方案中提取器的种子空间是随机选择 ##1 2 %%6 计算 <% % *<% # % # 选择抗碰撞哈希函数 $6 A91 2 '&12 及 '&12=/ 强提取器 8 '&12 A9 置公钥 #@<%%*$@5! ( ## 说明事实上整个系统所有用户可以共用群 62$@5! 和提取器 8 可以完全预先选定并公开对每个用户来说不同用户的公钥 %% * 是不同的默认用户的公钥只包括这个元素用户的密钥也只包括个 1 2 中的元素 + #@ 8 随机选取计算 <% <% 计算 <$ "< * 8 计算 81 " ( 输出密文 $< 81 $ ## 及 $< 81 计算 <$ 计算 "<?#?# ( 若 81 " 直接返回解密失败输出 8,*+ 性能分析 8 本节比较几种弹性泄漏的公钥加密方案所比较的方案皆基于 55 语言上的安全假设并可以此来构造哈希证明系统从而扩展并应用于其他的安全假设中如二次剩余双线性群假设等采用 55 假设的有限域实际中可以基于因式分解的困难假设构造也可以在椭圆曲线上的离散对数问题构造对于因式分解的假设中置 6 为 <2? 的阶是 2 的子群泄漏率定义为密钥允许的泄漏与整个密钥长度的比值即 < 显然 ## 的信息源有公钥 #@<%%*$@5! 挑战密文 $ < 81 解密询问的输出 ( 挑战明文 8 8 = 提取器 8 的输出上述信息中根据语义安全性的性质解密询问无法获得有关密钥的任何信息只能获得明文本文中消息与密钥和提取器种子是独立分布的和 $ 的性质定义无法从其输出中获得有关输入的有用信息设敌手获得密钥的泄漏长度是 /<@ 给定 <% % *<% # % 的情况下 " 的最小熵 "*@'&12=/ 根据密钥衍射函数的性质和仍具有 '&12=/ 无法获得密钥的信息即 ) <# < < / 2 同样消息认证码 81 也不泄漏密钥的信息消息相关加密 ",,15:98+:8*& 中加密的消息和密钥之间存在一定关系该方案中密文中除公钥相关信息对密钥存在泄漏熵之外加密消息本身也存在对密钥的泄漏本文不考虑此类情况

7 计算机学报年密钥中 # 和 # 是独立选取的 8 = /;*8'1 8 8 /.;*8' =/ <'&12=/ 式中 8 = 无关提取器 8 是 '&12= / 强提取器用以增强密钥的随机性在敌手获得公钥泄漏预言机询问解密预言机询问挑战密文及选择挑战明文的前提下最后系统中密钥仍具有不大于的 '&12=/ 信息熵为达到系统中密钥仍具有一定量有最小熵要求系统泄漏界 /'&12 即 /<'&12= 同时 # #1 因此方案所达到的最大泄漏率 </@<( 在. 标准安全下基于因式分解构造中 <2<( 对于椭圆曲线则要求 2< 对于安全性更高的. 安全标准因式分解构造中 <2<( 对于椭圆曲线则要求 2<( 对于方案中的消息认证码目前对位的认证码的输出是安全的它比一个群元素的长度要短且消息认证码 " 是对称密钥的计算效率比群指数运算要快同时计算量与哈希函数的运算量相当实际计算中可以忽略其复杂度基于 55 假设的方案构造中密文与密钥长度主要取决于群元素的个数而计算量主要取决于多指数 ) 单指数, 以及群元素判定 1)+ 等计算量在计算量方面 )<, 1)+<, 表列出和分析几种方案的密文与密钥长度泄漏率和安全级别的比较表列出方案的计算性能为能有数量上的比较把对多指数运算和群元素比较运算统一转换为单指数运算的运算量由于文献方案中用到了零知识证明其效率与一般群的指数运算完全不在一个数量级因此对其加密和解密计算量不作比较文献中设计两个方案分别达到安全和安全我们分别记为和 ; 表 ) 密文密钥泄漏率及安全性比较方案公钥长度密钥长度密文长度泄漏率安全级别 6?2 2?2 = # 2 2 2?8?9 ( 2 2 2?8?9 ( $? ( ; (2 2 2?8?81?9 3 ( ?9?8 本文方案 2 2 2?8?81?9 ( 注该方案用到可认证的加密 48/+ 可认证的加密密文长度 2<'&128 明文长度 81 认证标签长度 9 提取器种子长度表计算性能比较方案公钥长度密钥长度密文长度消息空间 6 =)<=, )?,<?, =)<=, 86 )<, <, )?1)+<, 2=/ )<, )?,<, )?1)+<, 2=/ 7 )<, )?,?@ )?1)+?@ 86 ; )<, )?,<, )?1)+<, 2=/ 3 )<, )?,<, )?1)+<, 86 本文方案 )<, )?,<, )?1)+<, 2=/ 注 ) 多指数运算, 单指数运算 1)+ 零知识证明计算量大 )<,1)+<, 在安全级别的方案中本文方案密钥只有个群元素比 ; 缩短了和方案中密钥长度相当但文献中需要零知识证明效根据 6,8* 的工作一个多指数的运算量是? '&1'&1 2 '&12 近似个单指数运算时间 6,8* 5 #*::1, :&8*8*& '1&*8/) /8:+:8&::,:*::1:9

8 期张明武等高效弹性泄漏下安全公钥加密体制率很低在泄漏率方面本文方案和安全的都达到 ( 比同安全级别的 ; 和文献提高了比文献中提高了在计算量方面由表可以看出本文的方案具有较好的计算效率 - 安全性本方案的安全性基于判定性 5**.') 假设即对任意多项时间的算法区分 $ < %%% % 与 $ <%%% % 是计算上不可行的 $ 称为有效的 5*.') 元组 $ 称为无效的 5**.') 元组根据第节的安全游戏抗泄漏安全性要求由随机抛币选择明文 8 产生的加密密文 $ 中无法猜出抛币密文结构中若 %% 是一个有效的 5**.') 元组即 <% <% 且 < 称密文 $ 称为有效密文 %'*9+*:/88 否则称为无效密文 '*9+*:/88 若密文解密中满足验证等式即 81" 则称该密文满足一致性 &,*,88+*:/88 否则是不一致的密文 +&,*,88+*:/88 显然使用一合法密钥解密密文时此密文对密钥来说应当是有效且满足一致性的安全性证明过程中我们采用一系列计算上不可区分游戏来证明第个游戏就是第节所定义的安全游戏设挑战密文是 $ < 81 显然在这个游戏中 < < 第个游戏中将和改变为非合法 5**.') 元组即根据 55 假设这种变化是计算上不可区分的显然是一个无效密文第个游戏中 <$ 仍是挑战密文中的元组计算而来此时 " 的计算也按照挑战密文中的和来计算显然此时生成的可以通过验证等是个一致性密文第个游戏中置 < $ 其中是安全假设实例中的元组显然 < 的概率是一个哈希函数可能碰撞的概率此时经过前面的变化询问的密文是无效密文第 ( 个游戏中挑战者拒绝所有无效密文的解密询问我们证明敌手根据公开信息和询问的泄漏密钥无法把一个无效密文转换为有效密文最后一个游戏中将密文中的明文组件用一个中的随机数代替显然此时密文是一个无效的不一致密文根据哈希证明系统的性质若一个有效密文与一个无效密文是不可区分的我们可以证明该方案是语义安全的接下来分析敌手允许从游戏中所能获得有关密钥的信息界从安全游戏中可知敌手获得有效密钥的信息来源主要有一是公钥 #@ 可能泄漏密钥熵三是挑战密文中隐藏关密钥的信息定理 ) 设是系统安全参数 $ 是密钥衍射函数 8 是 '&12= / 强提取器 9 是系统中敌手的解密询问的次数则方案是 /5 的安全的公钥加密方案其中 " 5?)*" 55 )?9)*" $ )?! )*" " )? / 29=?? /= 2 槡 2 #/<'&12=='&1 证明设是系列游戏对应的事件在中生成挑战密文 $ <+8 < 81 加密过程中所用的随机数和中间结果分别是 81 " 其中和对敌手来说在加密过程中是完全隐藏的对于敌手 ) 的泄漏询问或解密询问挑战者分别调用 7 5+ 和 7 进行应答事件表示敌手 ) 能成功猜出在中挑战者知道密钥直接用密钥生成挑战密文随机选取 1 2 计算 <% <% <$ " < <" 置密文 $< < < 81 在密文生成过程中只是把 " 的计算用密钥来计算因此本变化与是不可区分的且 %% 仍是有效 5**.') 元组即 # <# 在中 %% 用非法的 5**.') 元组代替随机选取 1 2 <% <% 而其他的密文元组保持不变事实上在中其他元组的计算与和无关根据 55 假设区分有效的和无效的 5**.') 元组在计算上是不可行的因此本游戏的变化对敌手来说是在计算上不可区分的其优势等价于解决 55 问题

9 ( 计算机学报年即 # =# )*" 55 ) 在中事件 1 是挑战者拒绝对所有密文但 $ <$ 的解密询问显然此游戏中满足拒绝的条件是哈希函数的碰撞概率容易得到 # 1 <# 1 设敌手最多进行 9 次解密询问根据引理 (# = # #1 9)*" $ ) 根据上面的变化挑战密文是无效密文无效 5**.') 元组在中挑战者拒绝敌手提供的所有无效密文的解密询问即公开的 %% 与密文中的不构成有效 5**.') 元组设 1 是挑战者由于无效密文而拒绝应答解密询问的事件则有 # 1 <# 1 # =# #1 由节抗泄漏性能的分析可知事件 1 发生的概率 $ 是一个无效密文设 <'&1% < '&1% 显然对 $$ 则有 $ '&1% & $ & $ '&1% * < A '&1% " %'&1% " ' % ' # & %# ' 上式中 988< = = = 意味着 " 与密文 $ 无关对于 9 无效密文被解密预言机接受的概率是 / 29= 因此有 # =# )? / 29= 接下来我们考虑 ( 该游戏中消息组件由一长的随机串代替经过的变换所有无效密文都被解密预言机拒绝解密预言机无法获得有关密钥的信息事实上在中当被替换后已证明该转换是不可区分的本游戏重点考虑密文中的 81 假定若 <81 <81 < 则 $ <$8 是一个强提取器种子是公开的证明中我们默认使用相同的种子对密钥信息获取有帮助的主要有公钥 #@ 挑战密文中的 81 显然若 " <" 则 < 若 $ 被解密预言机接受则有 81< " 若 < 则 81 <81 这样 $ <$ 我们考虑 $ $ 根据 " 的性质要求此时 $ 被解密预言机接受的概率是 )*" " ) 本游戏中为随机选取 < 若要求 8 是 '&12=/ 的强提取器则 8 与统计不可区分 8 #@@81 <'&12=/?'&1 根据剩余哈希引理有 5 2/ 2 / = < 槡槡 2 同时 # < < < 2 因此 # ( =#? /= 2 槡 2?)*"" ) 敌手猜测随机串和加密消息密文组件 8 8 的概率是 # ( <? 由于是在安全参数下多项式时间是可忽略的因此敌手攻击本方案的概率与一个随机抛币在计算上是不可区分的证毕. 方案应用本节给出本文方案在实际中的典型应用在物联网系统中为保证开放节点中的数据安全一般要引入加密体制来保证物联网节点存储数据的私密性与此对应的是实现加密系统的密钥也是一同保存在该节点中以供相应节点实现对数据的解密密钥对攻击者来说是黑盒显然攻击者对密钥系统的攻击期望更大于对加密系统算法本身的关注特别是物联网一般采用离散网络结构大部分节点架设于室外并通过无线通讯来实现数据的传输这极易让攻击者通过侧信道攻击的手段获得敏感机密信息包括密钥提供便利采用本文方案从算法上设计可证明安全的密码系统在给定攻击者一定量密钥的情形下灰盒密钥仍能保证系统仍具有黑盒密码系统的安全强度本文方案的另一个典型的应用场景是银行 $" 系统我们假定用户的银行卡号为公钥对应的交易取款密码为密钥事实上在取款或交易过程中交易密码可能被意者由视频监控 # 机监听甚至在输入密码的过程中观测按键的手势频率或速度等方式来获得部分的交易密码传统采用公钥加密方式来保护敏感信息的方案在交易密码被泄漏的情况下是不能证明为完全安全的虽然攻击者未得到全部的交易密码但通过字典攻击或穷举搜索可以极大概率实现猜测攻击采用本文的方案在即便的交易密码被窃取的情形下仍保证系统

10 期张明武等高效弹性泄漏下安全公钥加密体制 ( 是安全的在一定程度上实现了密钥增强能力 / 结束语本文提出一种有效安全的公钥加密方案在 ( 密钥被泄漏的情况下仍保证该方案是可证明安全的文中给出系统的安全模型实际构造以及安全性证明并给出详细的性能分析和比较结果显示本方案在安全级别的方案中具有较短密钥和较高计算效率接下来的工作是在保证系统计算效率的情形下设计容忍更高泄漏率的方案同时考虑到很多实际攻击方案如病毒可以控制伪随机发生器从而控制密码系统随机数的安全性构造抗伪随机数泄漏的方案也是接下来的研究内容参考文献 6*8, 5+/)&'9 5 * 1.8&'8 +&):488*&-*8/*:48*9:98::&+,,*1#&+9*1, *31/*7*$/*+*8,+4:4;'*+ +:8*&,+/)/*,&4'& &):48, */*, 康立王之怡高效的适应性选择密文安全公钥加密算法计算机学报 5&9*,7#*8.@1.,*'*8:,49&9&)4+8*&, 9,*9.+/'8+,&!*,8'8-&,#&+9*1,& 8/7#$86; *2&'9-,,%*488/%*)4'8&4, /9+& ;*8,9+:8&1:/ 1*,8 ))& 8+, #&+9*1,&8/ $!+*,+& ( ( 6,/*@'*7$@8.%*488/%+& )*18//&'*8/;4+8#4;'*++:8&1:/,*'*8 8&+&8*4'))&'1#&+9*1,&8/!,%1,(( /1 "*134716&$1*$",8'1.,*'*89+&8*4'1.,*'*84+8*&'+:8*& *94'*,:+,/*,&4'&&):48, ((*/*, 张明武杨波 $1*$ 抗主密钥泄漏和连续泄漏的双态仿射函数加密计算机学报 (( 5&9*,7');*@ B:.'8@3*+/,5*+*8 :4;'*++:8&1:/*8/ :,+ &'1 #&+9*1,&8/7#$*1:& '-5&9*,73*+/,5 1.,*'*8:4;'*+* 8/;&4998*')&9'#&+9*1,&8/7#$ 86;( 74@&1!7/1C28'84,*&,*'*8*98*8 ;,9,*184+4*89**8*&9+&,84+8*&&4' &,8),9&8-( 74*/1 C*124& *!218'#&;',+4*84,*&,*'*8:4;'*++:8*&,+/)*8/,899)&9'&4'&&8- */*, 于佳程相国李发根等标准模型下可证明安全的入侵容忍公钥加密方案软件学报 '-5&9*, 7& "#4;'*++:8*&*8/ ;&4998*')&9'#&+9*1,&8/7#$ **!+/ 665&9*,7@-+.8' 8&/,/')) *,*89#&+9*1,&8/7#$86; /&-5&9*,5&4,'*,738,6#+8*+''1.,*'*8*98*8;,9+:8*&&),*):',,4):8*&, #&+9*1,&8/"- 7& ( &"12#4;'*++:8&,,8),,*'*88& '1#&+9*1,&8/7#$86; ( 1,*'*8'2)'+:8*& #&+9*1,&8/7#$*1:&(( 8*5&9*, 7'*8':&,4.,*'*8 4+8*&9'&&8/*18,&),#&+9*1,&8/ 7#$641,6'1*4)( )/&4:%*,'/,/:&&,9:9*1) &9:8*+/&,+*:/88,+4:4;'*++:8*& #&+9*1,&8/7#$),89)8/'9, ( '* * 88/.+8 '1 * :4;'*+ +:8*&#&+9*1,&8/$#&*9+ &"741"#4;'*++:8&,,8),:&;',+4 1*,8+/&,+*:/888+,#&+9*1,&8/$ - 7& */1!4C/ *+*8'1.,*'*8 :4;'*+ +:8*& &) 55,,4):8*& '4,8 &):48*1 *431/& 7*+*8:4;'*++:8&,,8),*'*88&'1+/&,+*:/888+,#&+9*1, &8/$!+*,+& ,*'*8 :4;'*++:8*&&) -*,*9:98/,/ 4+8*&,#&+9*1,&8/$51%*8) -& 6&4,'*, 738, 6+/**1'1,*'*+8/&41/ 94',,8) +:8*&#&+9*1, & 8/$#&*9+

11 ( 计算机学报年 /1 "71 6$1* $6&499'1.,*'*8 4+8*&'+:8*& -*8/ /*99 +8& :9*+8 $/ &):48&4'( ( * 6 *4 1.,*'*8+/&,+*:/88,+4 :4;'*++:8*&&) /,/:&&,,8) 9&.8*) '&,,*'8#&+9*1,&8/7#$61'44 9* 8/ #2&' %#9 8+8*:&&,49 +&8*4'))&'1#&+9*1,&8/7#$ $-'1.,*'*8,+4:4;'*++:8*&&4'& "8/)8*+' :8&'&1 5&9*,%,8&,.* )*8/!4..8+8&, &-8&18,8&1,&);*&)8*+,9&8/&*, 98"&4'&&):48, 6&/5'*);41 ",8&, *+4',+4+:8*&&)9+*,*&5**.')#&+9*1, &8/ 7#$ ((8 6; ( 2&;& * #/5:&,,&*,,+/*8,8, *+'49 ::'*9 +:8&1:/,+4*8 9:*+:,8*&98/:&8&+&' &8-&,+4*8 2;&*"+9*98*, )*,+/&+4,,&*&)8*&,+4*898-&,+4*8 3(;&*#/5,,&+*8:&,,& *,)*,+/*8,8,*+'49*&)8*&98-&,+4*8 43(;&*#/5:&,,&*,,+/ *8,8,*+'49+:8&1:/9*&)8*&,+4*8 3'(&$ +4*8:*)*8*,&)&9+:8&1:/8+/&'&1 /, )&9'98+,,/*1&' ;'+;&++,,8& 8/:*)*8*,9,48/8,+8, )4,8;,',8&99*8',88,&8'98&8/8+, &-8/,,+4*8 )&9',*'8&+:84 )',+*&,*-/*+/8/8+,+1*89*8*&'*&) 8*&;&48,+8,88,8/&41/,*9.+/'&98& 1*,88/*,8:&8+,8/8-&+&):')8 ::&+/,8&*):&8/,+4*8+&,84+8*&::&+/ *,8&9*)**,/8/9)1&8/*,,:+**+8+,;9,*1*1 *&+9/9-/9-.;,9''98/&8/ ::&+/*,8& )&9*8/89*8*&';'+<;& )&9'9 +&,84+88/,+/)8&1*,88/8+ '1&*8/);,9 '' 8/*,::-99,,8/:&;') &,+4 '1.,*'*8:4;'*++:8*&*8/'1&*8/);,9 ''9 1*8/,+4*8 )&9'9 +&,84+8*& 3 *8&94+9*8*&4+8*&9),,148/8*+ 8*&+&98& /+8/ *+*+ 9 ):'&,8&1 9&),,8+8&8&8&'88/'198/84 &8+8&8/,*.&,+8*,94+998/'1 8*, /+9 &):9 -*8/ '89,+/),&4,+/)D&,,/&8,+8,*.9/*1/'8* '18&+8'8/+&):488*&+&,8,& 18*&+:8*&99+:8*&4*'88& 9,*1':&8,&8/**81&4:,:+8*' $/*,,849*,:8*',4::&89;8/8*&'84' +*+!&498*&&/*4928&,9 98/@#&1)&84'+*+!&498*& &4;*#&* &!98/ :!49#&1)&88@ ;&8&&&)8*& +4*8&/*4918,9

期王志伟等抗辅助输入安全的 # 构造露密码学 /3**.5&/,5 被提出以应对密钥的泄露问题即如何在密钥泄露的情况下保证密码方案的安全性弹性泄露密码学已成为密码学的研究热点目前已提出的一些主要泄露模型如下仅计算泄露.5&)1&.3.6& )*&. 假设设备在进行密码运算时内

期王志伟等抗辅助输入安全的 # 构造露密码学 /3**.5&/,5 被提出以应对密钥的泄露问题即如何在密钥泄露的情况下保证密码方案的安全性弹性泄露密码学已成为密码学的研究热点目前已提出的一些主要泄露模型如下仅计算泄露.5&)1*&.3*.6& )*&. 假设设备在进行密码运算时内第卷第期年月计算机学报!"#$ %& & " 抗辅助输入安全的构造王志伟李道丰张伟陈南京邮电大学计算机学院南京广西大学计算机与电子信息学院南宁伟摘要辅助输入模型是弹性泄露密码学中一个重要的泄露模型它定义了一族不可逆的函数去模拟一类密钥泄露的情况目前已有的抗辅助输入公钥加密方案 # 身份基加密方案 2 都是选择明文攻击安全 #31 的文中提出了一个抗辅助输入选择密文攻击安全

期 张明武等 高效弹性泄漏下 安全公钥加密体制 *,/+9$/+&):488*&+&,8,&18*&+:8*&99+:8*&4*'8 8&8/8& 9,*1' :&8&:8*&, &8/**8 1&4:,:+8*' &):9-*8/'89,+/),'18,*.9+&):488*&+&,8*):&9

期张明武等高效弹性泄漏下安全公钥加密体制 ,/+9$/+&):488&+&,8,&18&+:8&99+:8&4'8 8&8/8& 9,1' :&8&:8&, &8/**8 1&4:,:+8' &):9-8/'89,+/),'18,.9+&):488&+&,8*):&9