(JBE Vol. 20, No. 4, July 2015) (Regular Paper) 20 4, (JBE Vol. 20, No. 4, July 2015) ISSN

Size: px

Start display at page:

Download "(JBE Vol. 20, No. 4, July 2015) (Regular Paper) 20 4, (JBE Vol. 20, No. 4, July 2015) ISSN"

인혜 저
2 years ago
Views:

1 (JBE Vol. 20, No. 4, July 2015) (Regular Paper) 20 4, (JBE Vol. 20, No. 4, July 2015) ISSN (Online) ISSN (Print) 2-Subset Difference a), a) 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method Jae Hwan Lee a) and Jong Hwan Park a). Subset Difference(SD), (PRG: Pseudo-Random Generator) (SS: Secret Sharing). 2-SD SD. 2-SD SD. PRG SS 2-SD Jae Hwan Lee[9] SS SD SS 2-SD. SS SD 25%. 2-SD. Abstract Broadcast encryption system is a cryptographic primitive that enables a sender to broadcast a message to a set of receivers in a secure channel. Out of previous proposed broadcast encryption systems, the most effective is the one that uses the Subset Difference(SD) method in a binary tree structure. The SD method has been realized by two underlying approaches: Pseudo-Random Generator(PRG) and Secret Sharing(SS). 2-SD method is the generalized version of the SD method by which two subsets of revoked receivers can be dealt with by one subset (in an SD-based broadcast encryption system). The primary advantage of the 2-SD method is to further reduce the size of transmission overhead, compared to the SD method. Until now, however, there is no known broadcast encryption system that is based on such a 2-SD technique using either PRG or SS basis. In this paper, we suggest a new 2-SD broadcast encryption system using the SS-based technique that was suggested by Jae Hwan Lee et al. in 2014[9]. The new system can reduce the size of ciphertext by 25% of the one in the previous SS-based broadcast encryption system. Also, on a theoretical note, ours is the first 2-SD broadcast encryption system that is provably secure. Keyword : broadcast encryption, subset difference, secret sharing a) ICT (Department of Computer Science, College of ICT Convergence, Sangmyung University) Corresponding Author : (Jong Hwan Park) jhpark@smu.ac.kr Tel: ORCID: () (NRF-2014R1A1A ). Manuscript received April 14, 2015; revised June 24, 2015; accepted June 24, 2015.

2 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method). [1].,. TV, PPV (pay-per-view TV), DRM(Digital Right Management).,,., ( ~ ).. ( ) [2] [3][4][5] Naor, Naor, Lotspiech [2] SD(Subset Difference) ( ).,, log, log. SD Subset (PRG: Pseudo-random generator). PRG trade-off [6][7][8]. [9] Shamir -(Secret Sharing) SD ( ). PRG (security loss),. SD PRG SD 2-SD Fig. 1. Subset representation in SD(left) and 2-SD(right) methods SD [ 1]. root subtree root subtree. [ 1]. root subtree root subtree. 2-SD subtree SD [10] Naor 2-SD. 2-SD 1/ [11] 2-SD (collusion attack). Bhattacherjee [8] 2-SD,

3 (JBE Vol. 20, No. 4, July 2015) PRG SD. [8] 2-SD. 2-SD ( ) [8]. [8] worst case. 2-SD. [9] 2-SD. 2-SD ( 2- ) - -, -. 2-, log,., 1/4.., 1., 2- Table 1. Comparison between the previous, schemes and our new 2- scheme [2] log log CCA1 [9] log 2- log weak CCA1 weak CCA1 Subset Cover,,, setup, weak CCA1 : [9] =.,, : : 2- = 1 : 1.7 : [ 1],, 2-. PRG 2-SD.. 1.,.. 1..,. =. - (setup), (Encryption), (decryption) Setup( ):,. 2. Encryption( ):,.. 3. Decryption( ):.,.

4 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method) 2. Subset Cover Subset Cover, disjoint. =. CoverFinding,.,. (),., Subset Cover subset Subset Cover. 2.1 (Setup)..,. 2.2 (Encryption) , (Decryption), [9], (weak CCA1). (CCA1: Chosen ciphertext and launch-time attack) [2]., (collusion attack).,.,

5 (JBE Vol. 20, No. 4, July 2015) weak CCA1 CCA1. ( ),.. weak CCA1 ( ). - Setup. Setup(,n) ( ). - Adversarial Action... (1).. (2),.. (3),.. - Challenge.. bit. b=1 Encrypt(, ). b=0 Encrypt(, ). 1. weak CCA1 (negligible), weak CCA1. 4. =( ). CCA1 CCA1. CCA1 ( ). - Setup.. - Adversarial Action.. (1). (2). - Challenge.. bit. b=1. b=0. - Guess.. - Guess.. bit b. advantage Pr. bit b. advantage Pr.

