（计算机应用技术专业论文）关于公钥加密方案匿名性质的研究.pdf

大连理工大学硕士学位论文 摘要 公钥加密方案的匿名性( 亦称公钥隐密性) 与数据保密性同样都具有重要应用价值。 匿名性( k e y - p r i v a c y ) 与保密性( d a t a - p r i v a c y ) 是完全不同的性质：前者保证密文不泄露用来 加密的公钥，后者则保证密文不泄露其明文。 文中首先建立关于公钥加密方案的两个通用的新概念，即相对匿名性和相对保密 性。通过这些较弱的安全性概念，建立了公钥加密方案的保密性与匿名性之间两个对偶 式的普遍关系，即相对匿名性( 相对保密性) 连同保密性( 匿名性) 蕴涵匿名性( 保密性) 。对 某些特殊方案，相对匿名和相对保密性概念可以用来大大简化保密性或匿名性的证明。 最近c a n e t t i h a l e v i k a t z 给出了基于i b e 构造普通公钥加密方案的一个优美的一般 性方法，继而b o n c h k a t z 给出一个不同的构造，对前者进行了性能改进。 c a n e t t i h a l e v i k a t z 还第一次非常一般性地构造了一类前向保密的时变公钥加密方案。 本文研究了这三类一般性构造的匿名性质。建立了关于i b e 方案的两个通用的新概念， 即全局公钥匿名和全局公钥相对匿名性质，通过这两个较弱的安全性概念，证明了关于 c a n e t t i h a l e v i k a t z 方案和b o n e h - k a t z 方案的选择密文匿名的两类充分条件。为便于理 解和应用，文中还对一些具体实例检验了这些匿名条件。论文还建立了所谓2 叉树加密 方案的全局匿名性以及时变公钥加密方案的前向匿名性这两个通用的新概念，并基于此 证明了时变公钥加密方案的c a n e t t i h a l e v i k a t z 构造的前向匿名条件。 最后，给出两个典型的混合加密构造，即f u j i s a k i o k a m o t o 构造和 o k a m o t o p o i n t c h e v a l 构造( r e a c t ) 选择密文匿名的充分条件，这些条件仅包括特定意义 上的相对匿名性质和其它一些自然的弱保密性要求。文中不仅用多个具体实例表明这些 条件都是非常实用的判定准则，而且还进一步应用这些普遍结果，给出对某些具体公钥 加密方案匿名性质的简化证明，并证明了著名的n e s s i e 方案p s e c 1 2 3 的选择密文匿 名性质。 关键词：计算密码学；匿名性；可证明的安全性；公钥隐秘性 关于公钥加密方案匿名性质的研究 r e s e a r c ho na n o n y m i t yi np u b l i c k e ye n c r y p t i o nc o n s t r u c t i o n s a b s t r a c t i na p p l i c a t i o n so fp u b l i c - k e ye n c r y p t i o ns c h e m e s ，a n o n y m i t y ( 1 【e y p r i v a c y ) 弱w e l l 弱 s e c u r i t y ( d a t a - p r i v a c y ) i su s e f u la n dw i d e l yd e s i r e d a n o n y m i t yi sc o m p l e t e l yd i f f e r e n tf r o m s e c u r i t y n l ef o r m e rm a k e ss t i l et h ec i p h e r - t e x tw i l ln o tl e a kt h ee n c r y p t i o nk e yw h i l et h e l a t t e ra s k st h es e c u r i t yo fp l a i n t e x t i nt h i sp a p e rt w on e wa n dg e n e r a lc o n c e p t s ，n a m e d r e l e v a n ta n o n y m i t y a n d r e l e v a n t s e c u r i t y ”，w e r ei n c l u d e d ，b a s e d - u p o nw h i c h ，t w og e n e r a lc o n j u g a t er e l a t i o n sw e r ep r o v e d b e t w e e na n o n y m i t ya n dd a t a - p r i v a c y ，i e ，r e l e v a n ta n o n y m i t y ( r e l e v a n td a t a - p r i v a c y ) t o g e t h e r w i t l ld a t a - p r i v a c y ( a n o n y m i t y ) i m p l i e da n o n y m i t y ( d a t a - p r i v a c y ) i ns o m es c h e m e s ，r e l e v a n t a n o n y m i t ya n dr e l e v a n td a t a - p r i v a c yw o u l ds i m p l i f yt h e i rp r o v e no fs e c u r i t ya n da n o n y m i t y r e c e n t l yc a n e t t i h a l e v i - k a t zp r o p o s e dag e n e r i ca n de l e g a n ti b e - b a s e dc o n s t r u c t i o nf o r ( t r a d i t i o n a l ) p u b l i c - k e ye n c r y p t i o n , t h ep e r f o r m a n c eo fw h i c hw a si m p r o v e db ya n o t h e r c o n s t r u c t i o np r o p o s e d b y b o n e h k a t z c a n e t t i h a l e v i - k a t za l s op r o p o s e dag e n e r i c f o r w a r d s e c u r ep u b l i c k e ye n c r y p t i o ns c h e m e t l l i sp a p e ra n a l y z e ds u c ht h r e ec o n s t r u c t i o n s a n o n y m i t y f i r s t l y ，t w on e wa n dg e n e r i cc o n c e p t si ni b es c h e m e ， m a s t e r - k e ya n o n y m i t y a n d r e l e v a n tm a s t e r - k e ya n o n y m i t y w e r ep r o p o s e da n dt w od i f f e r e n ts u f f i c i e n tc o n d i t i o n s f o rc h o s e n c i p h e r t e x ta n o n y m i t yw e r ep r o v e df o rc a n e t t i - - h a l e v i - k a t za n db e n c h - k a t z c o n s t r u c t i o n s e c o n d l y ，n e wc o n c e p t so f m a s t e r - k e ya n o n y m i t y f o rt h es o - c a l l e db i n a r y - t r e e e n c r y p t i o ns c h e m ea n d “f o r w a r da n o n y m i t y f o rt i m e - s h i f tp u b l i c - k e ye n c r y p t i o nw e r e p r o p o s e d 耶1 e f o r m e rw a sp r o v e dt ob eas u f f i c i e n tc o n d i t i o nf o rt h e g e n e t i c c a n e t t i - h a l e v i k a t zt i m e s h i f tp u b l i c - k e ye n c r y p t i o nc o n s t r u c t i o n a l s o ；s u f f i c i e n tc o n d i t i o n sf o rc h o s e n c i p h e r t e x ta n o n y m i t yi nf u j i s a k i o k a m o t oa n d o k a m o t o - p o i n t c h e v a l ( r e a c t ) h y b r i dc o n s t r u c t i o n sw e r ep r o v e dr e s p e c t i v e l y ，o n l y c o n t a i n i n gs p e c i f i cr e l e v a n ta n o n y m i t ya n d s o m em 炽l i a l l yw e a kd a t a - p r i v a c yr e q u i r e m e n t s a s e x a m p l e ss h o w e d ，a l lt h e s ec o n d i t i o n sw e r ee a s y - t o - c h e c kc r i t e r i o ni np r a c t i c e t h e s eg e n e r a l c o n s e q u e n c e sw e r ea p p l i e dt os o m es p e c i f i cs c h e m e sa n d ，a sar e s u l t , a n o n y m i t yo fs o m e w e l l k n o w ns c h e m e sw e r er e e s t a b l i s h e di nas i m p l e rw a y f u r t h e r m o r e ，n e s s i es c h e m e p s e c - 1 2 3 sc c aa n o n y m i t yw a sp r o v e da sa p p l i c a t i o i l so ft h e s eg e n e r a lr e s u l t s k e yw o r d s ：c o m p u t a t i o n a lc r y p t o g r a p h y ；a n o n y m i t y ；p r o v a l es e c u r i t y ；k e y p r i v a c y i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均己在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：差王公翅左旦蜜友塞匿名丝厦的硒究 作者签名：l 弹雄一隰耳年上月丘日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 1绪论 匿名性和保密性都是公钥加密方案的重要安全性质，两者都有广泛的应用价值。然 而，对匿名性系统而严格的理论处理却较之保密性要晚得多，在这方面 1 是开创性的 工作，它第一次建立了匿名性质精确的计算密码学概念，并严格证明了e 1 g a m a l 方案、 c m m e r - s h o u p 方案和r a e p r s a 方案的匿名性。直观地讲，匿名性( 亦称公钥隐密性： k e y p r i v a c y ) 与保密性( d a t a - p r i v a c y ) 是完全不同的性质，前者保证密文不泄露用来加密的 公钥，后者则保证密文不泄露其明文。除了隐藏公钥，匿名性还是一个有用的工具，能 用来达到复杂密码方案或协议的特殊功能目标，例如隐形检索方案中对关键字的保密 2 1 、 组群加密方案中对接收方身份的保密【3 】等。因此，同时具有匿名性和保密性的公钥加密 方案有非常重要的应用价值，例如 1 0 中证明了常用的混合方案( f u j i s a k i o k a m o t o 方案 和r e a c t 方案) 能将仅有弱匿名性质的基本组成方案提升为具有最强匿名性质的方案， 并且作为这些一般性结论的具体应用证明了三个著名的n e s s i e 方案p s e c 1 2 3 具有选 择密文匿名性质。 最近，c a n e t t i h a l e v i - k a t z 给出了一种基于i b e ( i d e n t i t y b a s e de n c r y p t i o n ) j j h 密方案 构造普通公钥加密方案的优美方法，并严格证明了其保密性质【4 】。b o n e h k a t z 继而给出 了一种改进1 5 ，在计算效率上要明显优于c a n e t t i h a l e v i k a t z 构造。这两种构造本文今 后分别称之为c a n e t t i h a l e v i k a t z 变换和b o n e h k a t z 变换。两种都是非常一般性的构造， 并且都只要求基本i b e 方案和辅助方案具有弱安全性质即可保证整体方案选择密文保 密。此外，c a n e t t i h a l e v i k a t z 在【6 】中基于所谓2 叉树加密方案( b t e ：b i n a r y t r e e e n c r y p i o n ) 给出了一种前向保密的时变公钥加密方案，这也是一种非常一般的构造，其 公钥不变但私钥随时间变化，即使某一时间区间上的私钥泄露也不会导致在此之前的密 文被破译。 以上这些一般性构造都有重要的理论和应用价值，例如c a n e t t i h a l e v i k a t z 变换和 b o n e h ，k a t z 变换都是不同于以往构造非随机o r a c l e 的公钥加密方案的方法，这一点具有 重要的理论意义。不仅如此，b o n e h k a t z 变换在计算效率方面是一种比较实用的构造， 而时变公钥加密方案的c a n e t t i h a l e v i - k a t z 构造是第一种前向保密的公钥加密方案，其 应用价值是毋雍质疑的。所有这些方案的保密性质都已被严格证明，然而尚不清楚这些 一般性构造的匿名性质或匿名性条件。 关于公钥加密方案匿名性质的研究 1 1本文主要贡献 本文将刻画并证明以上三类公钥加密方案的匿名性条件。首先，建立关于公钥加密 方案的两个通用的新概念，即相对匿名性和相对保密性。通过这些较弱的安全性概念， 建立了公钥加密方案的保密性与匿名性之间两个对偶式的普遍关系，即相对匿名性( 相 对保密性) 连同保密性( 匿名性) 蕴涵匿名性( 保密性) 。对某些特殊方案，相对匿名和相对 保密性概念可以用来大大简化保密性或匿名性的证明。我们建立关于i b e 公钥加密方案 的两个一般性的新概念：全局公钥匿名和全局公钥相对匿名性质，并通过这两个概念刻 画和证明了关于c a n e t t i h a l e v i k a t z 变换和b o n e h k a t z 变换选择密文匿名性的一般性结 果( 定理4 2 - 4 4 、定理4 6 - 4 8 ) 。对这两类方案我们分别给出关于其选择密文匿名性质的 两种充分条件，一种较强( 定理4 2 、定理4 8 ) 而另一种较弱、容易检验但需要依赖于保 密性才能得出完整结论( 定理4 4 、定理4 7 ) 。这些条件都只要求i b e 方案抵抗某种意义 上的选择明文攻击，因此与保密性质相似，这两类构造也能将弱匿名性质提升为最强的 匿名性质。为便于理解和应用，我们在第4 3 节针对目前一些典型的i b e 实例具体检验 这些匿名条件。在第5 节，我们建立关于时变公钥加密方案的前向匿名性质和2 叉树公 钥加密方案的全局公钥匿名性质，并证明c a n e t t i h a l e v i k a t z 一般性构造的前向匿名条 件( 定理5 2 ) 。前向匿名性的直观涵义是：即使某一时间区间i 上的私钥s k ( i ) 被泄露，凭 借s k ( i ) 也无法从以前时间区间上的任何密文识别出该密文的接收者是谁。就作者所知这 是第一次提出前向匿名性概念的计算密码学定义。 最后，给出两个典型的混合加密构造，即f u j i s a k i o k a m o t o 构造和 o k a m o t o p o i n t c h e v a l 构造( r e a c t ) 选择密文匿名的充分条件，这些条件仅包括特定意义 上的相对匿名性质和其它一些自然的弱保密性要求。文中不仅用多个具体实例表明这些 条件都是非常实用的判定准则，而且还进一步应用这些普遍结果，给出对某些具体公钥 加密方案匿名性质的简化证明，并证明了著名的n e s s i e 方案p s e c 1 2 3 的选择密文匿 名性质。 1 2 各节内容概要 第2 节简要回顾所需要的基本概念和结果；第3 节回顾相对匿名性和相对保密性概 念及关于匿名性和保密性的两个普遍关系的证明，并应用于p s e c 1 等实例；第4 节建 立i b e 方案的全局公钥匿名和相对匿名性概念，证明关于c a n e t t i h a l e v i k a t z 变换和 大连理工大学硕士学位论文 b o n e h k a t z 变换选择密文匿名性的两类一般性条件，实际检验几个典型i b e 方案的全局 公钥匿名和相对匿名性质；第5 节刻画关于时变公钥加密方案的前向匿名性质和2 叉树 公钥加密方案的全局公钥匿名性质，并证明c a n e t t i h a l e v i k a t z 一般性构造的前向匿名 条件；第6 节回顾关于f u j i s a k i - o k a m o t o 混合方案和r e a c t 混合方案匿名性的充分条 件，并分别应用于p s e c 2 3 ；最后总结全文。 关于公钥加密方案匿名性质的研究 2 符号与基本概念 2 1符号说明 本节回顾某些基本概念并给出符号约定。x l l y 表示字x 和y 的联结，我们约定这种 联结是有结构的，即从x l l y 总可以准确恢复出x 和y 。i x i 表示字x 的编码长度。设x 是 一个集合，记号a s x 表示从x 随机选取一个元素a ( a 在x 上均匀分布) 。正整数k 的 速降函数是指这样一类函数，当k 充分大时函数值下降得比任何多项式的倒数都要快。 文中所有算法均以伪c 语言表达，并以产木给出算法中的注释。给定某个特定的值a 木， ( a 幸，) 表示二元关系表中第一个字段的值等于a 幸的表项( 这里句点“表示任意的、不 加约定的值) ；该符号可推广到任何n 元关系表，例如，符号( a ，b 幸，) 表示5 元关系表 中第一个字段的值等于a 幸且第二个字段的值等于b 幸的表项。符号上用以表示异常或 错误情况下的输出。概率多项式算法简称为p p t 算法。 2 2 基本概念 定义2 1 ( 公钥加密方案) 一个公钥加密方案n = ( k g ，e ，d ) 是一组p p t 算法k g ，e 和d 。设k 是复杂度参数，k g 是钥生成算法，输出公钥私钥对( p k ，s k ) ：e 是加密算法， 以公钥p k 和明文m 为输入并输出密文y ；d 是解密算法，以私钥s k 和密文y 为输入、 输出明文m 并且满足一致性关系：对任意的k 和m 恒有p 【q ks k ) * - k g ( k ) ；y 卜e ( 1 比 m ) ：d ( s k , y ) = m 】- 1 。 定义2 2 ( m e 加密方案) i b e 加密方案h = ( s e t u p ，u k g ，e ，d ) 是一组p p t 算法，其 中s e t u p 是全局密钥( 亦称主密钥) 生成算法，以k 为输入并输出全局公钥私钥偶( m p k ， m s k ) ；u k g 是用户私钥生成算法，以全局私钥m s k 、用户身份标识a 为输入并输出口 的私钥u s k ( a ) ：e 是加密算法，以全局公钥m p k 、用户身份标识a 和消息m 为输入并输 出密文y ；d 是解密算法，以全局公钥m p k 、用户私钥u s k ( a ) 和密文y 为输入并输出明 文m 。所有这些算法还满足一致性关系：对任何k 、a 和m 恒有 p ( m p k ，m s k ) , - s e t u p ( k ) ；u s k ( a ) - - u k g ( m s k , a ) ； y - - e ( m p k ，a ，m ) ：d ( m p k , u s k ( a ) ，y ) = m 】= l 由于i b e 方案的特殊结构，在刻画其保密性质时需要考虑所谓合谋攻击，这时攻击 者可能( 通过非法入侵或合谋) 持有某些用户a l ，a n 的私钥u s k ( a 1 ) ，u s k ( a n ) 。合谋攻击 用允许攻击者a 访问o r a c l e u k g ( m s k ，) 来刻画，安全的i b e 方案必须能抵抗这类攻击。 大连理工大学硕十学位论文 定义2 3 ( 公钥加密方案的匿名性质1 1 ) n = ( k g ，e ，d ) 是一个公钥加密方案， a = ( a l ，a 2 ) 是p p t 算法，a t k c p a ，c c a ) ，o r a c l e 是一个由a t k 的值确定的o r a c l e 。 考虑以下对抗实验却髫_ a t ( ( 露) ： ( p k o ，s k o ) ，( p k m ，s k l ) - - - - k g ( k ) ；严独立运行k g ( k ) 两次奉 ( m 宰，s t ) “l 愀，p k l ) ； b - - - o ，1 ) ； y + 一e ( p k b ，m 唯) ； d 卜a 2 啪船( y ，s t ) ； i fd = bt h e no u t p u t1e l s eo u t p u t0 对a t k = c p a ，o r a c l e 空；对a n o c c a ，o r a c l e = ( d ( s k o ，) ，d ( s k l ，) ) 且a 不允许向 其o r a c l e - d ( s k o ，) 或d ( s k l ，) 询问y 事。a 的优势函数a d v 。a j v 。o 爿定义为 f 2 p 【脚州a n o 一4 ( 七) = 1 卜l l 。定义做抗适应性选择明文( 密文) 匿名，若对任何p p t 算 法a ，彳咖州a n o 一硎、d p a , a n o 蚴) 是k 的速降函数；今后分别简称为a n 0 一c p a 匿名和 a n o c c a 匿名。记彳咖尹一棚：( 七) - 。燃a d v 酬a 。v o 一爿豫( 七) 。 若需要将这些函数视为计算 时间的上界t 和对o r a c l e 询问总数的上界q 的函数，则用记号a a b f f d 一彳疆0 ，窖) 代替记号 a 咖拿o _ a r k ( k ) o 作为分析匿名性质的一个有力工具，我们还需要相对匿名性概念( 见3 1 节) 。 不难看出匿名性蕴涵相对匿名性。实际上相对匿名性严格弱于匿名性，但对许多具 体方案相对匿名性要容易判定得多，甚至可能无条件成、- y o o l 。另一方面，相对匿名性与 保密性相结合能够蕴涵匿名性，从而能够借助于已经证明的保密性结果和方案的相对匿 名性( 这一点常容易判定) ，推导出方案的匿名性。其精确叙述和证明参见第3 节，我们 在第4 节和5 节完整证明一类匿名条件时需要用到这一结果。最后指出，对i b e 加密方 案同样可以类似地定义匿名性质和相对匿名性质，但本文的工作并不需要。 定义2 4 ( 公钥加密方案的保密性质) h = ( k g ，e ，d ) 是个公钥加密方案，k 是复杂度 参数。a = ( a i ，a 2 ) 是一个p p t 算法，a t k e c p a ，c c a ) ，o r a c l e 是一个由a t k 的值 确定的o r a c l e 。考虑以下对抗实验磁a t k ( 七) ： 关于公钥加密方案匿名性质的研究 ( p k ，s k ) c - - - k g ( k ) ； ( m o ，m l ，s d 卜a l 阢础( p k ) ； b 卜 o ，1 ) ； y 木卜e ( p k ，m b ) ； d 卜a 2d 僦缸( y + ，s t ) ； i fd = bt h e no u t p u t ( 1 ) e l s eo u t p u t ( o ) ； 对滕c p a ，o r a c l e 空；对a t k = c c a ，o r a c l e = d ( s k ，) 且a 不允许向其o r a c l e d ( s k , ) 询问y 。a 的优、万劂，皴月i n 一d 一爿膳定义做 2 p e x p ，, , a d _ a t k ( 露) = 1 卜1i 。若对任何e e t 算法 a ，彳咖箸一硎( 、d r h ，i n 4 d c 翻) 是k 的速降函数，则h 定义做抗适应性选择明文( 密文) 保密， 分别简称为i n d c p a 保密和i n d c c a 保密。a d v 1 1 ”d 一_ ( 七) 宝s u pa , , h , i n d 一彳搿( 七) 。 a e j d j d 了 若需要将这些函数视为计算时间上界t 和o r a c l e 询问总数上界q 的的函数，则用记号 a d ，r ，。m o _ a t k ( t ，g ) 代替记号a d v i n d - a t k ( k ) 。 后面讨论c a n e t t i h a l e v i - k a t z 变换和b o n e h - k a t z 变换时都用到一次性抗强伪造的数 字签名或消息认证方案，在此给出其计算密码学定义。 定义2 5 ( 消息认证方案的抗一次性选择消息强伪造性质5 1 ) x = ( k g ，t a g ，v f ) 是消 息认证方案，k 是复杂度参数、f 是p p t 算法。考虑以下对抗实验唧e x p s u f f 一删1 ( 七) ： k * - - g ( k ) ； ( m 枣，t * ) - - f r a g f ( ( 七) ； i f v f ( k , m ，t 幸) = 1 八iq f t a g f 降1a t 幸仨。r 厂r a g x 严酽。表示f 对o r a c l e t a g k ( ) 的询问集合、 r r 表示o r a c l e t a g k ( ) 对f 的响应集合 t h e no u t p u t ( 1 ) e l s eo u t p u t ( 0 ) ； 大连理工大学硕士学位论文 f 的优势函数以a 口v z s 。u f f c 捌”定义做p 【却筘一c 删1 ( 七) = l 】。 定义做抗一次性选择消 息强伪造，简称s u f _ c m a 0 ) 安全，若对任何p p t 算法f ，相应的优势函数 a a l i , s u f f c 删1 总是k 的速降函数；记彳咖罗一c 枷1 ( 七) 兰s u p a , 4 r z s u f f c 俐( 1 ( | | ) 。 a e p ，p i 1 定义2 6 ( 数字签名方案的抗一次性选择消息强伪造性质f 4 】) 互= ( k g ，s i g ，v o 是数- 7 签名方案，k 是复杂性参数。对p p t 算法a ，考虑以下对抗实验脚e x 矽p 三s u 月f 一洲1 ( 七) ： ( v k , s k ) 卜k g ( k ) ； ( m 幸，o 宰) 卜彳瓤a o ( 让) ； i f v f ( v k , m ，o ) = 1 八a 木星尺叠。八jq t 峰1 严酽矗表示a 对o r a c l e s i g 。k ( ) 的询问集合、尺t o 表示a 从其 签字o r a c l e 所获响应的集合宰 t h e no u t p u t ( 1 ) e l s eo u t p u t ( o ) ； a 的优势函数彳咖晋一伽1 定义做p e x p s , v f 一伽1 ( 七) = 1 】。量定义做抗一次性选择消 息强伪造，简称为s u fc m a ( 1 ) 安全，若对任何p p t 算法a ，以a “7 v 引s u f 一删1 是k 的 速降函数；a d v s u f 一洲o ( 后) 兰s u p 彳咖：芽一伽 ( j j ) 。若需要将该函数视为计算时间 4 e l p ? 上界t 和o r a c l e 询问总数上界q h 、q 。的函数，则用记号a d v s u f 一伽1 ( f ，q a ，g ，) 代替记号 么西p 一伽( 1 ( 后) 。 一7 一 关于公钥加密方案匿名性质的研究 3 匿名性和保密性之间的两个普遍关系 a b d a l l a 等针对i b e 的情形引入了所谓相对匿名性概念，并以此建立了一个关于 i b e 加密方案匿名性的充分条件( 针对其具体应用，他们仅考虑了抗选择明文攻击) 。【1 0 将这一概念移植到传统的公钥加密方案并证明更一般的结果。不仅如此， 1 0 】还进一步 建立一个对偶的概念一相对保密性一并以此建立一个关于保密性的充分条件。正如本节 各种例子所显示的，虽然相对匿名性和相对保密性都严格弱于对应的( 非相对) 匿名性 和保密性，但在具体应用中它们往往很容易判别，因此这些充分条件实际上都是很实用 的判定准则，特别是在以后各节中将做为重要的工具。 3 1相对匿名性及其与保密性的关系 定义3 1 ( 公钥加密方案的相对匿名性质口，1 1 】) 设1 - i = ( k g , e ，d ) 是公钥加密方案， a 2 ( a 1 ，a 2 ) 是p p t 算法，a t k e c p a ，c c a ，o r a c l e 是由a t k 的值决定的o r a c l e 。考 虑以下对抗实验： e x p ，r r e 一一舢一一纭( 未) ： ( p l 【o ，s k o ) ，( p k l ，s k l ) 卜k g ( k ) ；产独立运行k g ( k ) 两次宰 ( m 牛，s t ) + 一a l d 刚8 ( p l ( o ，p k l ) ； m 卜$ o ，l i m * i ；户随机选取与m 乖相同长度的消息m 幸 b , - - - $ o ，1 ) ； y 宰卜e ( p b ，m ) ； d - a 2 “删8 ( y 母，s t ) ； i fd = bt h e no u t p u t ( i ) e l s eo u t p u t ( o ) ； 对a t k = c p l a ，o r a c l e 为空；对a t k = c c a 有o r a c l e = ( d ( s k o ，。) ，d ( s k l ，。) ) ，但与定义 2 3 的( 非相对) 匿名性概念不同，这里允许a 向其o r a c l e - ( d ( s k o ，) ，d ( s k l ，) ) 询问y 木。a 的 优势函数彳咖笔一舢一4 定义为 2 研晟睹舢a t 。( 露) = 1 - 1i 或等价的表达式 i p d = o i b = o 一p d = o i b = 1 l 。若对任何e e t 算法a ，彳咖等a n o 一硎、( , , t d a , p 疆一_ a n o 一砌) 是k 的速降函数，则定义做抗适应性选择明文( 密文) 相对匿名，今后分别简称为 r ea n oc p a 匿名和r ea n oc c a 匿名。记 大连理工大学硕士学位论文 么西笋一舢一脲( 七) 兰s u p 彳幽等a n o 一胱往) ， 月e p 尸7 若需要将这些函数视为计算时间上界t 和对其o r a c l e 询问的总数上界q 的函数，则用记 号彳咖笋一舢一 ( ，g ) 代替记号彳咖笋一舢一一( 七) 。 不难验证匿名性蕴涵相对匿名性。另一方面，以下定理表明相对匿名性与保密性相 结合蕴涵匿名性，从而能够借助于已经证明的保密性结果和方案的相对匿名性( 这一点 常容易判定) ，推出方案的匿名性。定理3 1 是对这一事实的精确陈述，后续的例子给出 其具体应用。 定理3 1 = ( k ge ，d ) 是i n d _ c p a ( i n d _ c c a ) 保密的公钥加密方案。若兀也是 r e a n o c p a ( r ea n o _ c c a ) 匿名的，则n 必a n o _ c p a ( a n oc c a ) 匿名。具体有不 等式： 彳西，一硎( f ) 彳衅一舢一c p a ( t ) + 2 a d v f f 9 d 一嗍( f ) 彳咖参0 一a _ ( f ，g ) 彳咖尹二- 舢一a _ ( f ，q ) + 2 a d v t n d c c _ ( t + o ( q r a ) ，9 ) 其中乃是解密算法d 的计算时间。 证明这里仅给出对c c a 情形的证明，c p a 情形的证明本质相同但更简单，不再赘述。 设a = ( a i ，a 2 ) 是破译的a n o c c a 匿名性的e e t 算法，以下基于a 构造一个e e t 算法b a = - ( b i ，b 2 ) 来破译n 的i n d c c a 保密性。考虑以下对抗实验及算法b 的实现：- 唧e x p ，r i n 占d 一黝( 七) ： ( p k o ，s k o ) 卜k g ( k ) ； ( m 0 ，m i ，s t ) 卜曰p 成j ( p k o ) ，其中b l 实现如下： ( p k l ，s k j ) 卜k g ( k ) ； ( m 母，s t a ) 卜彳p 吼加幽j ( p k o ，p k l ) ； m o 卜m 幸；m 1 卜$ o ，1 ) i m * i ；s t 卜s t a i l p k l f i s k l ； r e t u m ( m o ，m l ，s t ) ； b , - - ， 0 ，1 ) ； y 奎卜e ( p k o ，m b ) ； d 卜衅( y 宰，s t ) ，其中b 2 实现如下： p a r s es ta ss t a i l p k l i l s k l ； d + 一彳夕p 幽j ( y ，s t a ) ； r e t u r n ( d ) ； i fd = bt h e no u t p u t ( i ) e l s eo u t p u t ( 0 ) ； 关于公钥加密方案匿名性质的研究 b 以其自身的o r a c l e d ( s k o ，) 仿真a 的o r a c l e d ( s k o ，) ；又由于b 已知s k l 故b 能完 全实现对a 的o r a c l e d ( s k l ，) 的仿真。显然这两种仿真都是完美的( p e r f e c t ) 。 根据以上构造不难直接验证b = 0 情形的唧e x p 柑i n d 一删( 七) 恰等价于b = o 情形的 却：髫一删( 膏) ，而b = l 情形的却筹一吲( 七) 恰等价于b = o 情形的饿e x p 艇，厂, o v o 一删( 是) 。另一 方面，可以构造n 的另一个i n d c c a 破译算法c a = ( c i ，c 2 ) ，c 与b 的唯一差别是 c p o k o j ( p k o ) 以么尸嚆d 札一( p k j ，p k o ) 的f g 式调用a j ，即对换p k o 和p k l 的角色，从而b = o 情形的唧e x p 村m d c 翻( 七) 恰等价于b = l 情形的却：劣一c 翻( 七) ，而b = l 情形的唧e x p 啦i n d c c a ( k ) 恰等 价于b = l 情形的e x p - a n o 一捌( 七) 。因此： 么i n ，占d 一砌( 素) = j q p r 唧, - 。i n ，占d c c _ ( k ) = i l b = o 一，1 a p 唧”，r i n ，矗d 一黝( 史) = 1 1 6 = 1 】l 。= ip e x a n o 一彻( 七) = lb = o 】- h 却等a n o 一倒( 七) = 1b = 0 i 且 彳咖玎i n ，c d f 吲( 七) = i ，1 p i 唧e 厅i n ，c d 一倒( 七) = 1 i b = 0 一，1 p 唧”。i n ，c d 一黝( 七) = l i b = l 】i = f 研却髫一蚴( 七) = 1 1 6 = l 】_ h 脚嚣舢一蚴( 后) = 1 1 6 = 1 】i 两式相加得a z h , 枷i n d c c al k ，t 月i n 。c d 一矧( j | ) i p 【却髫一吲( 七) = i l b = o 】一j p 【却等舢一删( 七) = 1 1 6 - b o 】| + i ，1 p 唧”。a n o 一倒( 七) = 1 | 6 = 1 】- p e x # 匿a n o 一删( 后) = l i b = 1 i 彳咖等一c 翻( 七) 一彳咖子a n o c 翻( 后) ，即： a d v a n o 一吲( 七) 爿咖等a n o 一黝( 七) + 彳咖黠一c c a ( k ) + a a v , 罂一吲( 七) 从这一不等式立即导出待证的不等式；从算法b 、c 的构造不难直接验证相应的计算复 杂度。 口 定理3 1 是一个有力的工具，能用来大大简化某些公钥加密方案的匿名性证明。以 下给出一些具体的实例。 例3 1 ( e i g a m a l 方案的a n o c p a 匿名性) 在判定性d i f f i e h e l l m a n 问题的难解性假设 大连理工大学硕士学位论文 下已经证明e 1 g a m a l 方案是i n d c p a 保密的【1 2 ，13 1 。进一步分析e i g a m a l 方案( 图3 1 ) ， 注意到在相对匿名对抗实验e x p 蒹：黯硎( 七) 中攻击算法a 2 接受挑战密文 ( c h a l l e n g e e i p h e n e x t ) y * = ( y , ，其中w = t m ，m 是随机选择的群元素( 但m 的编码长度 等于a l ( p k o ，p k d 输出消息m 的编码长度) ，在b = o 和b = l 两种情形下y 宰对a 2 有完全相 同的概率分布( y 的值均为矿，w 的值分别为x o m 和x m ) ，b k i i i i a a v 琵孟黯c e a ( k ) = 0 ， 即e i g a m a l 方案无条件r ea n oc p a 匿名。根据其i n dc p a 保密性结论和以上分析， 应用定理3 1 立得e 1 g a m a l 方案在判定性d i f f i e h e l l m a n 问题难解性假设下a n oc p a 匿名，这正是 1 用直接方法证明的结论。 图3 1e i g a m a l 方案 f