New scheme of dynamic traitor tracing against the immediate rebroadcast attack

SU Jia-jun(蘇加軍), WANG Xin-mei(王新梅)

(State Key Laboratory of Integrated Service Network, Xidian University, Xi’an 710071, China)

?

New scheme of dynamic traitor tracing against the immediate rebroadcast attack

SU Jia-jun(蘇加軍), WANG Xin-mei(王新梅)

(State Key Laboratory of Integrated Service Network, Xidian University, Xi’an 710071, China)

Traitor tracing schemes are introduced to combat the piracy scenarios. The notation of dynamic traitor tracing is proposed by Fiat and Tassa, which fights against rebroadcast of decrypted content. In this paper, using the idea of searching user address level by level, a new dynamic traitor tracing scheme based on a multilevel structure of user set is constructed. The scheme proposed can efficiently combat with the immediate rebroadcast attack, and possesses lower tracing complexity. Importantly, the tracing scheme can be applicable to systems with different sizes of subscriber sets.

traitor tracing; copyright protection; rebroadcast attack; watermarking

In a broadcast encryption system[1], the data suppliers (DS) have to face two typical threats of collusion key attack and rebroadcast attack. Traitor tracing schemes against the attacks are efficient to trace and identify the traitors.

In 1994, Chor et al.[2]introduced the notion of traitor tracing to protect the decryption keys in the broadcast encryption. A new scheme of cryptography with one encryption key and multiple distinct decryption keys was designed to achieve the property that no one can compute a new decryption key from a given set of keys. In 1998, Kurosawa et al.[3]proposed a new asymmetry schemes using linear codes, and Naor et al.[4]constructed some new schemes called threshold traitor tracing schemes. In 1999, an efficient public key traitor tracing scheme[5]was presented, and the new public key scheme using RSA[6]was constructed in 2004.

All the above schemes can fight against the collusion key attack, but are not effective for the rebroadcast attack. Using fingerprinting technology[7-8], the schemes can trace the traitors of the redistribution attack.

In 1999, Fiat and Tassa introduced the notation of dynamic traitor tracing and constructed some different schemes based on the watermarking assumption[9]. Using the real-time feedback channel of system, Fiat and Tassa constructed three different schemes called Fiat-Tassa (FT) schemes which can easily fight against rebroadcast attack. In 2000, Safavi-Naini et al. presented an improved dynamic traitor tracing scheme called sequential traitor tracing scheme[10].

In this paper, based on the system model with the real-time feedback channel and the idea of searching the user address level by level, a new dynamic traitor tracing scheme with lower tracing complexity is proposed to against rebroadcast attacks.

1 FT schemes

1.1 Watermarking assumption

Watermark is a copyright notice embedded into the original message by an embedding algorithm. Digital watermarking is an efficient measure to protect data suppliers against the redistribution attack. Recently, digital watermarking technique has become a new focus in the field of security of media information and an important branch of information hiding theory. Watermarking technique shows the property of sensitive message by embedding the watermark into the original message.

A watermark has many different forms. It may be a segment of text, a piece of image or a serial number, and so on. Usually if a watermark is a serial number, it is called a fingerprint.There are many watermark embedding algorithms, among which the NEC algorithm[8]proposed by Cox et al. is most famous.

There are two important properties for watermarking as follows:

①Robustness. Watermark embedded into the original data should be able to resist on the usual signal processes, such as coding and transformation and not been removed by the subscriber.

②Hiding. Subscribers shouldn’t be able to confirm whether the message is marked by watermark and where the watermark is embedded if it exists.

Based on the aforementioned properties, the message marked by the watermark can be identified by the watermark as ID number. Because traitors cannot collude a new message copy with a watermark difficult to identify by DS, DS can identify the traitor by detect the watermark in the message copy redistributed. In fact, the watermarking properties are the basis of the traitor tracing schemes against the rebroadcast attack.

1.2 Model of FT schemes

The idea of FT schemes can be briefly described as follows: In each round, the algorithm divides the set of usersUinto disjoint subsetsUi(1≤i≤r), where the number of subsets is bounded by the watermarking alphabet size. Then different versions of the content are transmitted by DS to these subsets of users, one version per subset. Whenever the pirate broadcasts one to these versions, it is evidence that the corresponding subset contains a traitor. When this happens, the algorithm changes the allocation of versions to the users, thus starting a new round. Eventually the information gathered allows the algorithm to locate and disconnected all traitors. The system model of FT schemes is shown in Fig.1.

Fig.1 System model of FT schemes

1.3 Performance of FT schemes

In FT schemes, there are two interesting complexity measures called performance parameters in this paper: one measure is the time or number of rounds needed by the algorithm to trace all the traitors, which is called the tracing complexity, and another is the maximum number of different versions used which equals the maximum size of the watermarking alphabet, which is called the computation complexity or bandwidth.

Letnbe the number of all subscribers in the system andpthe number of traitors. The performance of three different FT schemes is shown in Tab.1. From Tab.1, scheme A need low bandwidth of system, but is also impractical because of the tracing complexity approximate tonp. The tracing complexity in both the scheme B and C has been decreased, but still too high for the system with large size of subscribers. The tracing complexity between two parameters should be more important with the development of broadband communication. That means, it is increasingly important for data suppliers (DS) to trace the traitors as rapidly as possible. So if the system has reasonable and enough bandwidth, how to minimize the tracing complexity is a key problem in the traitor tracing scheme. Different from small size of subscriber set in FT schemes, new scheme in this paper not only can be against the rebroadcast attack, but can satisfy the system with the large size of subscriber set.

2 New schemes

2.1 Construction of multilevel structure of subscriber set

LetUbe subscriber set, and suppose |U|=n=m2v(m>0,v>0). For specialmandv, ifn