6 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method) 2. CCA1 (negligible), CCA CCA1 one-time (CAP: chosen-plaintext attack). one-time CPA ( ). - Setup.. - Challenge.. bit. b=1. b=0. - Guess.. bit b. advantage Pr. 3. one-time CPA (ne- gligible), one- time CPA. 6. Shamir (SS: Secret Sharing) Shamir -SS -SS. (prime). -SS, 1.,. share, share 2. Lagrange. -SS 2.,. share 3, 2 share.. bit. -SS, b=1, b=0.. bit b. A. Pr.. Pr Pr -SS,.,,,. Pr.. Pr Pr

7 (JBE Vol. 20, No. 4, July 2015). Secret Sharing 2-SD 1. : 2 Secret Sharing 2. SS 2-SD Subset Fig. 2. Subset form in 2- leaf. Naor, Naor, Lotspiech [2] SD(Subset Difference) subtree root. 2-SD root subtree. [ 2], root root. 2-SD ( ), SD. 2-SD SD, 2-SD. SD (PRG: Pseudo-random generator) (SS: Secret Sharing). SD, PRG root PRG, SS root depth -SS. 2-SD. Bhattacherjee [8] PRG 2-SD, 3 ( root ). SS 2-SD. [9] 2-SD Coverfinding. 2-,,, log,., log,,. (worst case) 2- bits, bits, 2-25% SS. [ 2] root subtree.. 1), 2) root subtree, root subtree.. 1)

8 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method), 2. [ 2],..,.. ( ),,. 1 -SS. root depth -SS, 2- ( ) depth -SS. depth ( -SS). -SS, 2.,. 2-, Coverfinding disjoint Coverfinding. Coverfinding disjoint. Coverfind- ing,. root subtree ( ) ( ).. 2). 1), ), ) 3) 2- Coverfinding ( ) ( )... Coverfinding root leaf, Steiner Tree, root disjoint ), root. 2), Coverfinding. 3) setup.

(JBE Vol. 20, No. 4, July 2015) 2.1 2- Coverfinding let let let while( ) { Find two revoked node, in such that the least-common-ancestor of, does not con tain any other revoked node.

9 (JBE Vol. 20, No. 4, July 2015) Coverfinding let let let while( ) { Find two revoked node, in such that the least-common-ancestor of, does not con tain any other revoked node. 2- if and then else if and then else if and then set Remove nodes that are descendants of } return 2.2 Coverfinding Coverfinding while. 1. root. root while root root. while. worst case 1,. 3. Secret-sharing 2-SD Fig. 3. Example of key assignment in ). 2) =( ). 3) (AES ) 128 (prime). 4). 5) leaf (full binary tree),. 1.1 (Setup) 1. root subtree depth 1..

10 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method) 2. 1 root depth log. deg deg 6-8. deg deg 3. root subtree subtree depth subtree depth 2.,. 2 leaf depth. 1 III.2 2. [ 3] depth 4 root subtree root depth log. 5. root leaf SS deg. 7. -SS deg. 8. deg deg. 9. subtree root 10. -SS deg deg deg deg -SS deg deg deg deg deg deg.., deg log, 0 log log,. deg log, 0 log log,. log log log, log. 1.2 (Encryption), Coverfinding. 3. subtree depth,

11 (JBE Vol. 20, No. 4, July 2015) (6) index.. 7. (5). 8. subtree depth depth, 2, ,. 11. index deg deg., Coverfinding. 2- Coverfinding., (Decryption). deg deg 1. deg index. 5. deg deg

12 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method) ( ) Lagrange. 1,. mod deg index , ( ) Lagrange. 2,,. mod , modular =( ) CCA1, one-time CPA. weak CCA1. weak CCA1, CCA1, one-time CPA, 2-SD setup. ) weak CCA1. =( ) CCA1 one-time CPA

13 (JBE Vol. 20, No. 4, July 2015).. 4) (11).,.. Pr. weak CCA1.. advantage (negligible). Claim 1. Pr Pr setup.. (,.) root subtree leaf. 1), ( ). ( ),. 2), (). ( ), ( ). ( ), ( ). ) weak CCA1.,. 4) [9], 1 secret sharing.

14 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method),. ( ) (statistically identical). 5) () ( ),. weak CCA1.,... (, ),. 2. advantage 0. (II. 6 ) Claim 2. Pr Pr ) weak CCA1. setup. CCA1. 1), ( ). ( ),.. ( ), (abort). 2), (). (), (). ( ).,.... 5) 2-SD setup, (independently).

