2022年标准模型下KDM安全的对称加密方案 .pdf

《2022年标准模型下KDM安全的对称加密方案 .pdf》由会员分享，可在线阅读，更多相关《2022年标准模型下KDM安全的对称加密方案 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 33 卷第 6 期电子与信息学报Vol.33No.6 2011 年 6 月Journal of Electronics & Information Technology Jun. 2011 标准模型下 KDM 安全的对称加密方案来齐齐*陈原裴庆祺谢敏张安源(西安电子科技大学计算机网络与信息安全教育部重点实验室西安 710071) (西安电子科技大学ISN 综合业务网国家重点实验室西安 710071) 摘要： KDM(Key-Dependent Message)安全是考虑当加密的明文消息是所用加密方案私钥的函数时的安全问题。该文利用通用哈希函数(universal hash function

2、)，在标准模型下基于一种变形的剩余哈希引理(left-over hash lemma) 构造出一个信息论KDM安全的无状态对称加密方案。该方案能够抵抗任意攻击者接近指数次边界的KDM加密询问攻击， 并且攻击者询问的挑战函数可以是任意集合。最后通过合理选择参数，对比已有方案，证明该文所构造方案的安全性有所提高。关键词： 依赖于密钥的明文(KDM) ；对称加密；通用哈希函数；剩余哈希引理；标准模型中图分类号： TP309 文献标识码：A 文章编号： 1009-5896(2011)06-1277-05 DOI : 10.3724/SP.J.1146.2010.00899 A KDM-secure S

3、ymmetric Encryption Scheme in the Standard Model Lai Qi-qiChen YuanPei Qing-qiXie Min Zhang An-yuan(Key Laboratory of Computer Network and Information Security of Education, Xidian University, Xi an 710071, China ) (National Key Lab of Integrated Service Network, Xidian University, Xi an 710071, Chi

4、na ) Abstract : Key-Dependent Message (KDM) security was introduced to address the case where message is a function of secret key of encryption scheme. By using universal hash function, this paper presents a stateless symmetric encryption scheme that is information-theoretically KDM secure based on

5、an extended version of left-over hash lemma in the standard model. The scheme is secure in face of a bounded of nearly exponent number of encryptions for which the messages depend in an arbitrary way on the secret key. Finally, through choosing parameters properly and comparing with existing schemes

6、, the security and efficiency of the constructed scheme are proved to be improved. Key words : Key-Dependent Message (KDM); Symmetric encryption; Universal hash function; Left-over hash lemma; Standard model 1引言传统安全性定义没有考虑私钥或者私钥函数(依赖于密钥的明文，KDM) 被加密的情况。加密的标准定义建立在明文和私钥相互独立的假设之上，例如密文不可区分性和密文不可扩展性。但在某些实

7、际应用中，加密的明文数据会直接或者间接依赖于私钥。例如，硬盘加密将密钥放在硬盘上和其它数据同时加密。利用KDM安全的密码方案可以构造满足特殊要求的安全 系统。例如，循环安全(circular security)是 KDM安全的一种特殊情况。文献 1利用循环安全构造出一个匿名信用卡加密方2010-08-24 收到， 2011-03-18 改回国家自然科学基金(60970120, 60803150, 60903200)和中央高校基本科研业务费专项资金(JY10000901021)资助课题* 通信作者：来齐齐 案。该方案鼓励用户不必删除自身的密钥信息。同时， KDM安全问题是计算安全和理论安全相互统

8、一的关键。加密方案的KDM 安全定义最早由Black 等人2在 2002 年提出。该定义建立了明文和私钥之间的联系。在他们提出的对称加密KDM安全模型中，攻击者通过询问Oracle ，可以得到ik对1(,)ng kk的加密，其中 1in , 1,nkk是安全定义模型中需要用到的n个密钥，g是任意多项式时间内能够计算的函数， 也称之为挑战函数。1(,)ng kk是把n个密钥作为输入时，挑战函数的输出结果。当攻击者不能够正确区分Oracle 返回值和相同长度0 bit串的密文时，就称方案是KDM安全的。目前，关于KDM安全问题的研究已有诸多进展。自文献 2首次提出KDM安全的形式化定义。在随机预言

9、机模型下，他们构造出第1 个 KDM安名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 1278 电 子 与 信 息 学 报第 33 卷全的对称加密方案。文献3，文献 4，文献 5,6和文献 7分别从不同的角度对KDM安全问题进行了研究。在 2008 年，Boneh 等人8取得突破性的进展。他们在标准模型下，基于DDH假设构造出第1 个能够抵抗挑战函数是仿射函数的KDM加密询问攻击的公钥加密方案。最近，Brakerski 等人9把

