允許免費(fèi)接收者的完全子樹廣播加密方案
admin 由于數(shù)字化信息極易被復(fù)制、修改和傳播，盜版現(xiàn)象日益嚴(yán)重，給相關(guān)權(quán)利人造成巨大的經(jīng)濟(jì)損失。廣播加密技術(shù)解決版權(quán)保護(hù)問題并能有效地管理密鑰。但用戶量巨大的時(shí)候，通信量和用戶端密鑰存儲(chǔ)量都急劇增加，為了解決這一問題，本文提出一個(gè)允許免費(fèi)接收者的完全子樹廣播加密方案，當(dāng)撤銷用戶很多的時(shí)候，顯著降低了系統(tǒng)的通信量。
一、允許免費(fèi)接收者的完全子樹方案
1、 概念與定義
定義U是系統(tǒng)中所有用戶集合， |U|=n；R是撤銷用戶集合，|R|=r；F是免費(fèi)接收者集合，表示那些沒有付費(fèi)訂閱服務(wù)卻能解密廣播消息的用戶，|F|=f。
因子
，表示系統(tǒng)可忍受免費(fèi)接收者的程度。
當(dāng)FRratio=1時(shí)，系統(tǒng)完全開放廣播，所有用戶u∈U都能正確解密廣播消息；當(dāng)FRratio=0時(shí)，系統(tǒng)禁止免費(fèi)接收者，只有授權(quán)用戶u∈P能夠正確解密廣播消息，用于版權(quán)管理時(shí)，系統(tǒng)根據(jù)數(shù)字內(nèi)容的受歡迎程度、訂閱者數(shù)量、價(jià)格等參數(shù)確定某個(gè)合適的FRratio。
在滿樹中，v表示一個(gè)節(jié)點(diǎn)，T（v）表示以節(jié)點(diǎn)v為根節(jié)點(diǎn)的子樹，L（v）、R（v）分別表示以節(jié)點(diǎn)v的左孩子和右孩子為根節(jié)點(diǎn)的子樹。使用節(jié)點(diǎn)的序號(hào)表示某個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)序號(hào)的標(biāo)記方法是按層次從左到右序號(hào)依次增大，滿二叉樹的根節(jié)點(diǎn)序號(hào)為1，如圖1：
2、方案描述
我們提出的完全子樹廣播加密方案是子集覆蓋模型下的一個(gè)實(shí)例，在該方案中用戶被組織成一個(gè)滿二叉樹的葉子節(jié)點(diǎn)，以某個(gè)節(jié)點(diǎn)vi為根的子樹T（vi)中包含的用戶集合為子集，給定撤銷用戶集合R，在Steiner樹（R）中尋找U\R的一個(gè)覆蓋。我們?cè)谕耆訕浞桨傅幕A(chǔ)上，引入可控?cái)?shù)量的免費(fèi)接收者，減少覆蓋集合的大小，從而減少通信量。
令fr=FRratio×|R|是系統(tǒng)允許的免費(fèi)接收者數(shù)量，F(xiàn)是免費(fèi)接收者集合，滿足|F|=f≤fr。定義V={Vi1，Vi2，...Vit}是二叉樹節(jié)點(diǎn)的集合，且滿足：
當(dāng)|V|=t取最小的時(shí)候，F(xiàn)為最優(yōu)。
從上面的定義可以看出，集合V就是允許免費(fèi)接收者條件下，在完全子樹方案中的一個(gè)覆蓋，集合V的大小決定了廣播消息的長度。用戶仍然同完全子樹方案一樣，存儲(chǔ)自己到根節(jié)點(diǎn)路徑上的密鑰，大小為O（log（n））。
使集合V的大小盡可能小是一個(gè)最優(yōu)化問題。定義OPT（i，T（v）），i=0，1...fr為在節(jié)點(diǎn)v的子樹T（v）引入最多i個(gè)免費(fèi)接收者，集合V大小最小。當(dāng)i≥|T（v）∩R|時(shí)，允許的免費(fèi)接收者數(shù)量已經(jīng)超過了T（v）下的撤銷用戶，如果T（v）的所有用戶都是撤銷用戶，OPT（i，T（v））=0，因?yàn)樵谠黾舆@些撤銷用戶并不能帶來益處，如果T（v）下并不都是撤銷用
戶，OPT（i，T（v））=1，因?yàn)榭梢允褂靡粋€(gè)密鑰，使T（v）下的所有用戶都能正確解密廣播消息；如果節(jié)點(diǎn)v滿足，L（v）∩R=_且R（v）∩R=_，那么OPT（i，T（v））=1，因?yàn)榭梢詢H僅使用單個(gè)密鑰，就使T（v）下的所有用戶都能正確解密廣播消息；否則對(duì)每個(gè)i（0≤i≤fr）0，有：
根據(jù)上述的最優(yōu)化函數(shù)，可以使用動(dòng)態(tài)規(guī)劃計(jì)算出OPT（i，T（root））,，0≤i≤fr的值，并取最小值。方案的通信量低于完全子樹方案，而且通信量的大小可以通過參數(shù)fr調(diào)節(jié)。但可以看出，盡管得到了最優(yōu)的結(jié)果（不超過給定的免費(fèi)接收者數(shù)量，通信量最?。┦褂脛?dòng)態(tài)規(guī)劃求最優(yōu)值非常耗時(shí)Onf2，當(dāng)用戶數(shù)量n很大的時(shí)候無法實(shí)用。為此，這里采用貪婪算法，以減少計(jì)算量。
方案將系統(tǒng)中的用戶被組織為滿二叉樹的葉結(jié)點(diǎn)，為（R）（Steiner樹）的每個(gè)節(jié)點(diǎn)vi增加2個(gè)標(biāo)記，標(biāo)記fvi=|T（v）∩R|，即在節(jié)點(diǎn)vi下撤銷用戶的數(shù)量，標(biāo)記cvi等于T（vi）中包含的只有一個(gè)兒子節(jié)點(diǎn)的數(shù)量（即完全子樹方法覆蓋的數(shù)量），如圖2所示。方案采用貪婪算法尋找免費(fèi)接收者，并使用完全子樹方案廣播消息。
在（R）中，如果某個(gè)節(jié)點(diǎn)的f較小，而c較大，那么我們就可以在引入較少的免費(fèi)接收者的同時(shí)降低較多的通信量。并且注意到當(dāng)某個(gè)節(jié)點(diǎn)vi的標(biāo)記c≤1，且其父節(jié)點(diǎn)有兩個(gè)孩子，那么將該節(jié)點(diǎn)下的撤銷用戶作為免費(fèi)接收者不會(huì)降低通信量。如圖2，在節(jié)點(diǎn)A引入3個(gè)免費(fèi)接收者不能降低通信量，節(jié)點(diǎn)B則可以。方案使用算法1標(biāo)記免費(fèi)接收者。首先，計(jì)算_（R）各個(gè)節(jié)點(diǎn)的標(biāo)記c和f，然后選擇f/c最小的節(jié)點(diǎn)，如果該節(jié)點(diǎn)的c≤1且其父節(jié)點(diǎn)有兩個(gè)孩子，則將以該節(jié)點(diǎn)為根的子樹從（R）中刪除，否則，標(biāo)記該節(jié)點(diǎn)下的撤銷用戶為免費(fèi)接收者，然后將以該節(jié)點(diǎn)為根的子樹從（R）中刪除，并累計(jì)免費(fèi)接收者數(shù)量f。持續(xù)上述操作，直至免費(fèi)接收者數(shù)量達(dá)到fr=FRratio*|R|。
允許免費(fèi)接收者的完全子樹方案的初始化和解密算法與完全子樹方案完全相同。廣播算法，增加了若干步驟，具體描述如下：
廣播算法：給定撤銷用戶集合R，廣播中心設(shè)置FRratio，運(yùn)行算法1產(chǎn)生免費(fèi)接收者集合F，將F中的用戶標(biāo)記為授權(quán)用戶，即R←R\F。隨后的步驟，與完全子樹方法完全相同。
3、存儲(chǔ)和通信代價(jià)分析
方案基于完全子樹方法，用戶端的密鑰量為O（log（n））。方案的通信量低于完全子樹方案，因?yàn)樗惴?保證引入新的免費(fèi)接收者一定能降低通信量，實(shí)際效果見實(shí)驗(yàn)評(píng)估。通信量的大小可以通過參數(shù)FRratio調(diào)節(jié)。
4、安全性分析
本方案可以暫時(shí)視那些免費(fèi)接收者為授權(quán)用戶，所以本方案的安全性可以等同于完全子樹方案的安全，即完全抗串謀，且是信息論安全的。
方案中免費(fèi)接收者并不是隨機(jī)選擇的（盡管在算法1的步驟5，當(dāng)有若干個(gè)節(jié)點(diǎn)同時(shí)取得最小值時(shí)，可以引入隨機(jī)化），在撤銷用戶集合R相對(duì)固定的情況下，某些用戶可能總能成為免費(fèi)接收者，他們就會(huì)傾向于不付費(fèi)，而帶來損失。當(dāng)撤銷用戶集合R劇烈變化時(shí)，用戶難以預(yù)測自己是否為免費(fèi)接收者，所以方案更適合撤銷用戶集合R劇烈變化的應(yīng)用，比如視頻點(diǎn)播服務(wù)。
5、實(shí)驗(yàn)評(píng)估
圖3顯示了當(dāng)系統(tǒng)用戶總數(shù)n=65536，不同撤銷用戶數(shù)量，完全子樹方案和本方案通信量的比較。隨著撤銷用戶數(shù)量的逐漸增加，完全子樹方案的通信量迅速增加。在FRratio=0.05的條件下，本方案通信量明顯低于完全子樹方案，且隨著撤銷用戶數(shù)量的增加，這種優(yōu)勢就越明顯。
圖4 顯示了當(dāng)系統(tǒng)總?cè)藬?shù)n=65536，撤銷用戶數(shù)量r=3276時(shí)，允許不同數(shù)量免費(fèi)接收者通信量的比較。隨著FRratio的逐漸增大，系統(tǒng)地通信量明顯降低。
由實(shí)驗(yàn)結(jié)果可以看出，允許免費(fèi)接收者的完全子樹方案在撤銷用戶數(shù)量較大時(shí)（撤消用戶數(shù)量占系統(tǒng)總?cè)藬?shù)20%-50%）有較大的優(yōu)勢，因此適用于撤銷用戶集合較大的應(yīng)用。
二、 結(jié)論
本文給出了一個(gè)有效的廣播加密方案，并能夠在允許的免費(fèi)接收者數(shù)量和通信量等其他性能參數(shù)之間做出平衡。本方案適用無狀態(tài)接收者，并且在撤銷用戶較大時(shí)，在通信量上比完全子樹方案有顯著優(yōu)勢。
小知識(shí)之Steiner樹
Steiner樹是總代價(jià)最小的分布樹，它使連接特定圖（graph）中的特定組成員所需的鏈路數(shù)最少。若考慮資源總量被大量的組使用的情況，那么使用資源較少最終就會(huì)減少產(chǎn)生擁塞的風(fēng)險(xiǎn)。Steiner樹相當(dāng)不穩(wěn)定，樹的形狀隨組中成員關(guān)系的改變而改變，且對(duì)大型網(wǎng)絡(luò)缺少通用的解決方案。所以Steiner樹只是一種理論模型，而非實(shí)用工具。目前，出現(xiàn)了許多Steiner樹的次優(yōu)啟發(fā)式生成算法。