15 (JBE Vol. 20, No. 4, July 2015),. (abort), CCA1. abort 2-SD setup. Pr Pr. Claim 3. Pr Pr ) Claim 1., Claim 1, Claim 2, Claim 3. Claim 4, Claim 5, Claim 6. Claim 4. Pr Pr (for ) Claim 5. Pr Pr (for ),...,.. one-time CPA.... (15). Claim 6. Pr Pr (for ) Claim 7. Pr Pr ) weak CCA1. setup. one-time CPA. ( ) (). Pr Pr Pr Pr Pr Pr Pr Pr Pr Pr Pr Pr Pr Pr, 4..,. 2-SD.

16 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method) PRG(Pseudo-Random Generator) SD [2], SS(Secret Sharing) SD [9], SS(Secret Sharing) 2-SD 2-. [ 2] 1), 2), 3),, deg deg [] (header).,., 2- Coverfinding (worst case).. 1 index 1 overhead. 2- deg. (17). index. index [9].. index log bits. leaf log bits. index log bits., AES bits, 128bits. AES 128bits block 128bits. index log bits Cover- finding worst case 2- log bits bits(192KB), bits(320KB) bits(240kb). 2-, ( =80)/320 = 1/4 2. Table 2. Performance comparison to the existing methods [2] log log log [9] log log 2- log log

17 (JBE Vol. 20, No. 4, July 2015). < <2-., 320/192= /192= log.., 128bits bits(7.8KB) bits(151KB) 151/7.8= log PRG, 2- Lagrange -SS -SS... [9] - SD (Subset Difference) 2-SD. 2-SD - -, 2-SD Coverfinding. 2-SD 25%. (worst case) [9]. ( ) 2-SD. (PRG) 2-SD,. (References) [1] A. Fiat and M. Naor, "Broadcast encryption," Proceedings of the CRYPTO'93, volume 773 of LNCS, pp , Aug [2] D. Naor, M. Naor and J. Lotspiech, "Revocation and tracing schemes for stateless receivers," Proceedings of the CRYPTO 2001, vol of LNCS, pp , Feb [3] Y. Dodis and N. Fazio, "Public key broadcast encryption for stateless receivers," Proceedings of the Digital Rights Management Workshop, vol of Lecture Notes in Computer Science, pp , [4] D. Boneh, C. Gentry and B. Waters, "Collusion resistant broadcast encryption with short ciphertexts and private keys," Proceedings of the CRYPTO 2005, vol of LNCS, pp , Aug [5] ChongHee Kim, YongHo Hwang and PilJoong Lee, "An efficient public key trace and revoke scheme secure against adaptive chosen ciphertext attack," Proceedings of the ASIACRYPT 2003, vol of LNCS, pp , Nov/Dec [6] D. Halevy and A. Shamir, "The LSD broadcast encryption scheme," Proceedings of the CRYPTO 2002, vol of LNCS, pp , Aug [7] M.T. Goodrich, J.Z. Sun and R. Tamassia, "Efficient tree-based revocation in groups of low-state devices," Proceedings of the CRYPTO 2004, vol of LNCS, pp , Aug [8] S. Bhattacherjee and P. Sarkar, Tree based symmetric key broadcast

1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method) encryption, IACR Cryptology eprint Archive, Report 2013/786, 2013.

[10] Ji Yong Jang, Dae Hun Nyung, and Joo Seok Song, 2-Subset Difference scheme for broadcast encryption, Journal of the Korea Institute of Information Security & Cryptology, 16(4), pp.1-5, Aug. 2006.

18 1 : 2-Subset Difference (Jae Hwan Lee et al.: 2-Subset Difference Broadcast Encryption System Based on Secret Sharing Method) encryption, IACR Cryptology eprint Archive, Report 2013/786, [9] Jae Hwan Lee and Jong Hwan Park, Broadcast encryption system using secret sharing and subset difference methods, Journal of Broadcast Engineering, 20(1), pp , Jan [10] Ji Yong Jang, Dae Hun Nyung, and Joo Seok Song, 2-Subset Difference scheme for broadcast encryption, Journal of the Korea Institute of Information Security & Cryptology, 16(4), pp.1-5, Aug [11] Jae Hwan Lee and Jong Hwan Park, Security analysis of broadcast encryption system based on 2-subset difference method, Journal of Broadcast Engineering, 19(4), pp , July ~ : - :, : () : () : () ~ : () ~ : BK ~ : - ORCID : - :, ID-based,,

(JBE Vol. 20, No. 1, January 2015) (Regular Paper) 20 1, (JBE Vol. 20, No. 1, January 2015) ISSN 228

(JBE Vol. 20, No. 1, January 2015) (Regular Paper) 20 1, 2015 1 (JBE Vol. 20, No. 1, January 2015) http://dx.doi.org/10.5909/jbe.2015.20.1.92 ISSN 2287-9137 (Online) ISSN 1226-7953 (Print) Subset Difference