10、 KDM安全问题、密钥泄露和辅助输入联系到一起，构造出一个能够抵抗以上攻击的公钥加密方案。在2008年， Hofheinz 等人10构造出较弱的KDM安全的对称加密方案。他们提出一个基于剩余哈希引理的信息论安全的无状态对称加密方案，该方案能抵抗多项式次的任意KDM询问攻击；同时也构造出一个仅依赖当前状态的KDM安全的状态对称加密方案。该方案是计算安全的，并且能抵抗任意次的KDM加密询问攻击。 由剩余哈希引理得知，若x具有足够多的不确定性， 即统计熵，则两个分布( , ( )h h x和 (0,1 )lH 是统计不可区分的。 在攻击者多次加密询问过程中，x 的不确定性不断减少，导致第 1 个方案

11、只能抵抗多项式次KDM加密询问攻击。第 2 个方案通过引入状态变量将攻击次数提高到任意多次。但缺点是该方案的证明在仅依赖于当前状态的假设下成立，并且方案是计算安全，只能抵抗多项式时间攻击者的攻击。为了更好地实现KDM安全性，本文构造出一个能够抵抗接近指数次任意KDM加密询问攻击的信息论安全的无状态对称加密方案。通过引入随机参数使得每次加密时通用哈希函数的输入不断变化，同时该输入具有足够多的统计熵，保证剩余哈希引理成立。最后，计算通用哈希函数的输出分布与均匀分布之间的统计距离，证明所提方案能满足上述要求。 该文方案相对于文献10给出的第 1 个方案，在保证信息论KDM安全的同时，提高了允许加密询

12、问的次数，从而增强了方案的安全性；相对于文献 10给出的第 2 个方案，本文方案是无状态信息论安全的，证明过程不用建立在仅依赖于当前状态的假设之上，因此安全性证明更加合理并且实现了更高的安全性目标。2预备知识和基本概念2.1 基本概念和符号本文中，对于任意nN, 1,nxx表示 n 个变量，简记为1,nx; kN表示安全参数； 有限集 X ，用$xX ?表示从 X 中均匀选取x 。设概率算法A ，用( )yA x表示把 x 和均匀的随机性作为算法A 的输入，该算法运行完后将输出结果赋给y。如果概率算法A 能在 k 的多项式时间内完成，就称A是一个概率多项式时间(PPT) 算法。设函数( )f

13、x，若对于cN?, 0kN?使得0kk时，有 | ( ) |f kck-，那么由这样的函数组成的集合F称为哈希函数族。若 |FD=，记为(;,)FD N M=定 义212通 用 哈 希 函 数 族 (Universal Hash Family, UHF) 对 于 任 意,x yXxy， 且$hH ?。如果( )( )h xh y=的概率是 1/ M ，称哈希函数的集合H是 UHF 。如果( )( )h xh y=的概率至多 是 1/1/MM+， 则 称H是 近 似 通 用 (almost universal) 的。通用哈希函数是一种输出比较均匀的函数。只要输入具有足够多的不确定性，通用哈希函数

14、的输出分布与相同长度的均匀分布是统计不可区分的。拟随机性与随机变量分布之间的统计距离有密切关系。借助拟随机性可以描述分布之间的统计距离。下面给出拟随机性的定义。定义 310(拟随机性 ) 设 ( , )Y p 是一个有限概率空间，令0,YY?Y作为一个集合，用|Y表示Y中的 元 素 个 数 ，R且0 。 如 果00|()|pYY-/ |Y成立，称概率分布p在集合0Y 上是-拟随 机 的 。 如 果 对 于 所 有 的0,YY?00|()|pYY-/ |Y成立，称概率分布p 是-拟随机的。引理111,13设Yu是集合Y上的均匀概率分布，集合Y上的任意概率分布p 是-拟随机的，当且仅当( ;)Yp

15、 u。引 理 .212 剩 余 哈 希 引 理 (left-over hash lemma) ：设0,1 ,nX?|2lX，存在0e，使得H 是从 n bit 特到2le-bit 的近似通用哈希函数。 令$,hH ?$xX ?， 则 分 布( , ( )h h x在 集 合20,1leH-上是1/2-e拟随机的，即2( , ( );0,1)1/2leeh h xH-(统计不可区分 ) 引理 2 是该文方案构造和证明的一个重要的基础。定义 4(标准模型下对称加密的KDM安全定义) 设对称加密方案(, ,), =EKD1:(,K=K)nK是密钥向量，n 是一个可以用安全参数k的多项式表示的量，A

16、是攻击者。 Real 是一个 Oracle ，在输入 g ,时，返回 C(1 , ();kKgKEFake 是一名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 第 6 期来齐齐等： 标准模型下 KDM 安全的对称加密方案 1279个 Oracle ，在输入 g , 时，返回(1 ,)kCKU E。攻击者 A 的 KDM 攻击成功的优势是()()KDMRealFakeAdv( ) : | Pr1Pr1|AAA=-=若任意PPT攻击

17、者A 和任意 n ，优势函数KDMAdv()A相对于安全参数是可忽略的，则称对称加密方案是 KDM 安全的。攻击者A只能用输出长度相同的挑战函数g 进行加密询问，即对于所有的K, ()gK的长度|() |gK是定值。已知概率分布的碰撞概率可以求出拟随机性。碰撞概率的定义如下。定义 511(碰撞概率 ) 令(, )Y p 是概率空间，将概率分布p的碰撞概率的定义记为2( ( )ypp y=概率分布的拟随机性和碰撞概率之间的关系由下面引理给出。引理 312令(, )Yp是概率空间，则概率分布p是|1 /2-pY-拟随机的。3 一个 KDM 安全的对称加密方案及证明3.1 方案构造在本文构造的方案中

18、，密钥可以分为两部分。该方案可以抵抗针对于这两部分密钥的接近指数次KDM加密询问攻击。系统建立：令H, H 是两个通用哈希函数族，H将( )l k长的比特串映射成为k长的比特串，H将( )m k长的比特串映射成为( )l k长的比特串。定义无状 态 的 对称 加 密 方 案(, ,) =K E D， 安 全 参 数kN， 明 文 空 间 0,1k， 密 钥 空 间( )0,1l k、( )0,1m k，其中( )( )l km k。密钥生成：(1 )kK:$( )0,1l kK ?, $K ?( )0,1m k；加密：(1 ,)kK KME:$hH ?,$hH ?, ()hKR =，输出密文(

19、 , ()Ch hh RK=)M；解密：(1 ,( ,)kKKh h DD:()Rh K =, M =()h RKD。3.2 方案的安全证明解密的正确性显然成立。为完成方案的安全性证明，先给出以下两个引理。引理4对于任意未知的R, K选自于概率空间(,)lY U，则CRK=同样未知并且服从分布(,)lY U，即C和K有相同的信息量。证 明由 于(,)lKY U， 则Pr1/Ky=|Y，其中 yY。PrPrPr=1/CyKRyKyR=|Y，因此RK在Y上的取值是均匀的，与均匀选取的K有同样的信息量。证毕引理 5(扩展的 Left-over hash lemma)：设通用 哈 希函 数 族H和H

20、, : 0,10,1 ,mlH:H0,1l0,1 ,k,mllk。选取h,hx,r， 如下：$,hH ?$,hH ?$0,1,mx ?$r ?0,1l，计算( )h rR=，则( , (); ,)h h h RKh h U( )/22l kk-，即( , ()( ,h h h hKKh h )U。证明该引理的证明可以分为两部分：先求出碰撞概率，再求拟随机性。( , ()h h h RK在 (,H H )U上的碰撞概率是1h, 2hH, KX, KY, 1h, 2hH分别随机 选 取 时 ，12hh=, 12hh=, (111()hKR =, 222()h KR =), 122()()h Rxh

21、 Rx=同时成立的概率，即11112222121211221122112211221122Pr(, ()(, ()PrPrPr()()1/ |1/ | (PrPrPr()() |)1/ |1/ | (1h hh Rxhhh Rxhhhhh Rxh RxHHRxRxRxRxh Rxh RxRxRxHH=?=+=()/ |1/ |11/ |1/ |1/ |)1/ |1/ | (1/ |1/ |1/ |1/ |)XYYYYYYZHHXYYYYYZ+-+利用引理3 得()1/2( , ();,)( | / | + | / | + | /| )/2/23 |2 | |h hh RKh h UZXYZYY

22、ZYYZYYZY YZY YZYZY=+=所以( , ()( ,)h hh h KKh h U 成立。证毕定理1该文所提方案是近似于指数边界的KDM安全的对称加密方案。证明令0,1mX ?, 0,1lY =, 0,1kZ =, ( )mm k=, ( )。ll k=由引理4 得知RK有足够的信息量，能作为通用哈希函数$hH ?的输入。K是通信双方初始共享的密钥，具有足够多的统计熵作为哈希函数h的输入， 即(,()(,)hhKh U 成立。在加密方案中，R是一个与真随机统计不可区分的量，因此明文同样可以是密钥K 的函数。 下面详细计算该方案能够抵抗KDM询问攻击的次数。令1,1,1,1,1,1,

23、(,;,)iiiiiiihhchhU=，用i表示全部i次询问得到的正确回答与全部是随机消名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 1280 电 子 与 信 息 学 报第 33 卷息加密之间的统计距离。相类似可以定义：11,11,11,11,11,11,1(,;,)iiiiiiihhchhU-=由 参 数 选 择 ，(,)iiih h U是 独 立 于1,1(,ih-1,11,11,1,)iiihcU-的 。 所 以 得11

24、,(,iih-=1,1,11,1,1,1,;,)iiiiiiihUchhUU-。 由参考文献 10的引理1，可以求1,1,1,11,1,(,;,iiiiiihhUchh-1,1,)iic c-。与文献10 相类似，在此同样取( )l k(2 ( )3)p kk=+，由引理5 可以求得( )( )1,1,1,11,1,1,11,1,1,11,1,1,1/21/21/221,1,1,1,(,;,)(,;,(),)2322(,;iiiiiiiiiiiiiiiiiiikkl kikkl kkiiiihhUchhc chhUmchhh h KKchhch-+-+-=,1,1,1,1,1,11,1,1,1

25、,1,1,11,1,1,121,)(,;,)(,;,)2iiiiiiiiiiiiiiiiiikihUhhcUhhUhhUchhc c-+由定义00 =，所以2( )( )2kp kp k-。即使( )p k是一个非常接近指数2k的多项式，( )p k仍然是可忽略的。证毕4方案的性能分析和参数选择由上面分析得知，本文所提方案可以抵抗接近指数次的 KDM加密询问攻击， 相对于文献 10只能抵抗多项式次加密询问攻击的方案，本文方案的安全性有较大提高。同时， 本文方案是信息论安全的，并且安全证明无需依赖于当前状态的假设。因此与文献 10的第 2 个方案相比， 虽然该本文方案允许询问次数有所降低，但安全

26、性证明更加合理并且实现了更强的安全性目标。3 个方案的详细对比在表1中给出。为更加清晰地表示出在允许加密询问的次数方面，本方案相对于文献10所构造方案1 的提高， 我们用图 1 表示。图 1 中用横轴表示安全参数，纵轴表示允许加密询问的次数。 在文献 10的方案 1 中，具体多项式表 1 本文构造的方案与文献10的方案1、方案2 的具体比较主要方法允许加密询问次数达到的安全性文献 10 的方案 1 利用 UHF 多项式次信息论安全文献 10 的方案 2 引入状态加密任意次计算安全本文所构造方案增加 UHF 输入的随机性接近指数次信息论安全图 1 本文构造的方案与文献10中方案1 的询问次数随安

27、全参数变化示意图次允许加密询问的次数要根据具体情况而定，我们在此分别以2( )h kk=和3( )g kk=为例表示该方案在不同的多项式选择下，所允许加密询问的次数。而用( )2kp k 表示本文构造方案所允许加密询问的次数。由此可见，本文方案允许加密询问次数显著提高。下面对参数的选取范围进行讨论。与单独增加密钥长度相比，本文方案能够明显减小输出密文分布和相同长度均匀分布之前的统计距离。由定理1的证明过程得知，允许询问的次数( )p k是由( )p k可忽略决定的，与剩余哈希引理和扩展的剩余哈希引理给出的两个分布之间的统计距离有关。显然，该统计距离越小，可进行询问的次数就越大。为此，作为询问次

28、数提高的一个充分条件，需要计算参数的选取范围，使得扩展的剩余哈希引理给出的两个分布之间的统计距离比剩余哈希引理的要小。单纯增 加 密 钥 长 度 为( )m k时 ，( , ();,)h h Kh U| / | 2ZX。按照本文提出的方案，( ,h h();,)h RKh h U满足：( , (); ,)| / | / | / |/2h h h RKh h UZXYZYYZYY+若| / |/2| / | / | / |/2ZXZXYZYYZYY+则222222221/ |1/ |1/ |1/(2 |)1/22|22 | (2|) |2|22 (|1)|(2 ( |1)/(2|)2| /22

29、|2 |lllllllllllllllXXYYYXXYYXYYXYYYYXY+?+?+-=-?-+=?因为 |2lY =，所以2|2lX 。由此，我们可以令20,1lX ?。按照以上分析，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 第 6 期来齐齐等： 标准模型下 KDM 安全的对称加密方案 1281大致确定了参数X的选取范围。而参数Y和Z的具体选择已在方案证明过程中说明。5 结束语本文利用通用哈希函数和变型的剩余哈希引理，

30、构造了一个KDM安全的对称加密方案。该方案增加了通用哈希函数输入的随机性，使得输出密文分布和均匀分布之间的统计距离变小，从而提高了允许加密询问的次数，因此本文方案的安全性得到增强。经分析得知本方案是信息论安全的，所以在进行 KDM加密询问时，挑战函数可以取自任意函数的集合。本文方案中待加密的明文长度和密钥长度存在依赖关系，且明文长度小于密钥长度，使得方案未能实现标准的KDM安全定义。在对密钥的相关信息进行加密时，该方案可以提供部分KDM安全。如何设计能够实现标准KDM安全的对称加密方案，值得进一步研究。我们初步的设想是通过将理想加密模型和通用哈希函数相结合，来达到减少密钥长度的目的，从而实现标

31、准的KDM安全性。此外如何构造主动攻击模型下的KDM安全加密方案，也是一个有意义的研究问题。参 考 文 献1Camenisch J and Lysyanskaya A. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In EUROCRYPT 01, 2001, Vol. 2045: 93- 118. 2Black J, Rogaway P, and Shrimption T. Encryption-scheme security in the

32、presence of key-dependent message. In SAC 2002, 2002, Vol. 2595: 62- 75. 3Adao P, Bana G, Herzog J, and Scedro A. Soundness of formal encryption in the presence of key-cycle. In ESORICS 2005, 2005, LNCS 3679: 374- 396. 4Halevi S and Krawczyk H. Security under key-dependent inputs. In ACM CCS 07, 200

33、7: 466- 475. 5Back M, Durmuth M, and Unruh D. OAEP is secure under key-dependent messages. In ASIACRYPTO2008, Josef Pieprzyk, 2008, Vol. 5350: 506- 523. 6Backes M, Pfitzmann B, and Scedrov A. Key-dependent messages security under active attacksBRSIM/UC- soundness of symbolic encryption with key cycl

34、es. In 20th IEEE Computer Security Foundations Symposium, Proceedings of CSF 2007, Venice, Italy, 2007: 112- 124. 7Haitner I and Holenstein T. On the (im)possibility of key-dependent encryption. In TCC 09, 2009, Vol. 5444: 202- 219. 8Boneh D, Halevi S, Hamburg M, and Ostrovsky R. Circular- secure en

35、cryption from decision Diffie-Hellamn. In CRYPTO 08, California, USA, 2008: 108- 125. 9Brakerski Z and Goldwasser S. Circular and leakage resilient public-key encryption under subgroup indistinguishability. In CRYPT 10, California, USA, 2010: 1- 20. 10Hofheinz D and Unruh D. Towards key-dependent me

36、ssage security in the standard model. In EUROCRYPT 08, 2008, Vol. 4965: 108- 126. 11Stinson D R. Universal hash families and the leftover hash lemma, and applications to cryptography and computing. Journal of Combinatorial Mathematics and Combinatorial Computing, 2002, (42): 3- 31. 12Impagliazzo R a

37、nd Zuckerman D. How to recycle random bits. In 30th IEEE Symposium on Foundations of computer science, Research Triangle Park, 1989: 248- 253. 13Impagliazzo R, Levin L, and Luby M. Pseudo-random generation from one-way functions. In 21st ACM Symposium on Theory of computing, Washigton, USA, 1989: 12- 24. 来齐齐：男， 1986 年生，硕博连读生，研究方向为数据加密的KDM安全方案设计、公钥加密的可证明安全方法研究. 陈原：女，1978 年生，博士，讲师，研究方向为公钥加密与单双钥混合加密的可证明安全性. 裴庆褀：男，1975 年生，博士，副教授，计算机网络与信息安全教育部重点实验室副主任，研究方向为密码学、安全协议设计与分析. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -