(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 a), a) Broadcast Encryption System Using Secret Sharing and Subset Difference Methods Jae Hwan Lee a) and Jong Hwan Park a). 2001 Naor, Naor, Lotspiech Subset Difference(SD). (secret sharing) SD.,, log,. SD log,. (security loss), SD log. Complete Subtree SD. Abstract Broadcast encryption is a cryptographic primitive that allows a sender to securely broadcast a message to a set of receivers. The most influential broadcast encryption system was proposed in 2001 by Naor, Naor, Lotspiech, based on a pseudo-random generator and the Subset Difference (SD) method. In this paper, we suggest a new broadcast encryption system that is based on secret sharing and SD methods. On an efficiency aspect, our system achieves transmission cost, log storage cost, and computational cost for the number of users and the number of revoked users. Compared to log computational cost in the previous SD method, our system has the advantage that it needs only constant-sized computational cost for decryption, regardless of the number or. On a security aspect, our system can achieve tighter security reduction than the previous SD method and the gap of security loss is about log. Moreover, our result shows that it is possible to give the effect of the SD method while using an information-theoretically secure key distribution technique as in the Complete Subtree method. Keyword : broadcast encryption, subset difference, secret sharing
1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods). [1].,.. TV, pay-per-view TV, DRM(Digital Right Management), (revocation). (collusion attack)..,.. (stateless). a) ICT (Department of Computer Science, College of ICT Convergence, Sangmyung University) Corresponding Author : (Jong Hwan Park) E-mail: jhpark@smu.ac.kr Tel: +82-2-781-7589 ORCID: http://orcid.org/0000-0003-2742-6119. [B0101-14-0059, ]. 2014 () (NRF-2014R1A1A2059802). Manuscript received July 28, 2014 Revised October 16, 2014 Accepted December 1, 2014.,,. trade-off,. [2] [3][4]. 2001 Naor, Naor, Lotspiech [2] SD (Subset Difference). SD. leaf,., SD, log, log. SD (PRG: Pseudorandom generator). PRG SD ( ) [5][6][7]. [7] PRG SD,. (worst case), (average case). (worst case). PRG SD. SD
(JBE Vol. 20, No. 1, January 2015). Shamir -(Secret Sharing). -SS 1 share, 2 share.,.,. share. SD. 1). SS SD ( ), log,. 2),. log PRG, Lagrange.. ( ) 1.7..,,..,.,. [ 1]. 1. Fig. 1. User sets defined in two compared security models 1).1. 2),.
1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods), CCA1 (Chosen-ciphertext and launch-time attack) ( weak CCA1 ).. TV, (= ).. ( n ). leaf.,.,,. SD.. (security loss). Subset Cover,.. log, log 30bits. 128bits, 30bits 158bits.,,. Table 1. (computationally secure) PRG, (information-theoretically secure). security loss. Naor, Naor, Lotspiech [2] CS(Complete Subtree). CS,, log, log,.. CS, SD. 1. Table 1. Comparison between the previous scheme and our new scheme [2] log log CCA1 log weak CCA1 Subset Cover..
(JBE Vol. 20, No. 1, January 2015) traitor tracing [8][9][10]. traitor tracing,, ID., traitor tracing ID. traitor tracing. traitor tracing.. 1.,. 1....,., =. - (setup), (Encryption), (decryption) -. (1) Setup( ):,. (2) Encryption( ):,.. (3) Decryption( ):.,. 2. Subset Cover Subset Cover, disjoint. =. CoverFinding,.,. (),., Subset Cover. (1) (2) subset Subset Cover. 2.1 (Setup)..,
1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods) (PRG: Pseudo-random generator). 2.2 (Encryption) (1). (2),. (3). 2.3 (Decryption),. (1).. (2). (3). (4). 3., (collusion attack).,.,., ( ),.. (CCA1: Chosen ciphertext and launch-time attack) [2]. weak CCA1. weak CCA1 ( ). - Setup. Setup(,n) ( ). - Adversarial Action... (1).. (2),.. (3),.. - Challenge.. bit. b=1 Encrypt(, ). b=0 Encrypt(, ). - Guess.. bit b
(JBE Vol. 20, No. 1, January 2015). ad- vantage Pr. 1. weak CCA1 (negligible), weak CCA1. 4. =( ). CCA1 CCA1. CCA1 ( ). - Setup.. - Adversarial Action.. (1). (2). - Challenge.. bit. b=1. b=0. - Guess.. bit b. advantage Pr. 2. CCA1 (negligible), CCA1. 5.. CCA1 one-time (CAP: chosen-plaintext attack). 3) one- time CPA ( ). - Setup.. - Challenge.. bit. b=1. b=0. - Guess.. bit b. advantage Pr. 3) IV.
1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods) 3. one-time CPA (negligible), one-time CPA. 6. (SS: Secret Sharing) Shamir -SS. (prime), 1.,. share, share 2. Lagrange. 1 share (information-theoretically).,. bit. b=1, b=0.. bit b., Pr.. Pr Pr.. 1. Secret Sharing SD Naor, Naor, Lotspiech [2] leaf, disjoint. CoverFinding.,. root subtree. [2]. Subset Difference, [2] (PRG: Pseudo-random generator). 2. SS SD Fig. 2. Example of key assignment in PRG (SS: Se- cret Sharing) SD. SS Shamir SS 1 -SS. 2
(JBE Vol. 20, No. 1, January 2015). [ 2]., ( ). subtree root depth 1.. leaf ( ). leaf (root )., depth, leaf. root subtree 1,. leaf., [ 2] root subtree. SD... -SS,. -SS. [ 2], SD -SS.,, Lagrange.. log PRG. 2.. 1). 2) =( ). 3) (AES ) 128 (prime). 4). 5) leaf (full binary tree), 4). 1.1 (Setup) 3. leaf u Fig. 3 Key assignment corresponding to the leaf node u 4) log bit 0 1 leaf.
1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods) (1) root subtree depth 1.. (2) (1) root depth log. (3) root leaf.. (4) root. (5) subtree root (4). (6).. 128. log, 0 log log,., log. (). log log log log log log log log, log log log. V. 1.2 (Encryption),. (1). (2). (3) subtree depth,. (4) (3). (5). (6). (7) index.. (8)..,.. 1.3 (Decryption).
(JBE Vol. 20, No. 1, January 2015) (1) index. (2). (3) ( ) Lagrange. 1,. mod (4). (5)., (3). log PRG, modular. (3). 2. Secret Sharing LSD PRG. LSD (SS: Secret Sharing). log layer log ( log ) depth special LSD. -SS., subtree root special level root layer, root special level SS SD subtree root. SS LSD LSD log log. LSD, SS LSD.. Halevy, Shamir [5] LSD(Layered Subset Difference) log log.,, leaf root, disjoint.,. 4. =( ) CCA1, one- time CPA. weak CCA1. weak CCA1, CCA1, one-time CPA
1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods) Subset Cover,. ) weak CCA1. =( ) CCA1 one-time CPA..,.. Pr. weak CCA1.. advantage (negligible). Claim 1. Pr Pr ) weak CCA1. setup.. (.) root subtree leaf. 1), ( ).,. 2), ()., ( )., ( ).,.,
(JBE Vol. 20, No. 1, January 2015). ( ) (statistically identical). 5) (),. weak CCA1.,... 1.,.. advantage 0. (II. 6 ) Claim 2. Pr Pr ) weak CCA1. setup. CCA1. 1), ( ).,.., (abort). 2), (). (), ( ). ( ).,...., 5) (independently).
1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods). (abort), CCA1. abort. Pr Pr. Claim 3. Pr Pr ) Claim 1....,.. one-time CPA Claim 1, Claim 2, Claim 3 Claim 4, Claim 5, Claim 6. Claim 4. Pr Pr (for ) Claim 5. Pr Pr (for ) Claim 6. Pr Pr (for ) Claim 7. Pr Pr ) weak CCA1. setup. one-time CPA. ( ) ().,.,..... Pr Pr Pr Pr Pr Pr Pr Pr, 4. Pr Pr Pr Pr Pr Pr 4 SS LSD. special layer local layer..
(JBE Vol. 20, No. 1, January 2015). SD(LSD) -SS SD, LSD. SS SD, SS LSD. 1. SD(LSD) PRG, -SS. (security loss) SD,. Subset Cover,. SD. log log., SD 25bits. 128bits, SD 128+25= 153bits., SD(LSD) CCA1, ( ) weak CCA1. CCA1, weak CCA1. 2. 1), 2), 3)., ( ). Table 4 CS, PRG SD [2], LSD [5] SS SD, LSD. 2.1. [ ] (header).,. SD (LSD) 4. Table 4. Performance comparison to the previous PRG-based SD and LSD methods CS [2] log log log SD [2] log log log LSD [5] log log log log log log log
1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods), ( ). index SD (LSD). index 1), 2).,., index.. SD(LSD) index. leaf, log bits., index log bits. SD index log bits. ( ). AES 128bits. SD 128bits log bits. 128bits 128bits log bits. LSD CS log Table 4.,. CS 12451840bits, SD 1572672bits, LSD 3145344bits, 2621120bits, 5242240bits. CS, SD (LSD) ( ). 2.2 SD 128bits, 128bits.. LSD log. ( )... setup. root index,. bits,.,. 4... 2.3 SD, LSD
(JBE Vol. 20, No. 1, January 2015) log PRG, Lagrange -SS.. CS. Table 4 CS. SD ( subtree ), ( subtree ). SD ( ).. (PRG) SD, (Secret Sharing) SD., SD. ( ) CS. ( ). SD 1.7. Layered SD.., -ary. (References) [1] A. Fiat and M. Naor, "Broadcast encryption," Proceedings of the CRYPTO'93, volume 773 of LNCS, pp. 480-491, Aug. 1993. [2] D. Naor, M. Naor and J. Lotspiech, "Revocation and tracing schemes for stateless receivers," Proceedings of the CRYPTO 2001, vol. 2139 of LNCS, pp. 41-62, Feb. 2001. [3] Y. Dodis and N. Fazio, "Public key broadcast encryption for stateless receivers," Proceedings of the Digital Rights Management Workshop, vol. 2696 of Lecture Notes in Computer Science, pp. 61-80, 2002. [4] D. Boneh, C. Gentry and B. Waters, "Collusion resistant broadcast encryption with short ciphertexts and private keys," Proceedings of the CRYPTO 2005, vol. 3621 of LNCS, pp. 258-275, Aug.2005. [5] D. Halevy and A. Shamir, "The LSD broadcast encryption scheme," Proceedings of the CRYPTO 2002, vol. 2442 of LNCS, pp. 47-60, Aug. 2002. [6] 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. 3152 of LNCS, pp. 511-527, Aug. 2004. [7] S. Bhattacherjee and P. Sarkar, Tree based symmetric key broadcast encryption, IACR Cryptology eprint Archive, Report 2013/786, 2013. [8] B. Chor, A. Fiat, and M. Naor, "Tracing traitors," Proceedings of the CRYPTO'94, vol. 839 of LNCS, pp. 257-270, Aug. 1994. [9] 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. 2894 of LNCS, pp. 359-373, Nov/Dec. 2003. [10] D. Boneh and B. Waters, "A fully collusion resistant broadcast, trace, and revoke system," Proceedings of the ACM CCS 06, pp. 211-220, Oct/Nov. 2006.
이재환 외 인 비밀분산 기법과 기법을 이용한 브로드캐스트 암호시스템 1 : Subset Difference (Jae Hwan Lee et al. : Broadcast Encryption System Using Secret Sharing and Subset Difference Methods) 저자소개 이재환 년 월 현재 상명대학교 컴퓨터과학과 학사과정 주관심분야 브로드캐스트 암호 전자서명 등 - 2009 3 ~ : - ORCID : http://orcid.org/0000-0001-5580-416x :, 박종환 - 년 2월 : 고려대학교 이과대학 수학과 (학사) 년 2월 : 고려대학교 정보보호대학원 정보보호학과 (석사) 년 8월 : 고려대학교 정보경영공학전문대학원 정보보호학과 (박사) 년 6월 ~ 2011년 5월 : 경희대학교(국제) 응용과학대학 학술연구교수 년 6월 ~ 2013년 8월 : 고려대학교 BK21정보보호사업단 연구교수 년 9월 ~ 현재 : 상명대학교 컴퓨터과학과 조교수 : http://orcid.org/0000-0003-2742-6119 주관심분야 : 인증암호, ID-based 암호, 브로드캐스트 암호, 암호프로토콜 등 1999 2004 2008 2009 2011 2013 ORCID 109