基于双线性映射的公钥叛逆者追踪.doc

基于双线性映射的公钥叛逆者追踪吕 锡 香1 , 杨波2 , 裴 昌 幸1(11 西安电子科技大学 综合业务网理论与关键技术国家重点实验室 ,陕西 西安 710071 ;21 华南农业大学 信息学院 ,广东 广州 510640)摘要 : 基于椭圆曲线上 Weil 配对理论提出一种新的叛逆者追踪方案 ,利用 Weil 配对的双线性特性并结合简单多项式在方案中实现了以前方案所不具有的密钥托管 ,使得方案具有全程托管功能 ,允许托管 代理用一个简单的密钥解密任意公开钥所加密的密文 ,有利于系统管理者管理整个系统 ,也有利于有关 部门对整个行业实施监管. 在同等安全级别下 ,相对于传统基于有限域上离散对数问题的叛逆者追踪 , 该方案在效率上占有相当优势.关键词 : 叛逆者追踪 ;广播加密 ;电子版权保护中图分类号 : T P911 . 22文献标识码 : A文章编号 :100122400 (2006) 0620935204Publ ic2key tra itor trac ing ba sed on the bil inear ma pL X i2x i a n g 1 , Y A N G B o2 , P E I Ch a n g2x i n g 1( 1 . Stat e Key L a b. of Integrat ed Service Net wo r ks , Xidia n U niv. , Xia n 710071 , China ; 2 . College ofInfo r matio n , So ut h China A gricult ural U niv. , Guangzho u 510640 , China)Abstract : A new t raito r t racing scheme i s p ropo sed by using t he Weil p ai ring in ellip tic curves. Thep ropo sed scheme sho w s t hat t he Weil p airing enable s us to add a glo bal escro w cap a bilit y to t he t raito r t racing system. A single escro w key ena ble s t he decr yp tio n of cip hert ext s encr yp ted under any p ublic key ,w hich i s e ssential fo r t he system ma nager to ma nage t he glo bal sit uatio n. The a ut ho ritie s can al so supervi se t he entire mar ket a nd fo r bid t he sp read of bad info r matio n wit h t he glo bal escro w capa bilit y. In additio n , wit h t he sa me securit y , t hi s scheme , w ho se op eratio ns are o n ellip tic curves , i s mo re efficient t han t he p revio us scheme s ba sed o n t he di screte - lo g p ro blem o ver t he gro up G.Key Words : t raito r t racing ; broadca st encr yp tio n ;elect ro nic cop yright p ro tectio n当大规模的数字产品通过广播信道分发给授权用户时 ,一般情况下 ,数据都是以加密的方式分发并且只有授权用户才能解密 ,这时数据提供者会给每个授权用户提供一个包含解密密钥的硬件或软件解码器. 但 是 ,这种加密不能阻止一些授权用户 (叛逆者) 将他们的解密密钥泄露给非授权的用户 (盗版者) . 为了解决这一难题 ,Cho r 和 Fiat 等在 1994 年提出了叛逆者追踪的概念并且给出了一种叛逆者追踪方案 ,用以阻止授权 用户泄漏其解密密钥. 其基本的指导思想是让所有的用户秘密钥都不相同 ,并且使得每一个分发过的秘密钥都能够追踪到特定解码器的最初拥有者 ,这相当于在用户的解密密钥里加入了指纹信息. 在这之后 ,人们陆 续设计了许多叛逆者追踪方案 ,包括对称的 13 、非对称的 47 ( 能够提供不可否认性) 、基于公钥密码体制 的 24 ,7 等. 这些陆续提出的一系列设计巧妙的方案确实逐步发现并解决了许多关键性的问题 ,例如 ,防共谋 安全 ,不可否认性等等. 近年来随着椭圆曲线上的双线性映射在密码学上的应用和发展 ,人们先后设计了几种基于双线性配对的叛逆者追踪方案 8 . 然而 ,正是由于双线性配对的各种灵巧特性 ,它易于用来构造密码体制 ,也正是由于这些灵巧特性 ,那些设计巧妙的密码体制也很容易被破解. 笔者给出一种基于双线性映射 的非对称叛逆者追踪方案 ,该方案相比以往解决了以下新问题 : (1) 方案具有全程托管功能. 这种全程托管功收稿日期 :2006201210基金项目 :国家自然科学基金项目( 60372046) ;国家部委重点实验室基金项目资助( 51436040204D Z0102)作者简介 :吕锡香( 19782) ,女 ,西安电子科技大学博士研究生1能允许托管代理用一个简单的密钥解密任意一个数字产品供应商所加密的密文 ,这一点有利于系统管理者管理整个系统 ,也有利于有关部门对整个行业的监管 ; ( 2) 由于运算是在椭圆曲线 E ( Fq ) 上点的加法群中( 其中 q = p m , p 是素数) ,在相同安全级别下运算效率提高很多.双线性映射1设 G1 和 G2 是两个阶为素数的群 , 并且在 G1 和 G2 中求解离散对数是困难的. 那么存在这样的可计算双线性映射 e : G1 G1 G2 .实际中 G1 代表椭圆曲线 E ( Fq ) 上点的加法群 ( 其中 q = pm , p 素数) , 而 G2 代表有限域乘法群的子群. 此双线性映射有下面两个特性 :(1) 双线性对所有的 P , Q G1 有 e ( a P , bQ ) = e ( P , Q) ab ;( 2) 非退化性如果 P 是 G1 的生成元 , 那么 e ( P , P) 是 G2 的生成元.基于双线性映射的叛逆者追踪方案2方案具有全程托管功能. 这种全程托管功能允许托管代理解密任意一个数字产品供应商所加密的密文 ,这一点有利于系统管理者管理整个系统 ,也有利于有关部门对整个行业的监管 ,禁止有害信息的传播.21 1初 始 化设 G 是 BD H 参数产生器 (双线性 Diffie2Hell ma n 参数产生器) ,给定秘密参数 k Z+ , 系统管理员执行如下算法 :( 1) 输入 k 执行算法 G 以产生素数 q 、两个阶为 q 的群 G1 和 G2 、双线性映射 e : G1 G1 G2 . 设 P 是群 G1的生成元 , R 是 G 3的任意元 , g = e ( P , R) .1( 2) 选择两个秘密随机数 s Z 3 , b Z 3 和 Z q 上的一个秘密随机多项式 F1 ( x)+ a2 v x 2 v .= s + a1 x +qq设多项式 F ( x , y)F1 ( x) + by . 可以通过选取任意的 a1 , a2 , a2 v , b 获得任意的加密公开钥 ,而对这些公=开钥加密的密文托管代理都可以解密.(3) 选择哈希函数 H : G2 0 , 1 n.M = 0 , 1 n是消息空间 , 系统参数为 . 托管密钥为 s Z 3 .qr j“表示”的定义 : 设 h0 , h1 , hv 是群 G 上的任意元 , hj = g, v. 对于 G 上的某个确定元, j = 0 , 1 , h v 的 ( v +1) 维向量= , 或者y = gb , y 在基 h0 , h1 , hv 下的表示是一个满足 y = h 0 h 10 1v说满足 r = b , 其中“, ”表示向量的内积 , r = .新用户加入过程实际上是系统管理员和新用户之间执行的一个协议 ,此过程利用不经意多项式估值协u . 其中 , z u 是2 v议获得非对称性. 协议的执行结果是新用户 u 得到秘密钥 k =uu系统管理员在 Z 3 上选择的随机数 , 而u 是用户 u 在 Z 3 上选择的秘密随机数. 实际上 , 用户 u 并不需要存储qq 计算整个密钥向量.整个 k , 在需要时可以由多项式 F 上的秘密点u设 Q1 = a1 P ,= bP , 则加密公开钥 kp = g , Q1 , ., Q2 v , Q2 v +1 , y , 其中, Q 2 v = a2 v P , Q2 v +1g = e ( P , R) , y = gs . 用户 u 解密密钥 k u=- a1- a2 v设 y = gs , h0 = g ; h1g , h= g- b (实际上 ,并不需要计算这些值) . 由“表示”的定= g ; h2 v =2 v2 vF( z u , ) () z u)F( z u , ) - ( a z + + a z u + b )z) ugs义和等式 ( h0 )(h u = g= = y , 可知 k 是 y 在基 h0 , h1 ,uh1h2 vu 1 u 2 v u,uh2 v , h下的一个表示.21 3加密利用加密公开钥加密会话密钥 sk 0 , 1 n , 做如下计算 :(1) 选取随机数 r Z 3 ;q(2) 计算使能头 : h = , 其中 U 1 = r P , U 2 = rQ1 , U 3 = rQ2 ,(3) 广播密文 C = ( h , Es ( M) ) , 其中 M 是待加密的广播数据 , Es ( ) 是对称加密算法.kk21 4解密只考虑使能头的解密. 设 h = 是用公开钥 kp 加密的使能头 , 又设 g= e ( U 1 ,2 vF ( z u ,u ) R) e ( U 2 , - z u R ) e ( U 3 , -z2 R ) e ( U 2 v +1 , - z2 v R ) e ( U 2 v +2 , - u R ) 和 U= ( -z i U i +1 ) , 则uuui = 1. 用户 u 利用解密密钥作如下计算以解密使能头 h 获得会g= e ( U 1 , F ( z u ,u ) R) e ( U , R) e ( U 2 v +2 , - u R )2 v话密钥 sk :U= ( -z i U i +1 ) , g= e ( U 1 , F ( z u ,u ) R) e ( U , R) e ( U 2 v +2 , - u R ) , sk= V H ( g) .ui = 1托管解密 ,托管代理用托管秘密钥 s Z 3 (或 sR ) 解密 ,计算 : V H ( e ( U 1 , sR ) ) = sk .q21 5叛逆者追踪2 vz1z2z12 vz2. n 表示用户数 , 因此 n 远远大于参数 v , 因而有 n 2 v. 设C 是 Z n定义 n 2 v 矩阵 : H =q2 vz nz上的码 , 其一致校验矩阵为 H , 即对任意 c C , 有 c H = 0 .引理 1设1 ,n 是拉格朗日系数 , 对所有的次数小于 n 的多项式 f Zq x 满足 :1 f ( z1 ) +n f ( z n ) = f ( 0) . 那么 , C = | M Zq x , de g ( M) n - 2 v , 并且 C 是线性码 ,证明(1) 一方面 ,显然 1 M ( z1 ) , ,n M ( z n )M Zq x , deg ( M) |, cn 具有 的形式 , 则对于 l = 1 , 2 ,空间为C. 若, cn C, c1 , = i M ( zi ) zl2 v ,有 zl , zli = 0 ,因而有 H = 0 ,所以 C C .1ni = 1= n - 2 v = di m ( C ) .另一方面 ,显然 di m ( C )C 是C 的子空间 , 而 C 与C 又具有相同的维数 , 则C = C .(2) 根据一致校验矩阵 H , 直接得出C 信息率为 ( n - 2 v) / n , 最小汉明距离为 2 v + 1 .根据 R S 线性码的定义 9 可知码 C 是 RS 码. 下面利用 R S 码的纠错能力来构造叛逆者追踪算法.t, ut 是叛逆用户集合. 给定盗版解密密钥 K = l Kul , 将 K表示成 K = . 设 =, K2 v ,l = 1 , 由向量的定义可知存在一个向量 v = , 对所有 l = 1 , H =. 显而易见 , 这样的 v 便代表了叛i | u1 , ut 时 , vi = 0 , 并且 v 满足 2 v , 方程组有 多个解 , 任取一个即可) . 定义向量 = - v , 显然 , 是线性码C 的一个码字 ( H = H - v H = - = 0) .假设 t v , 那么 v 的汉明重量将小于等于 v , 因此是一个和码字 至多有 v 个不同位的 n 维向量. 根据 线性码的特性 , 码字 是码C 中惟一一个具有这种特性的码字. 可以由通过 B2W 算法 10 在多项式时间内求得. 而 v = - , 至此追踪者得到了叛逆用户集合 v.安全性分析3从两个方面考虑方案的安全性 :(1) 一方面 ,在定理 1 和定理 2 的保证下 ,恶意者不可能构造出追踪者追踪不到的有效解密密钥.定理 1给定 y , 计算 y 在某个给定的基 h0 , h1 ,困难性 11 ., h2 v , h下的表示和在群 G 上求解离散对数有相同的定理 2假设存在一个攻击算法 ,在给定系统公开钥和 t 2 v +2 个随机值 的情况下 , 该算法能够输出 y 在基 h0 , h1 , h2 v , h下的一个表示 , 记作 K= , 而 K= 不是向量F ( z i ,i ) , z i , z2 , z2 v ,i 的线性组合 , 那么 , G 上的离散对数问题可解 12 . 和解密密钥为 U 1 , sk引理 2设 H 是从 G2 到 0 , 1 n的随机语言机模型. 如果在群 G1 中 BD H 问题是困难的 ,则 (在定理 1 的前提下) 文中加密方案是语义安全的.证明假设存在一个敌手产生两个明文消息 M0 , M1 G2 , 得到其中一个明文对应的密文 C , 如果这个敌手能够以明显的优势判断出与 C 对应的明文 M d , d 0 , 1 , 那么由以下过程可知这样的敌手可以解决群G1 中的 BD H 问题.在群 G1 中任取 = , D = e( P , P) abc G2 是群 G1 中 BD H 问题的解.令 s P = P1 , R = P2 . 实际上 , 此时秘密钥 dk = ab P .敌手给出两个明文消息 M1 , M2 G2 .随机选取 d 0 , 1 , 构造加密使能头 C = ( P3 , V ) , 其中 V = M d H ( e ( P1 , c P2 ) ) .实际上 ,此时 C 的解密算法为 :V H ( e ( P3 , dk ) ) = V H ( D) , 其中 dk 为秘密钥.反馈加密使能头 C 给敌手 , 敌手反馈 d 0 , 1 .如果 d= d , 输出 D = e ( P , P) abc .因为 D = e ( P , P) abc 时相应的明文为 M d , 即敌手有不可忽略的优势决定 d= d , 则敌手就有不可忽略的优势解决群 G1 中 BD H 问题 ,因为 D = e ( P , P) abc 是群 G1 中 BD H 问题的解. 由于在群的各项参数满足要求的情况下 ,群 G1 中 BD H 问题是困难的 ,所以本加密方案是语义安全的.效率4在本方案中 ,用户解密密钥的长度为 Zq 上的 3 个元 , 加密公开钥为群 G1 上的 2 v +1 个元和 G2 上的 2 个元 , 托管密钥为 Z 3 上的 1 个元; 加密算法仅需要2 v +2 次 G1 上的标量乘法运算和一次模指数运算 (或者一次q配对运算) , 解密算法仅需要 2 v +2 次 G1 上的标量乘法运算和一次配对运算. 在相同安全级别的情况下 ,椭圆曲线上的密码体制存储要求要小得多而运算要快得多 ,因此 ,相对于传统基于有限域上离散对数问题的叛逆者追踪方案 ,在同等安全级别下 ,本方案在效率上占有相当优势.结 束 语5数字产品的版权保护问题是信息化社会必须解决的重要问题 , 叛逆者追踪机制是禁止数字产品盗版的关键技术. 笔者提出的基于椭圆曲线上 Weil 配对的叛逆者追踪方案 ( 相对于传统基于有限域上离散对数问( 下转第 952 页)结 束 语3给出了一个统计零知识证明协议 ,来证明一个承诺值在一特定区间内 ,其效率比已知的协议更高. 该协议可用于电子现金、群签名 、可证实加密等安全协议.参考文献 : 1 Atenie se G , Ca meni sch J , J o ye M , et al . A Practical and Pro va bly Secure Coalitio n2re si sta nt Gro up Signat ure Scheme A . CR YP TO 2000 , L NCS 1 880 C . Berlin Heidel ber g : Sp ringer2Verlag , 2000 . 2552270 . 2 伍前红 , 张键红 , 王育民. 简单证明一个承诺值在特定区间内 J . 电子学报 , 2004 , 32 (7) :1 07121 073 . 3 Zha ng Futai , J i Do ngyao , Wa ng Yumin. A Publicly Verifia ble Seeret Sha ring Scheme Ba sed o n Di screte Lo garit hm J .J o ur nal of Xidia n U niver sit y , 2002 , 29 (1) : 629 . 4 Bo udo t F. Efficient Proof s That a Co mmit ted N umber L ie s in a n Interval A . EU ROCR YP T 2000 , L N CS 1 807 C .Berlin Heidel ber g : Sp ringer2Verlag , 2000 . 4312444 . 5 Fuji saki E , O ka mo to T. St ati stical Zero Kno wledge Pro tocol s to Pro ve Mo dular Polyno mial Relatio ns A . CR YP TO97 , L NCS 1 294 C . Berlin Heidel ber g : Sp ringer2Verlag , 1997 . 16230 .(编辑 : 高西全)( 上接第 938 页)题的叛逆者追踪方案) 在效率上占有相当优势 ;而且方案具有全程托管功能 ,允许托管代理用一个简单的密 钥解密任意一个数字产品供应商所加密的密文 ,这一点有利于系统管理者管理整个系统 ,也有利于有关部门 对整个行业的监管 ,禁止有害信息的传播.参考文献 :Cho r B , Fiat A , Nao r M . Tracing Traito r s A . A dvances in Cr yp tolo gy2CR YP T94 : L N CS , Vol 839 C . Berlin : Sp ringer2Verlag , 1994 . 2572270 .Bo neh D , Franklin M . A n Efficient Public Key Traito r Traci ng Scheme A . A dva nce s in Cr yp tolo gy2CR YP TO99 : L N CS , Vol 1 666 C . Berlin : Sp ringer2Verlag , 1999 . 3382353 .Yo shida M , Fujiwa ra T. A Subscriber2Excl uding a nd Traito r2Tracing Broadca st Di st ributio n System J . IEIC E Tra nsactio ns o n Fundamental s of Elect ro nic s , Co mmunicatio ns a nd Co mp uter Sciences , 2001 , E842A (1) : 2472255 .Kuro sawa K , Demedt Y. Op timum Traito r Tracing and A symmet ric Schemes A . A dva nce s in Cr yp tolo gy2EU ROCR YP T98 : L N CS , Vol 1 403 C . Berli n : Sp ringer2Verlag , 1999 . 1452157 .Pf tzma nn B . Trial s of Traced Traito r s A . Proc of Info r matio n Hiding96 : L N CS , Vol 1 174 C . Berlin : Sp ringer2Verlag , 1996 . 49263 .Pf tzma nn B , Waidner M . A symmet ric Fingerp rinting fo r L ar ger Coll usio ns DB/ OL . ht tp :/ / po rtal . acm. o r g/ cit atio n. cf m ? id = 266453 &t yp e = p df , 2005212211 .L i Yo ng , Yang Bo . A n Efficient A sy