(1)

(2)

In the (v-1)thlevel, each element is the subscriber or the prompt 0.

(3)

2.2 Watermark matrix based on the watermarking assumption

Two watermark matrixes as follows are used in the proposed scheme, which are based on the watermarking assumption.

(4)

(5)

W0is called surveillance matrix, which is used to survey all the elements in first level.W1is called tracing matrix, which is used to trace the traitors level by level.

2.3 Tracing algorithm

If DS wants to distribute the messageM, DS can splitMintoLsegments (M=M1‖M2‖…‖ML). When DS distributes the message segments marked by the watermarks , any traitor who redistributes any segment will be traced level by level. If a traitor, such as Elvis, redistributes any segment copy once, the first part of her ID can be marked by DS; if Elvis redistributes segment copies twice, the second parts of her ID can be marked; …; if Elvis redistributes segment copiesvtimes, DS can obtain the complete ID of Elvis.

SupposeIas the user set including a traitor,t(t≤L) as the serial number of message segment which DS will distribute, andk(k≤v) as the serial number of user level where a traitor has been located. And the detailed tracing algorithm is described as follows.

Step 0 SetI=?,t=1,k=1.

Step 1 DS produces 2m2copies ofMtsegment by embedding watermarks ofW0,W1, which are arranged in the following structure:

(6)

(7)

Subscribers of the setU0-Ireceive the copies of message fromW0(Mt) , and subscribers ofIreceive the copies of message fromW1(Mt).

Step 2 DS examines whether there exists a copy redistributed in the feedback channel.

①If there is no copy redistributed in the feedback channel,t=t+1, the tracing algorithm goes to Step 1.

Step 3 DS traces the ID of traitors.

②Ifk=v, DS can clearly identify the complete ID of Elvis, then disconnect Elvis from the network (DS can place prompt 0 on the position of Elvis ). And the tracing algorithm setsI=?,k=1,t=t+1, and returns to STEP1 to trace another traitor.

2.4 Key scheme

In traitor tracing schemes, the broadcast encryption is used to ensure each subscriber to get the corresponding segment copy. When DS wants to transmit the message segments to the users, DS can construct the message block consisted of the enabling block and cipher block. The cipher block is the symmetric encryption of the watermarking message segments by one secret random message key (MK). The enabling block allows the authorized users to obtain MK. The enabling block consists of the values encrypted by some or all of the keys of the base set including all personal keys of subscribers. Then each authorized user is able to compute MK by decrypting some values of enabling block using the personal keys, and obtain the exclusive message segment which is able to decrypt by the main key MK.

(8)

(9)

2.5 Performance

In above tracing algorithm, the number of tracing steps needed by tracing all the traitors is described in the following theorem.

Theorem Letpbe the number of traitors,N1the number of tracing steps needed by tracing one traitor, andNpthe number of tracing steps needed by tracing all the traitors, then

v≤N1≤p(v-1)+1

(10)

(11)

hold.

Proof During DS distributes the message segments, any traitor can be identified if he redistributes different message segmentsvtimes. If a traitor performs the simple rebroadcast attack to sequentially redistribute the message, he will be identified when he redistributes thevthsegment. In this case,N1=v,Np=pv. Ifptraitors perform collusion rebroadcast attack to obey the following rule: After a traitor has redistributed a message segment, he will not redistribute a new message segment until otherp-1 traitors redistributep-1 message segments. That means the position of allptraitors in the (v-1)thlevel will be disclosed ifptraitors have redistributedp(v-1) segments. And then any traitor will be identified if he redistributes a new segment again. In this case,N1=p(v-1)+1,Np=pv.

3 Conclusion

[1] Fiat A, Naor M. Broadcast encryption [C]∥International Crytology Conference-CRYPTO, Santa Barbara, CA, USA, 1993.

[2] Chor B, Fiat A, Naor M. Tracing traitors [C]∥International Crytology Conference-CRYPTO, Santa Barbara, CA, USA, 1994: 257-270.

[3] Kurosawa K, Desmedt Y. Optimum traitor tracing and asymmetric scheme[C]∥Theory and Application of Cryptographic Techniques-EUROCRYPT, Espoo, Finland, 1998.

[4] Naor M, Pinkas B. Threshold traitor tracing[C]∥International Crytology Conference-CRYPTO, Santa Barbara, CA, USA, 1998.

[5] Boneh D, Franklin M. An efficient public key traitor tracing scheme[C]∥International Crytology Conference-CRYPTO, Santa Barbara, CA, USA, 1999.

[6] Ma Hua, Cao Zhengwen. Traitor tracing scheme based on the encryption algorithm of RSA[J]. Journal of Xidian University, 2004, 31(4):611-613.(in Chinese)

[7] Boneh D, Shaw J. Collusion-secure Fingerprinting for Digital Data [J]. IEEE Transactions on Information Theory-TIT, 1998, 44(5):1897-1905.

[8] Cox I J, Kilian J, Leighton T, et al. A secure, robust watermark for multimedia[C]∥Information Hiding, Cambridge, U.K., 1996.

[9] Fiat A, Tassa T. Dynamic traitor tracing[C]∥International Crytology Conference-CRYPTO, Santa Barbara, CA, USA, 1999.

[10] Safavi-Naini R, Wang Yejing. Sequential traitor tracing [J]. IEEE Transactions on Information Theory, 2003, 49(5):1319-1326.

(Edited by Cai Jianying)

10.15918/j.jbit1004-0579.201524.0118

TN 918.4 Document code: A Article ID: 1004- 0579(2015)01- 0128- 05

Received 2014- 06- 17

Supported by the National Key Basic Research and Development Program (973 Program) (2012CB316103)

E-mail: jiajun.su@hotmail.com