2009年1月12日星期一

广播加密算法调研报告



广播加密算法调研报告

一、广播加密问题
1、问题的提法
一个系统有一个广播源和n个用户,订阅者S为用户集的一个子集,大小为k。广播源将消息m加密后广播给所有用户,使得S中的用户解密得到m,非S中的用户
无法解密得到m。其中如何加密解密,并使得密钥和密文长度尽量短,就是广播加密问题。相当于多把钥匙一把锁,锁可以制定,想让谁能开谁就能开,而且想让谁能开谁才能开。
注意到,不可以给每个订阅者单独加密,这样虽然可以把广播加密问题归结为已经解决的点对点加密问题,但是实际中不能接受:应为那样广播源加密的计算开销将随着k的增大而线性增大。这是广播加密问题和传统的加密问题的区别。
广播加密问题的形式化提法:
通过
Setup(用户总数 n)函数得到一个广播源的公钥PK,每个用户i的私钥di,i=1,..,n。广播源针对订阅者集合S加密消息m,即执行加密函数Encrypt(广播明文m, 订阅者集合S, 公钥 PK)得到密文Hdr,通过网络广播Hdr给所有用户。所有用户都有相同的解密函数Decrypt(密文Hdr,私钥d)用户i接收到Hdr后计算Decrypt(Hdr, di)Decrypt(Hdr, di)=m当且仅当i属于S。注意到,初始化公钥和私钥的算法与订阅者S无关,实际中订阅者会经常变化。我们希望开发出其中Setup、Encrypt、Decrypt的算法,满足一系列安全要求,并且PK、di关于n不太长,给定m后Hdr不太长。
关于广播正文m的一点注解:实际中广播内容是一段比较长的视频流stream,但是用此非对称加密算法加密stream可能无法满足实时性需要,因此,我们用计算复杂度比较低的某种对称加密算法加密stream,设对称密钥为K,然后用广播加密算法(非对称加密)加密此对称密钥K,然后广播非对称加密后的K和用K对称加密过的stream即可满足实时性的需要。因此我们下面讨论的广播正文m,实际就是这里的对称密钥K,因此,m只需要是某个随机的整数即可,与待广播的视频流stream无关。

2、广播加密问题的若干安全要求:
防破解:防止非S中的用户通过Hdr得到m。
盗版追踪:如果S中的某个i将di出卖给非S中的j,如何检测到并确定i的行为。
防恶意插播:如果另一个非法广播源在广播信道中广播内容,接收端如何识别,也就是如何验证广播源的身份。 

3、接收端无状态
[todo]

二、 广播加密算法
1、多项式插值
91Berkovits的《How to broadcast a secret1》提出这样一个基于拉格朗日多项式插值的广播加密算法,它利用了这样一个事实:一个n阶多项式能被平面上(横坐标互不相同的)n+1个点确定。
算法构造的思路如下(a special but typical case)
Setup(用户总数 n)
随机生成平面上
横坐标互不相同的n个点,分配(xi,yi)作为用户i的私钥di。不妨设所有xi都不为0。
不用公钥。
Encrypt(广播明文m, 订阅者集合S),S的大小为k
计算一个k阶多项式P,过下列k+1个点:(0,m), (xi,yi) ,i属于S
然后广播密文Hdr为一个长度为k的串/数组:(xi,yi),i不属于U,且(xi,yi)在P上,不妨设所有xi都不为0。
Decrypt(密文Hdr,私钥di)
如果用户i属于S,则i知道k+1个在P上的点(k个来自Hdr,还有一个是自己的私钥),从而确定P并能够求出P在0点的值,也就是密文m
否则i只知道k个在P上的点,自己的私钥(xi,yi)不在P上,无法求出P在0点的值。

实际加密的时候还要引入j个扰乱的点,可能是为了安全,为了计算方便,作者给出了矩阵描述的等价算法。


2、子集覆盖
3、配对
05年
Boneh等人的《Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys2》利用配对技术构造了这样一个广播加密算法,它利用了双线性DH假设。具体来说,给定误差限,给定p阶双线性群G和它上面的双线性映射e(相关定义和性质见附录),若h,g随机取值于G中 随机取值于中,则不存在这样一个(确定性的?且多项式时间的?)算法A使得
,其中
注意到,如果能在G中从g和计算出,则显然可计算出因为其中已知。在G中从g和计算出就是经典的离散对数计算,因此双线性DH假设比离散对数假设更强,如果离散对数多项式可解则双线性DH假设不再成立!(介于二者难度之间的还有一个DH假设,见附录)
算法构造的思路如下
(a special but typical case):
Setup(用户总数 n)
随机取值于中,令
公钥PK:
私钥di:
Encrypt(广播明文m, 订阅者集合S)
t随机取值于中,不妨设,广播密文为一个二元数组Hdr=(C0,C1),其中


Decrypt(密文Hdr,私钥di)


三、研究者
1、Naor
2、Boneh
四、应用
1、DRM
2、CA for IPTV
附、Mathematical Background


http://www.springerlink.com/index/XXBDHG4QH59RGCH4.pdf

http://crypto.stanford.edu/~dabo/papers/broadcast.pdf

没有评论: