중앙집중방식의그룹키관리구조및 알고리즘개발에관한연구 2002. 07. 30. 주관연구기관 : 공주대학교 정보통신부정보통신연구진흥원 -1-
제출문 정보통신부장관귀하 본보고서를 " 중앙집중방식의그룹키관리구조및알고리즘개발에관한연구" 의최종연구개발결과보고서로제출합니다. 2002년 7월 30일 주관연구기관 : 공주대학교 세부과제책임자 : 한근희 참여연구원 : 이승민정유진 김미선 -2-
요약문 1. 제목 중앙집중방식의그룹키관리구조및알고리즘개발 2. 연구의목적및중요성 그룹키관리는멀티캐스트통신에서그룹내통신에기밀성, 송신자확인, 내용물보호등다양한정보보호서비스를제공하기위한필수적인기초기술로서화상회의와같은다자간통신에서모든통신구성원들이하나의비밀키를공유함으로서그룹내의통신내용을보호하는기술로정의될수있다. 이러한그룹키관리의어려움은멀티캐스트의응용환경에서요구되는 PFS(Perfect Forward and Backward Secrecy) 라는요구조건을충족시켜야하는과정에서발생된다. PFS는그룹내사용자중그룹을이탈하는사용자가그이후의통신내용을인지할수없어야하는것과그룹에새로이가입하는사용자가가입이전의통신내용을인지할수없어야한다는요구조건이다. 이러한 PFS 요구조건은멀티캐스트통신이회사내의중역회의또는정부부처간에이루어지는화상회의등통신내용이민감한다자간통신에응용되는기술이기때문에반드시필요한요구조건이다. -3-
PFS의요구조건을만족시키기위해서는기존의사용자가그룹을이탈하거나또는새로운사용자가그룹에참여할때마다기존에그룹내에서공유되던비밀키를새로운비밀키로교체한후모든사용자들에게전송되어야한다. 그러나, 멀티캐스트의환경에서그룹이란매우동적인환경을요구한다. 즉, 그룹키관리메카니즘은빈번한사용자의이탈및가입이발생할수있다는것을가정하여야한다. 또한새로운그룹키를사용자들에게분배할때과다한통신량을발생시켜서는안된다. 이는멀티캐스트기술자체가포함하고있는통신량의감소라는장점을상쇄시키는결과를초래하기때문이다. 그룹키관리는중앙집중적인방식과분산관리방식을고려할수있으나분산관리방식은라우터등에그룹키관리의일부를분산시키므로그룹키의안전도가라우터의신뢰도에의존하게되는단점이있다. 이는멀티캐스트를이용한케이블 TV 등그룹키를기밀성유지의목적보다는정당한사용자인지의여부를판별하기위하여사용하는응용분야에서만적합할수있을것이다. 중앙집중적인방식은분산관리방식과는달리한개의그룹키서버가모든그룹키관리를담당하는방식으로서가장강한정보보호서비스를제공할수있는구조이며선진각국에서가장활발히연구되고있는분야이다. 이러한중앙집중방식은효율적인데이터구조및알고리즘을사용함으로서가능하며주로트리(Tree) 구조를기반으로한메카니즘이사용되고있다. 이는트리구조자체가지니는명확한계층구조및구조적단순함이그룹키관리의효율성을극대화할수있기때문이다. -4-
현재까지멀티캐스트의활용은다른통신분야에비하여미약하였다. 이는기존의라우터들이멀티캐스트를지원하지못하였기때문이다. 따라서, 지금까지멀티캐스트통신은 Tunneli ng 기법을이용한 MBone을주로이용하여왔으나차세대인터넷에서는기본적으로멀티캐스트가지원되며또한최근에발전되고있는 MPLS 또한멀티캐스트를지원할것으로예상되므로향후에는멀티캐스트의활용이급속도로발전될것으로예상되고있다. 멀티캐스트는 VOD 서비스, 인터넷방송, 인터넷공동작업및인터넷화상회의등주로멀티미디어에관련되는데이터들을운반하는통신기반으로활용되므로이들데이터를실시간에처리하면서사용자들이요구하는정보보호서비스를제공하는것이멀티캐스트활용전반에걸친성공여부를가름하게될것이다. 따라서, 향후에멀티캐스트의기초기술로서필수적으로활용될그룹키관리를위한효율적인데이터구조및알고리즘개발에본연구의필요성이있다. -5-
3. 연구의내용및범위본연구에서는효율적인중앙집중방식그룹키관리메카니즘을중점적으로연구하며세부적인연구의내용및범위는다음과같다. - 기존의트리를기반으로한중앙집중방식그룹키관리메카니즘소개및분석 - 키트리를기반으로한그룹키관리효율성증대를위한타당성분석 - 사용자의가입및탈퇴동작의발생비율을감안한상태에서완전정규트리및가변트리를이용한그룹키관리효율성증대를위한알고리즘개발및분석 - 가변트리를이용한그룹키관리메카니즘효율성분석 - 사용자의가입및탈퇴동작의발생비율을감안한상태에서최적의완전정규트리및가변트리구조를생성할수있는프로그램개발 4. 연구결과본연구에서는먼저기존에개발된중앙집중방식및분산환경방식의그룹키관리모델들을소개및분석하였으며또한이들의연구진행상황을소개하였다. -6-
본연구의주된연구결과는트리구조를기반으로하는그룹키관리모델에서기존에제안된경직된트리구조를벗어나더욱유연한트리모델을개발함으로서그룹키관리에서사용자들이그룹에가입및탈퇴시발생하는키갱신메세지를최소화할수있는트리구조및이에따르는알고리즘개발에있다. 본연구에서는먼저완전이진정규트리및 Star 그래프가각각사용자의탈퇴및가입동작에대하여최적의트리구조임을증명하였으며특히사용자의가입및탈퇴발생비율에근거하여최소한의키갱신메세지를발생시키는트리구조를계산하는알고리즘이개발되었다. 또한사용자의탈퇴비율이 50% 를넘는경우트리의차수가 2 또는 3 으로구성되는트리구조에서완전정규트리및가변에서최소한의키갱신메세지가발생한다는것을증명하였다. 연구의부산물로서제안된알고리즘은자바언어로구현되었다. 5. 활용에대한건의 국내에서는아직멀티캐스트환경하에서안전한통신을위한그룹키관리에관한표준이확립되어있지않다. 그러나, 아직선진각국에서도멀티캐스트에관련된그룹키관리표준은확립되어있지않은상태이다. 따라서, 본연구의결과물은멀티캐스트환경에서키관리표준을고려할때선진각국의흐름을파악할수있으며중앙집중방식의키관리표준을확립하는데기술적인자료로서활용될수있다. -7-
단대단통신에따르는통신망의과부하를줄이기위한멀티캐스트의중요도는점차적으로증대되고있는실정이다. 그러나멀티캐스트통신에정보보호서비스를제공하기위한필수적인요소인그룹키관리알고리즘은아직초보적인연구단계에머물고있다. 따라서, 본연구의결과물은중앙집중방식에서효율적인키관리메카니즘을제공하여정보보호서비스가요구되는다양한멀티캐스트응용서비스를창출하는데활용될수있을것이다. 6. 기대효과본연구의결과물은멀티캐스트환경하에서중앙집중방식의효율적인키관리메카니즘을제시하여정보보호서비스를요구하는다양한새로운응용서비스를창출하는데활용할수있다. 또한본기술은아직국제표준으로서확립이되지않은상태이므로국제표준을확립하는데기여를할수있다. -8-
SUMMARY ( 영문요약문) 1. Title Development of Data Structure and Algorithm for the Centralized Group Key Managem ent 2. Objectives and Necessity The main objective of group key management is to provide security services such as data secrecy, recipient authorization and content protection to multicast communicatio ns by sharing a single group key among all the users involved in the multicast comm unications. The difficulty of group key management arise from the security requiremen t known as Perfect Forward and Backward Secrecy (PFS) which is strongly required b y many multicast services. PFS requires that the newly joining member must not be a ble to recognize the communication that exchanged before he joined the group and t he leaving member must not be able to recognize the communication after he leaves the multicast group. This requirement is very critical since multicast can be used for t he application services such as Tele-conferences that are communicated by between CEO members of a company or government agencies. -9-
Currently, the only solution to satisfy the requirement of PFS is to change the current group key to a new one every time a new user joins the group or an existing user le aves the group and sends this new group key to all the group members. However, m ost multicast requires very dynamic environments. In other words, we must assume th at the probability of join and leave operations can be very high. Furthermore, group k ey management must not create too much communication overhead for otherwise it w ill compromise the merit of multicast communications. Group key management can be categorized into the following two mechanisms :centr alized group key management and distributed group key management. However, since distributed group key management mechanism distributes the trust point to the routers it causes the problem that multicast members must trust routers. Hence, such mecha nisms appropriate for the multicast applications which use the group key management to ensure that the members are the legitimate members of the group such as cable T V applications. Unlike the distributed group key management centralized group key ma nagement uses only one group key server which takes all the responsibilities of the g roup key management. Hence, centralized group key management is the most secure group key management since all the members in the group communication need to tr ust a single group key server. This mechanism is developed by using efficient data st ructures and key distribution algorithms. Since tree is the one of the most efficient an d simple data structure most centralized group key management is based on the tree structures. -10-
Compare to the development of other areas of communication techniques the develop ment of multicast area is relatively slow because most existing routers do not underst and multicast traffics. Therefore, currently multicast applications uses MBone which ba sed on the tunneling technique. However, since the next generation Internet and MPL S support the multicast it is obvious that the development of multicast technique will be quite fast in the near future. VOD services, internet TV, internet collaboration and teleconference are the most pro minent multicast application services. Since these services involve large volume of val uable multimedia data it will be the most important technique that can process these data in real time and provide various security services to protect their valuable data. -11-
3. Contents and Scope This research focus on the development of efficient centralized group key managemen t based on tree structures. The detailed contents and scope of this research is as fol lows: - Introduction and analysis of the existing centralized group key management mechani sm based on tree structure. - Research on the feasibility of the development of efficient group key management based on tree structure. - Development of the efficient group key management algorithm based on full regular tree and variable degree tree according to the probability of the join and leave operati ons. - Analysis of the developed group key management algorithm. - Development of the program based on the proposed group key management algorit hms. 4. Results First of all, we introduced and analyzed the existing several centralized and distributed group key management mechanisms. We also introduced the current status of the res earch in this area. -12-
The main result of this is research is to define more flexible tree structure than the e xisting one so that the number of rekey messages generated when the users join and leaves the multicast group communication. Especially, we constructed an algorithm th at minimizes the necessary rekey messages according to the probabilities of join and leave operations. Furthermore, we have proved that if the probability of leave operatio n is more than 50% then the tree structure that composed of the nodes with degree 2 or 3 generates the least rekey messages. We also implemented the proposed algorithms with Java programming language. 5. Applications Currently, there is no internationally recognized standard for the group key manageme nt mechanism. Therefore, the result of the this research can be used to follow up the development procedure of the group key management techniques for the multicast co mmunications and may be used to determine such standards. In order to reduce the communication overhead involved in the point-to-point commu nication researchers focus on the multicast communication. However, the status of re search area on the group key management mechanism which is the key factor for the required security service for the secure multicast communication has been immature. Therefore, the result of this research may be used to provide efficient key manageme nt mechanism for the group communications so that it can create various multicast a pplication services that provide security services. -13-
6. Effect The result of this research may be used to provide efficient group key management mechanism so that it can create various new multicast application services that requir e security services. Since the international standard for the group key management ha s not be determined yet the result of this research may help to determine such stand ard. -14-
CONTENTS ( 영문목차) Chapter 1 Section 1 Section 2 Section 3 Introduction Multicast Technology Research Trend on Group Key Management Security Requirements Chapter 2 Group Key Management Algorithms Section 1 Rekey Mechanism on Star Graph 1. Join Operation 2. Leave Operation Section 2 Rekey Mechanism on Key Tree 1. User-Oriented Mode 2. Key-Oriented Mode Chapter 3 Optimization Using Full Regular Tree Chapter 4 Section 1 Section 2 Chapter 5 Optimization Using Variable Degree Tree Feasibility of the Optimization Optimization Conclusion -15-
References -16-
목 차 제 1 장서론 제 1 절 멀티캐스트기술 제 2 절 멀티캐스트의그룹키관리연구동향 제 3 절 그룹키관리메카니즘및정보보호요구사항 제 2 장그룹키관리알고리즘 제1 절 Star 그래프의키갱신메카니즘 1. 가입동작을위한키갱신메카니즘 2. 탈퇴동작을위한키갱신메카니즘제 2 절키트리의키갱신메카니즘 1. 사용자중심모드의키갱신메카니즘 2. 키중심모드의키갱신메카니즘 제 3 장완전정규트리를이용한그룹키관리알고리즘최적화 -17-
제 4 장가변트리를이용한그룹키관리알고리즘최적화 제 1 절 가변트리를이용한키트리최적화의타당성분석 제 2 절 가변트리를이용한키트리최적화 제 5 장결론 참고문헌 -18-
제 1 장. 서론 제 1 절. 멀티캐스트기술 인터넷기술이개발된지 30 여년이된지금인터넷기술은다른기술들에비하여비약적인속도로개발되어왔으며인터넷이용자수및이를이용한인터넷응용분야또한비약적으로발전되어왔다. 게다가이러한추세는향후에도지속될것이확실시되고있다. 우리가현재주로사용하고있는인터넷통신은단대단(unicast) 통신방법으로이루어진다. 단대단통신은하나의송신자와하나의수신자가통신상의짝을이루는형태로서하나의송신자가수십또는수백명의서로다른수신자들에게동일한메세지를전송하기에는매우비효율적인메카니즘이다. 이러한통신상의문제점을해결하기위하여개발된통신메카니즘이멀티캐스트(multicast) 이며차세대인터넷기술의핵심기술중하나로인식되고있다. 멀티캐스트는브로드캐스트(Broadcast) 와는다른방식의통신기술이다. 브로드캐스트는하나의송신자가동일한서브네트워크(Subnetwork) 상의모든수신자에게메세지를전송하는방식이지만멀티캐스트는복수의송신자들이복수의특정한수신자들에게메세지를전송하는방식이기때문이며따라서멀티캐스트는메세지의중복전송으로인한네트워크자원의낭비를최소화하면서화상회의등의응용분야에적합한통신기술이다. -19-
멀티캐스트의장점에도불구하고멀티캐스트의활용도가낮은것은기존의라우터 (Router) 들이멀티캐스트통신을지원하지못하기때문이다. 따라서현재인터넷에서는터널링(Tun neling) 이라는기술을이용한가상망을구축하여사용하고있으며 Mbone이가장대표적인멀티캐스트가상망이다. 터널링이란멀티캐스트를지원하는두개의라우터들사이에서멀티캐스트패킷을일반단대단 IP 패킷형태로전송하는것으로서통신로상에멀티캐스트를지원하지않는라우터들을거친다하여도문제가없다. 이렇듯멀티캐스트가네트워크레벨에서지원되지못하기때문에현재인터넷을이용한멀티캐스트서비스는응용레벨에서구현된것이며터널링에따르는네트워크상의부하가큰것이현실이다. 그러나차세대인터넷프로토콜에서는멀티캐스트를기본적으로지원하기때문에향후에는현재개발중에있는 VOD 서비스, 인터넷화상회의, 인터넷방송등대용량의동일한메세지를복수의수신자에게효율적으로전송하는응용서비스분야가활성화될것으로기대된다. 제 2 절. 멀티캐스트의그룹키관리연구동향 지금까지그룹키관리연구는 IRTF내의 SMuG(Secure Multicast) Working Group에서가장활발히진행되어왔으며최근에는 IETF내에 Msec(Multicast Security) 이라는그룹키관리및멀티캐스트의정보보호연구를담당하는 working group이결성되어 SMuG 및 RMRG (Reliable Multicast) working group 등과함께본분야의연구를주도하고있다. -20-
분산관리방식의연구는 Hardjono[5] 등에의한 Intra-domain Group key Management Pr otocol이제안되어있지만분산관리방식은그룹키관리를위한데이터구조및알고리즘의 개발보다는관련프로토콜의개발에연구가집중되는동향을보이고있다. 이는분산방식이 복수개의키관리서버들이그룹키를관리하므로효율적인데이터구조및알고리즘보다는 대량의사용자들과지역적으로효율적으로통신할수있는통신기술을추구하기때문이다. 분산관리방식의다른연구로서는 Suvo Mittra에의한 Iolus[6] 를들수있다. 본방식은확 장성을염두에두고 GSA(Group Security Agents) 라는중간단계의그룹키서버들을사용 한메카니즘이다. 분산관리방식에비하여중앙집중관리방식의가장큰특징은중앙집중방식에서는한개의 그룹키서버가모든그룹키들을관리한다는것이다. 이러한중앙집중관리방식의가장대표 적인데이터구조및알고리즘은 LKH(Logical Key Hierarchy)[2] 를들수있으며이는트 리(Tree) 를기반데이터구조로서분산관리방식에비하여매우효율적인그룹키관리메카 니즘을제시하고있다. 그러나, LKH는정적인멀티캐스트그룹을대상으로개발되었으므로 사용자의수가꾸준히증가및감소하는동적인환경에서는적용하기가부적절할수도있 다. 또한데이터구조의신축성을실현할수있는방안이제안되지않았으므로특정한수의 사용자들을포함하는경우효율성이떨어지는단점을보이고있다. 이러한종류의다른그 룹키관리방식으로서 OFT(One-way Function Tree)[7] 라는메카니즘이 Balenson 등에의 하여제안되었다. -21-
본메카니즘은해쉬함수를이용한것으로서 LKH에비하여새로운비밀키를멀티캐스트내의모든사용자들이공유하기위하여전송되는통신량을약절반으로줄일수있는메카니즘이다. OFT방식은전체적인통신량은줄일수있는반면서버의계산량은 LKH 방식보다늘어나지만효율적인해쉬함수를적용할경우커다란단점이되지는않을수도있다. 트리구조를이용한다른키관리방식으로서 Wong[1] 의키트리모델이있다. 본방식은 LKH와마찬가지로정적방식을기반으로하지만 LKH 와는달리사용자중심모드(User-oriented), 키중심모드(Key-oriented) 및그룹중심모드(Group-oriented) 등 3 가지모드로그룹키정보를구성하여사용자들에게전송할수있다. 각각의모드는나름대로의장단점을포함하지만다양한멀티캐스트응용분야에알맞은모드를선택하여사용할수있다는점은매우효율적이다. 멀티캐스트는주로멀티미디어에관련되는데이터를전송하기때문에모든작업은실시간에수행되어야한다. 따라서, 사용자의인증또한멀티캐스트에서는더욱효율적인방법을요구하게된다. 이러한연구는현재미국의버클리대학에서진행중인 TESLA(Multicast Sour ce Authentication Transform) 를들수있다. 또한차세대인터넷의 IPSec에서안전한멀티캐스트를운용하기위하여필요한 payload 들의형식을규정하는 GSAKMP[8] (Group Do main of Interpretation) 가현재internet-draft 로제안되어있다. -22-
그룹키관리에서분산관리방식은뛰어난확장성을가지는반면라우터등이그룹키관리의일부분을담당하므로정보보호서비스의안정성에서중앙집중방식에비하여현저히취약한단점을가지고있다. 따라서본연구에서는한개의그룹키서버가모든그룹키관리를담당하는중앙집중방식의그룹키관리모델을중점적으로연구한다. 제 3 절. 그룹키관리메카니즘및정보보호요구사항 멀티캐스트그룹은동적인그룹으로서기존의사용자가그룹을탈퇴할수도있으며새로운사용자가그룹에가입할수도있다. 기존의사용자가그룹을탈퇴하는것을탈퇴동작(Leave operation) 라하며새로운사용자가그룹에가입하는것을가입동작(Join operation) 이라한다. 새로운사용자 u가기존의그룹에가입동작을요청하면서버와사용자는적절한인증프로토콜을이용하여상호간의신원인증과정을거친후그룹키서버와 u 사이에만공유되는개인키를설정하게되며이러한과정을초기화과정이라한다. 그룹키서버는 u 의개인키로그룹키를암호화하여 u 에게전송함으로서가입동작은완료되며새로운사용자 u 는전송받은그룹키를이용하여멀티캐스트통신에참여할수있게된다. 기존의사용자가그룹을탈퇴하는경우서버는탈퇴하는사용자와공유되었던개인키를서버에서관리하는데이터구조에서삭제함으로서탈퇴동작이완료될수있을것이다. 그러나그룹키관리의어려움은멀티캐스트의응용환경에서요구되는 PFS(Perfect Forward and Backward Secrecy) 라는요구조건을충족시켜야하는과정에서발생된다. -23-
PFS 는그룹내사용자중그룹을이탈하는사용자( 탈퇴동작) 가그룹을이탈한이후의통신내용을인지할수없어야하는것과또한그룹에새로이가입하는사용자( 가입동작) 가가입이전의통신내용을인지할수없어야한다는요구조건이다. 이러한 PFS 요구조건을충족시킬수있는방법은기존의멀티캐스트그룹에변화가발생할때마다기존에모든사용자들사이에공유되는그룹키를새로운그룹키로대체하는것이유일한방법이다. 그룹키서버가기존에모든사용자들사이에공유되던그룹키를새로운그룹키로대체하는과정을 키갱신 이라하며이과정에서서버는사용자들에게키갱신메세지(rekey messag e) 라불리우는새로운그룹키및서브그룹키들을적절한키들로암호화한메세지를전송하여야한다. 멀티캐스트그룹내에 n 명의사용자가있는경우만일단대단통신을이용하여새로운그룹키로대체한다면이러한과정에는명백히 O(n) 개의키갱신메세지가전송된다. 만일 n 이큰수이며빈번한가입/ 탈퇴동작이발생한다면단대단통신을이용한키갱신은과도한통신량으로인하여해당응용프로그램의효율성을무용지물로만들것이다. 따라서키갱신과정에서키갱신메세지들또한멀티캐스트를이용하여그룹내사용자들에게전송되는메카니즘이필수적으로필요하며이때가장적절한데이터구조가트리(Tree) 구조이다. -24-
트리의정점들은루트(Root), 내부정점(Internal Node) 및말단정점(Leaf Node) 등 3가지종류의정점들로구성되며루트를그룹키서버, 내부정점들을서브그룹키(Subgroup Key) 그리고말단정점들을사용자들을대변하는정점들로취급한다. 특정한키갱신메카니즘을 G 라하자. 그렇다면 G 를이용한키갱신메카니즘에서 G 의효율성을측정하기위하여다음과같은파라미터들이반드시고려되어야한다. _ JMsg(G) : 한개의가입동작에따른키갱신과정에서서버가사용자들에게전송해야되는키갱신메세지갯수. 멀티캐스트메세지는한개의메세지로계산된다. _ LMsg(G) : 한개의탈퇴동작에따른키갱신과정에서서버가사용자들에게전송해야되는키갱신메세지갯수. 멀티캐스트메세지는한개의메세지로계산된다. _ JEnc(G) : 한개의가입동작에따른키갱신과정에서서버가암호화해야할메세지갯수. - LEnc(G) : 한개의탈퇴동작에따른키갱신과정에서서버가암호화해야할메세지갯수. - SubKey(G) : G 에포함된서브그룹키들의총개수. -25-
상기한 3 개효율성파라메타들을모두동시에최적화할수없는상황이있을수있다. 이러한경우멀티캐스트통신의근본목적이통신량을감소시키는것이기때문에이러한근본목적을지키기위하여키갱신메세지갯수를최소화하는방향으로그룹키관리메카니즘이개발되어야한다. 3 장및 4 장에서우리는완전정규트리(Full Regular Tree) 및가변트리 (Variable Tree) 구조들을이용하여키갱신메세지를최소화하는목적하에서키트리를이용한최적화방안이논의된다. -26-
제 2 장. 그룹키관리알고리즘 중앙집중방식의그룹키관리모델은크게정적관리모델및동적관리로나눌수있다. 정적관리모델은키관리를위한전체데이터구조가초기에완성되는형태이며동적관리모델은데이터구조가사용자의증감에비례하여변화하는모델이다. 정적모델로서는 Wong [1] 및 Wallner[2] 가제안한트리에기반한모델이가장대표적이며동적모델로서는이진트리에기반한모델을제안한 Moyer 의모델[3] 이대표적이다. 본장에서는 [1] 및 [2] 에서제안된트리를기반으로한데이터구조및그룹키관리메카니즘을분석하며 3장및 4장에서는이들모델들을기반으로그룹키관리의최적화를이룰수있는새로운데이터구조및메카니즘에대하여논의하도록한다. 본보고서에서는표준적인그래프용어들이사용되며특별히언급되지않는용어들은 [4] 의정의들을따르도록한다. Wong[1] 은효율적인그룹키관리를위한데이터구조인키그래프를다음과같이정의하였다. [ 정의 2.1] " 키그래프" 는방향성을가진사이클이없는그래프 G(directed acyclic graph) 로서사용자를대변하는 u-node 및키를대변하는 k-node 등 2 가지형태의정점들을갖는그래프이다. 모든 u-node 들은하나또는그이상의 outgoing edge 들을가질수있지만 incoming edge 를갖지않으며, k-node 들은하나또는그이상의 incoming edge를갖는다. 만일특정 k-node가 incoming edge만을갖는다면이러한 k-node를 G 의 root 라부른다. -27-
그림 2.1. Key Graph 예제 그림 2.1은 u 1 u 5 등모두 5 개의 u-node와 8 개의 k-node들로구성된키그래프의 예제이다. 본키그래프에서 k 1 5 는 root 로서모든사용자 u 1 u 5 사이에공유되는그룹키 이다. 키그래프에서 u-node는사용자들을대표하는추상적객체이며각사용자의개인키는 k-n ode 의부모정점(parent node) 에저장된다. 그림 2.1에서 k 1 k 5 들이이러한개인키들을 나타내며이들은모두그룹키서버및각사용자들의단말기에저장된다. 그림 2.1에서 k 1 k 5 및루트를제외한 k-node ( 즉내부정점인 k 12 및 k 345 ) 는서브그룹키들로서가입/ 탈퇴동작들을효율적으로수행하기위한키들로서키그래프의핵심적인역할을수행한다. k -node 의일종인그룹키(k 1-5 ) 는 G 의루트에저장된다. 루트를대표하는 k-node는그룹키서버라는물리적주체에저장되며루트를제외한서브그룹키들을대표하는물리적주체는없으며이들은모두그룹키서버에저장된다. -28-
Wong[1] 은키그래프정의에서 u-node 및 k-node를서로구분하였지만 u-node에는특정한키가설정되지않는추상적인객체이므로이들의역할이이해되는한이들을특별히따로취급할필요가없으므로여기서는 u-node 의개념을사용하지않도록한다. 따라서앞으로는키그래프내에는 k-node 들만이존재하는것을가정하도록하며사용자의개인키를저장하고있는 k-node들이 u-node 의역할을함께담당하는것으로가정한다. 즉, 그림 2.1에서 k i (1 i 5) 들이 u i (1 i 5) 의역할을동시에수행하는것이다. 또한실제적인의미에서키그래프 G가방향성을가진그래프로정의할필요는없으므로보고서의나머지에서는 G 를무방향성그래프로취급을한다. 그림 2.2의키그래프는그림 2.1의키그래프를수정된정의에따라변경한것이다. Wong[1] 은키그래프의하부그래프로서 Star 그래프및키트리들을정의하였다. 여기서정의되는 star 그래프및키트리들은 [1] 에서정의된것들과유사하지만그구조를모두트리구조로제한한것들이다. 다음정의에서 k n,m 은 n 개및 m 개의정점을가지는완전이 분그래프 (complete bipartite graph) 이다. -29-
그림 2.2. Key Graph 예제 [ 정의 2.2] Star 그래프 G=(V, E) 는 V =n+1개의정점으로구성된 K 1,,n 이다. [ 정의 2.3] 키트리 T=(V, E) 는트리로서 T의높이 (height) h는 T내에서가장긴경로의간선갯수이며 T 의차수 d 는모든정점들중가장많은자식정점을갖는정점의자식정점의개수이다. 그림 2.3은 u 1 u 8 등모두 8명의사용자를수용할수있는 Star 그래프 K 1,8 이다. k i (1 i 8) 은사용자 u i (1 i 8) 가그룹키서버와공유하는개인키이며 k 1-8 은모든사용자들이서로공유하는그룹키이다. Star 그래프의경우서브그룹키는존재하지않는다. 그림 2.4 또한 u 1 u 8 까지모두 8 명의사용자를수용할수있는키트리모델이다. Star 그래프와마찬가지로 k i (1 i 8) 은사용자 u i (1 i 8) 가그룹키서버와공유하는개인키이며 k 1-8 은모든사용자들이서로공유하는그룹키이다. 또한 {k 12, k 34, k 56, k 78, k 1-4, k 5-8} 들은서브그룹키로서이들의역할은추후에자세히설명된다. -30-
그림 2.3 Star 그래프 K 1,8 예제 그림 2.4 키트리예제 -31-
키트리모델에서사용자 u 가그룹키서버 S 에게가입또는탈퇴동작을요청하였다하자. 가입동작의경우서버 S 는사용자 u에대한적절한신원인증과정을거친후 S 와 u 사이에만공유되는개인키를설정하게된다. 이러한개인키의설정은 IKE[9] 등을이용하여안전하게설정될수있을것이다. 개인키설정이완료된후 S 는 u 에게새로이생성된그룹키를전달하여야하며 PFS를위하여 u로부터트리의루트에이르는경로상에위치한모든서브그룹키들을새로운키로대체한후이들을필요로하는모든사용자들에게전달하여야한다. 탈퇴동작의경우에도 PFS를위하여새로운그룹키를생성한후이를남아있는모든사용자들에전달하여야하며또한탈퇴하는사용자 u 로부터루트에이르는경로상에위치한모든서브그룹키들을새로운키로대체한후이들을필요로하는모든사용자들에게전달하여야한다. 1절및 2절에서는 Star 그래프및키트리에서 PFS 요구조건을만족시키면서사용자들의가입및탈퇴동작이진행되는과정을분석하도록한다. 제 1 절. Star 그래프의키갱신메카니즘 1. 가입동작을위한키갱신메카니즘새로운사용자 u 가기존의 star 그래프에가입동작을요청한다고하자. 서버 S 는 u 를위하여새로운 k-node k u 를생성한후이를루트에연결시킨다. S 는또한새로운그룹키를생성한후이를 u 와공유하고있는개인키로암호화한후 u 에게전달한다. 끝으로 S 는기존의그룹키로새로운그룹키를암호화한후이를모든기존의사용자들에게전달한다. 이러한프로토콜을형식화하기위하여우리는 [1] 에서정의된다음정의를사용하도록한다. -32-
[ 정의 2.4] [1] S u i :m 서버 S 가사용자 u i 에게메세지 m 을단대단통신으로전송하는것이다. [2] S {u 1,u 2,..., u n}:m 서버 S 가사용자집합 {u 1, u 2,..., u n } 에게메세지 m 을멀티캐스트를이용하여전송하는것이다. [3] {k i}k j 키 k i 를키k j 로암호화한메세지이다. 그림 2.5 는 star 그래프에서의가입동작을위한키갱신메카니즘의과정을보여주는예제로서 k 1, k 2, k 3 로대변되는 3 명의사용자로구성된기존의 star 그래프에 k 4 로대변되는새로운사용자를가입시키는과정을보여주고있다. PFS를위하여새로운사용자가가입하기이전에사용되었던그룹키 k 123 은반드시새로운그룹키 k 1234 로대체되어야하며 k 1234 는새로운사용자및모든기존의사용자들에게암호화된상태로전송되어야만한다. 그림 2.5 의 (1) 은새로운사용자 u 가 join 하기이전의 star 그래프를나타내며 (2) 는 u 가 가입한이후의 star 그래프를보여준다. -33-
이때서버 S 는다음과같은메세지들을각사용자들에게전송한다. 그림 2.5 Star 그래프에서의가입동작 k 123 은 u 가 join 하기이전에 star 그래프에서모든사용자들사이에공유되었던그룹키이며 k 1234 는 u 가가입함으로서 PFS 를위하여새로이생성된그룹키이다. 상기한메세지들이사용자들에게전달된이후모든사용자들은새로이전송된그룹키 k 1234 를이용하여그룹내에서송수신되는메세지들을암복호화할수있게된다. 특히, 새로이가입한사용자는자신이가입하기이전에공유되었던그룹키 k 123 에대한정보가없기때문에비록이전의메세지들을특정한방법을통해서수신및저장하였다하여도이들은모두 k 123 으로암호화되었기때문에이들메세지들을복호화할수없다. -34-
가입동작에서서버는기존의사용자들에게한개의메세지를그리고새로운사용자에게또 한한개의메세지를전송하여야한다. 따라서, n 명의사용자를포함한 Star 그래프 G에서 가입동작의경우 JMsg(G) = JEnc(G) = 2 이다. Star 그래프에서는서브그룹키가사용되 지않는다. 상기한분석처럼 star 그래프는가입동작에서 O(1) 의 JMsg(G) 및 JEnc(G) 를요구하기때 문에매우효율적이다. 이는가입동작이전에모든사용자들이공유하였던그룹키 k 123 을이 용하어새로이생성된그룹키 k 1234 를암호화할수있기때문이며또한새로이가입하는사 용자는 k 123 에대한정보가없기때문에비록다른방법으로메세지 {k 1234 }k 123 를획득하였 다하여도이를복호화할수없기때문에 PFS 가확실히보장되는것이다. 특히우리는 3장에서 star 그래프는가입동작을위한최적의데이터구조라는것을증명할 것이다. 그러나, 다음에보듯이탈퇴동작의경우 star 그래프는매우비효율적이다. 2. 탈퇴동작을위한키갱신메카니즘그림 2.6는 u 1 u 4 등 4명의사용자로구성된 star 그래프에서 u 4 가탈퇴하는과정을보여주며그룹키서버는다음과메세지들을그룹내사용자들에게전송한다. -35-
그림 2.6 Star 그래프에서의탈퇴동작 PFS를위하여서버는각사용자들의개인키를이용하여새로운그룹키 k 123 을각각따로암호화한후전송하여야하며따라서탈퇴동작이전에 n 명의사용자가 star 그래프로구성되었다면한명의사용자를탈퇴시키기위하여 LMsg(G)=LEnc(G)=n-1 이요구된다. 만일 n이큰수이고탈퇴동작의발생빈도수가크다면 star 그래프의탈퇴동작은가입동작에비하여매우비효율적인메카니즘이다. n 명의사용자를수용하는 Star 그래프 G 에서의가입/ 탈퇴동작의효율성을정리하면다음표와같다. 표 2.1. Star 그래프의효율성 가입동작 탈퇴동작 JMsg(G)/LMsg(G) 2 n -1 JEnc(G)/LEnc(G) 2 n -1 Star 그래프의탈퇴동작의비효율성을보완할수있는데이터구조로서키트리가사용될수있으며키트리는 star 그래프와는달리서브그룹키들을사용한다. -36-
제 2 절. 키트리의키갱신메카니즘 Wong[1] 은키트리에서키갱신을위하여사용자중심모드(user-oriented), 키중심모드(ke y-oriented) 및그룹중심모드(group-oriented) 모드등 3 가지서로다른모드들을정의하였다. 이들은키갱신메세지가어떠한형태로조합되어사용자에게전송되는가에따라구분되며각모드들은나름대로의효율성을보여준다. 여기에서는이들중가장중요한사용자중심및키중심모드를분석하기로한다. 다음 2 개의그림은키트리에서가입/ 탈퇴동작을보여주고있다. 그림 2.7의키트리는그림 2.7의키트리로부터 u 9 이가입한것이며그림 2.8의키트리는그림 2.7의키트리로부터 u 9 이탈퇴한상태를보여준다. 그림 2.7 키트리에서가입탈퇴동작 / -37-
그림 2.8 키트리에서가입/ 탈퇴동작 1. 사용자중심모드의키갱신메카니즘본모드의특징은그룹키서버는각사용자에게정확히필요한정보만을사용자와공유되어있는키로암호화하여전송한다는것이다. 예를들어서그림 2.8의키트리에 u 9 이가입하기위하여서버는다음과같은암호화된메세지들을해당사용자들에게전송한다. 여기서 k l m 은 k m 을대체하기위하여새로생성된키를나타낸다. -38-
키트리의높이를 h 라하자. 사용자중심모드에서가입동작의경우모두 h 개의키갱신메세지가필요하다. 루트의레벨(level) 을 1로정의하면그룹키는레벨 1에위치하며서브그룹키들은레벨 2 부터레벨(h-1) 까지에위치하게된다. 사용자중심모드에서는레벨 i (1 i h - 1) 에서 i 개의키들을암호화하여야하며또한새로이가입하는사용자에게전달할메세지를생성하기위하여 (h-2) 개의키들이암호화되므로 JEnc(T) 는다음과같다. 사용자중심모드에서탈퇴동작은가입동작과동일한특징을가지고있다. 즉, 사용자들은자신들이반드시필요로하는키들만을전송받는다는것이다. 그림 2.7의키트리에서 u 9 이탈퇴하는경우그룹키서버 S 는다음과같은메세지들을남아있는사용자들에게전송한다. 본모드에서새로이생성된그룹키및서브그룹키들은루트부터시작해서레벨이 (h - 1) 에이를때까지 (d -1) 개씩새로운메세지에포함되어전송된다. 따라서, -39-
이며 LEnc(T) 는다음과같다. 2. 키중심모드의키갱신메카니즘본모드는기본적으로각각의키들은독립적으로암호화가된다는것이다. 그러나효율성을위하여사용자는사용자중심모드와는달리한개이상의키갱신메세지를수신할수도있다. 그림 2.8의키트리에 u 9 이새로이가입한다고하자. 서버는다음과같은키갱신메세지들을생성하여해당사용자들에게전송한다. 본모드를이용하면새로운그룹키및서브그룹키들이 2번씩암호화되어전송되므로총 2 (h-1) 개의키갱신메세지가필요하게되며마찬가지로JEnc(T) 도2(h-1) 가요구된다. -40-
그렇다면본모드는사용자중심모드와비교하여 JEnc(T) 는 ( ) 로부터 2(h-1) 로 현저히줄어들지만요구되는키갱신메세지는 h개로부터 2(h-1) 로오히려증가하게된다. 그러나, 다음과같이동일한사용자에게전송되는키갱신메세지를한개의메세지로통합하면서새로이가입하는사용자에게전송되는키들을하나의메세지로통합하여암호화하면본모드에서요구되는키갱신메세지를모두h 개로줄일수있다. 본모드를사용하여도 JEnc(T) 는계속 2(h-1) 이요구된다. 이는상기한예제에서도알수있듯이동일한키로암호화된키들이중복되게사용될수있기때문이다. 예를들어, {k 1 a}k a은 {u 1,..., u 6 }, 및 {u 7, u 8 } 에게반복적으로전달되고있기때문에 {k 1 a}k a 는한번만생성되면재전송이될수있다. 또한키갱신메세지는총 h 개가요구되는데이는기존의사용자들을위하여새로운그룹키및서브그룹키들이한번씩만암호화되어전송되며 ( 따라서, h-1 개의키갱신메세지), 새로이가입하는사용자에게는이러한 h-1 개의키들을하나의메세지로묶은후새로이가입하는사용자의개인키로암호화하여전송하기때문이다. 따라서, 키중심모드는가입동작에서사용자중심모드보다훨씬효율적이라할수있다. -41-
키중심모드의탈퇴동작또한가입동작과동일한개념을갖는다. 예를들어그림 2.7의키트리로부터 u 9 이그룹을탈퇴하게되면서버 S 는다음과같은키갱신메세지들을그룹에남아있는사용자들에게전송하게된다. 본모드에서키들이암호화되는과정은이전것들과는다소상이하다. 예를들어, 상기한프로토콜에서사용자 u 7 는암호문 {k l z}k 7 을자신의개인키 k 7 을복호화하여 k l z를얻은후에 {k l a}k l z 를복호화할수있으며이것은 u 8 도마찬가지이다. 이러한방법을채택하는이유는 LEnc(T) 를최소화하기위함이다. 예를들어서, 예제에서서버에의하여 u 7 및 u 8 에게전송되는 {k l a}k l z는동일하기때문에lenc(t) 를줄일수있다. 키트리 T의높이를 h라하고차수를 d 라하자. [1] 에서는키중심모드의탈퇴동작에서 L Enc(T) = d(h - 1) 이라고계산되어있다. 그러나, 실제로는다음에증명된것과같이 d(h -1)-1 이다. -42-
[ 정리 2.1] n 명의사용자를포함한키트리 T 의높이가 h 이고차수가 d 이면키중심모드의탈퇴동작에서 LEnc(T) = d( h - 1)-1 이다. 증명 : 탈퇴동작의경우 T 에서사용자정점의부모노드부터루트까지모두 (h - 1) 개의키들이새로이생성된다. 이들중루트부터레벨 (h - 2) 사이의 (h - 2) 개의키들은자신들의서브그룹키들로각각암호화된다. 따라서 d(h - 2) 번의암호화가이루어진다. 레벨 (h - 1) 즉탈퇴하는사용자의부모노드에위치한새로이생성된키는자신의자식노드에있는 (d - 1) 개의사용자들의개인키로암호화가된다. 따라서, 이다. 이때 LMsg(T)=(d - 1)(h - 1) 이요구되며이는탈퇴하는사용자의부모정점으로부터루트 에이르는 (h - 1) 개의키들이자신의자식노드에포함된서브그룹키로서로다르게암호 화된후전송되기때문이다. 키트리모델에서상기한두가지종류모드들의효율성을정리한것은다음표와같다. 여 기서키트리 T 는 n 명의사용자를수용할수있으며루트의레벨을 1 그리고 T 의높이 및차수는각각h 및 d 로정의한다. -43-
표 2.2 를통하여키중심모드의효율성이가입및탈퇴동작모두에서사용자중심모드보다뛰어나다는것을알수있다. 따라서앞으로키트리모델은키중심모드를기본모드로정의하며 3장및 4장에서는키중심모드를기반으로완전정규트리및가변트리모델의최적화를이룰수있는메카니즘을분석하도록한다. 표 2.2. 키트리모델의효율성 -44-
제 3 장. 완전정규트리를이용한그룹키관리알고리즘최적화 완전정규트리 (Full Regular Tree) T 는 T 의말단정점들을제외한모든내부정점들이동일한갯수의자식노드를갖으며또한모든말단정점들은동일한레벨에위치하는트리이며특히 [1] 의키트리또한이러한완전정규트리가기본모델이다. 완전정규트리의차수 d 는내부정점들이갖는자식노드의갯수라고정의한다. 2장에서분석된표 2.2의키트리모델의효율성은이러한완전정규트리를기반으로한효율성을나타낸다. 2장에서우리는키중심모드의효율성이사용자중심모드보다더효율적임을보였다. 따라서, 본장에서는키중심모드를기본으로이를완전정규트리에서키갱신메세지를최소화할수있는메카니즘을분석하도록한다. 다음은 2장에서분석된키트리모델에서키중심모드의효율성을나타내는것으로분석을위하여여기서다시인용하였다. 본장에서모든키트리는달리언급하지않는한완전정규트리를의미한다. 표 3.1. 키트리모델( 키중심모드) 의효율성 키중심모드 가입동작 탈퇴동작 JMsg(T)/LMsg(T) h (d-1)(h-1) JEnc(T)/LEnc(T) 2(h-1) d(h-1)-1-45-
표 3.1에의하면키트리 T 의효율성은 T 의높이 h 및차수 d 에의하여결정된다는것을알수있다. 다음2 개의정리들은완전정규트리의높이를분석한것이다. [ 정리 3.1] 완전정규트리 T 의차수가 d ( 2) 이고말단정점갯수가 n 이면 T 의높이 h 는다음식을만족한다. 증명 : 증명은 T 의높이h 에대한귀납법을사용한다. d 2 이므로 h=2 이면 n=2가되며 이다. 식 (3.1) 이 h 보다작은높이를갖는완전정규트리에성립한다고가정하고높이 h (> 2) 및 n 개의말단정점을갖는완전정규트리 T 를고려하자. T 의루트의 d 개의자 식노드들은모두 (h - 1) 의높이를갖는완전정규트리의루트가되므로이러한 d 개의 서브트리(subtree) 들을 T 1, T 2,..., T d 라하며 T 1 (1 i d) 의말단정점의갯수를 n i (1 i d) 라하자. 그렇다면 n i = n/d가된다. T i (1 i d) 의높이를 h l 라하면귀납가정에 의하여 h l = h - 1 이므로따라서, h =log d n+1 이다. -46-
키트리 T 에포함되는사용자의수를 n 명이라하자. T 의차수가 d 일때만일 n = d k (k = 1, 2,...) 라면정의 3.1에의하여 h = 1 + log d n임을알수있지만만일 n d k 라면 T 의높이h는최소한 이되어야함을다음정리가보여주고있다. [ 정리 3.2] 최소한 n 개의말단정점을수용할수있는차수 d 를갖는완전정규트리의높이 h 는다음식을만족하여야한다. 증명 : 만일 n=d k (k =1,2,...) 이면정리 3.1에의하여 h=log dn + 1 이다. n 을 d k < n < d k+1 의범위에있는정수라하고 h < 이라하자. 그렇다면정수 h 의최대값은 이된다. 또한 d k < n < d k+1 이므로 이다. 완전정규트리의높이가 k + 1이라면말단정점의갯수는 d k+1-1 = d k (< n) 이므로 n(d k < n < d k+ 1) 개의말단정점을포함할수있는완전정규트리의높이h 는식(3.2) 를만족하여야한다. 표 3.1은키트리모델의효율성은 d 및 h 의크기에의존하고있다는것을보여준다. 또한정리 3.2는키트리 T 에최소한 n명의사용자를수용하기위해서 T 의높이는최소한 보다크거나같아야하므로우리는 h 를최소화하는것이키트리모델의효율성을높일수있는것이므로 h 는필요한최소한의크기즉, 로정의한다. -47-
표 3.1 은키트리모델에서탈퇴동작은모두 (d - 1)(h - 1) = (d -1)( ) 개의키갱신메세지가필요하다는것을보여주고있다. 이때주어진사용자의수 n 을위한키트리 T 의높이 h 는 d 에의하여결정되므로어떠한d 값에대하여키트리모델이탈퇴동작에서최적이될수있는지를분석할수있다. 다음의정리 3.3 3.6 및따름정리 3.7은키트리모델에서탈퇴동작의경우 d = 2 일때즉, 키트리가완전이진트리인경우에가장적은수의키갱신메세지를요구한다는것을알수있다. [ 정리 3.3] x 및 y 를 2 개의실수라하자. 만일 x < y 라면 [x] [ y] 이다. 증명 : x=a+r 1 및 y=b+r 2 (a, b 는정수, 0 r 1, 2 r <1) 라하자. ( 경우 1) 1 r =r 2 =0 x=a, y=b 이며 a<b 이므로 [x] =a<b=[y] 이다. ( 경우 2) 1=0, r 2 r 0 a<[b+r 2 ]=b+[r 2 ]=b+1로부터 a b 이다(a,b 는정수이므로). 따라서, -48-
이다. ( 경우 3) 1 r 0, 2 r =0 a+r 1 <b로부터 a+1 b 이다(a, b 는정수이므로). 따라서, 이다. ( 경우 4) 1 r 0, 2 r 0 α+ 1 r <b+r 2 로부터 a b이다. 따라서, 이다. [ 정리 3.4] 정수 n(>1) 에대하여log 2 n<(d-1)(log d n). 여기서, d = 3,4,..., n. 증명 : -49-
[ 정리 3.5] 정수 x 및실수y( ) 에대하여 [xy] x[y] 이다. 증명 : y = k + r(k 는정수, 0 r < 1) 이라하자. 만일 =0 r 이면명확히 [xy] = x[y] 이다. r 0이면 x'r < x 이므로 [xr] x = x[r] 이다([r]=1 이므로) 이다. 따라서, [ 정리 3.6] 정수 d=3,..., n에대하여 이다. 증명 : 정리 3.4 및 3.5에의하여 -50-
정리 3.6 으로부터우리는다음과같은따름정리를구할수있다. [ 따름정리 3.7] n 명의사용자를포함하는키트리모델 T 는차수가 2 일때탈퇴동작에서최소한의키갱신메세지가발생한다. n명의사용자를포함한완전정규트리의경우 d = 2 일때탈퇴동작은최적화가된다는것을따름정리 3.7이보여주었지만다음정리는차수 d = n 일때가입동작은최적화가된다는것을보여준다. 이때완전정규트리 T 의차수 d = n 이라는것은 T 가 Star그래프라는것과동일한것임에주의한다. [ 정리 3.8] n 명의사용자를포함하는키트리모델 T 는차수가 n 일때가입동작에서최소한의키갱신메세지가발생한다. 증명 : 모든키트리모델의가입동작에서 PFS를위하여기존에사용되는그룹키를새로운그룹키로대체하여야하기때문에한개의키갱신메세지는새로운사용자를위하여필요하며또다른최소한한개의키갱신메세지가기존의사용자들을위하여필요하다. 따라서, 모든키트리모델의가입동작에는반드시최소한 2 개의키갱신메세지가필요하다. u 1 u n 등모두 n 명의사용자를포함하는키트리모델 T 의차수를 n 이라하자. 그렇 다면 T 의높이 h 는 2 가된다. 따라서 T에서의가입동작에는 h = 2 개의키갱신메세지 가필요하다. -51-
따름정리 3.7과정리 3.8은키트리모델 T 에서가입및탈퇴동작은서로상반된구조에서키갱신메세지의효율성이최적화되고있음을보여준다. 즉가입동작의경우 T 의높이가작을수로적은수의키갱신메세지가발생하지만탈퇴동작의경우 T 의높이가클수록적은수의키갱신메세지가발생한다는것을보여준다. 이것이키트리모델의최적화를이루는데가장어려운부분이다. 이는다시말해서가입및탈퇴동작에서키갱신메세지를모두최적화할수있는키트리구조는찾을수없다는것을의미한다. 이러한분석은자연스럽게키트리를기반으로한그룹키관리구조에서가입및탈퇴동작이발생하는비율을고려한상태에서키트리의최적화를이룰수있는방안을연구하여야함을제시하고있다. 키트리모델 T 에서가입및탈퇴동작이 50-50의비율로발생한다고가정한상태에서 A 를가입및탈퇴동작에의하여발생하는평균키갱신메세지갯수라하면 A 는다음과같다. 그러나, 이므로이값을 (3.3) 식에대입하면, 가된다. 우리는 d = 2 또는 d = 3 일때A 가최소값을갖는다는것을정리 3.9~3.11 및따름정리 3.12 를통하여증명할수있다. -52-
[ 정리 3.9] 양의정수 n( 1) 에대하여다음관계가성립한다. (1) 만일 n = d k (k는 n 1 을만족하는정수) 라면 d = 2, 3,... 에대하여 이다. (2) 만일 n d k (k는 n 1 을만족하는정수) 라면 d = 2, 3,... 에대하여 이다. 증명 : (1) n = d k 이면 (0 < r < 1) 이다. 따라서, (2) n 이 d k-1 < n < d k 이라하자. 그렇다면, (0 < r < 1) 이므 로 가된다. 또한만일 n = d k -1 이라면 이며 n d k -1인경우에도 가된다. 따라서, 모든경우에서 이다. [ 정리 3.10] n ( 6) 및 4 이다. d n 을만족하는모든정수 n 및 d 에서대하여 -53-
증명 : 증명은 n 에대한귀납법을이용한다. n=6이면 이고 4 d n(=6) 범위의 d 값에대하여, 및 이므로모든경우에서 이다. 이제 n(>6) 및 4 d n에대하여 이성립한다고가정하고다음을증명하도록한다. 우리는 n 의크기에따라다음과같은 (1) n =2 k (k 3) 인경우: 2 가지경우를증명한다. (2) n 2 k (k 3) 인경우: [ 정리 3.11] 주어진 n 값에대하여 A = ㆍ 은 d = 2 또는 d = 3 일때최소값을갖는다. -54-
증명 : 정리 3.10으로부터 d 4 인경우에 임을알수있다. 따라서, 만일 이라면 이최소값이되며만일 < 라면 이최소값이된다. 따라서 A = ㆍd 은 d=2 또는 d=3 일때최소값을갖는다. 정리 3.11은 A 값이최소가되는정확한 d 값을한번에결정해주지는않는다. 그러나, d = 2 또는 3 인경우를계산한후이들값들을비교함으로서 A 가최소가되는정확한 d 값을알수있으며우리는다음과같은따름정리를얻는다. [ 따름정리 3.12] 완전정규트리모델 T 에서가입및탈퇴동작이 50-50의비율로발생할때키갱신메세지를최소화할수있는구조는T의차수d가 2 또는 3 일때이다. 더욱일반적인경우를고려하기위하여 p 를키트리모델에서탈퇴동작이발생하는비율을나타낸다고하자. 그렇다면가입동작은 (1 - p) 의비율로발생하므로이들이발생하는 평균키갱신메세지갯수 A(p) 는 -55-
이다. 우리는따름정리 3.12 로부터 p = 인경우 d = 2 또는 d = 3 인경우에 A(1/2) 가최 소값을낳는다는것을증명하였었다. 그러나, 다음정리는따름정리 3.12 보다더욱강한 정리로서만일 p 0.5라면 d = 2 또는 d = 3 일때 A(p) 값이최소가된다는것을보여 준다. [ 정리 3.13] d 4 및 p 라면 증명 : 1-2p + pd이다. 주어진조건에서 d 4 이며 ( 2p -1) 0 이므로식(3.4) 는항상참이다. 주어진 n 에대하여 A d (p) 를차수 d를가지는완전정규트리의 A(p) 라하자. 그러면, 가된다. 다음정리는A d(p)(d 4) 의관계를설정해준다. -56-
[ 정리 3.14] n( 6) 및 4 d n 을만족하는모든정수 n 및 d 에서대하여만일 p 라면 d 4에대하여A2 (p) A d (p) 이다. 증명 : 정리 3.10으로부터 n 6 및 4 d n 에대하여 임을 알수있다. 따라서, 또한정리 3.13으로부터 d 4 및 p 라면 1-2p + pd임을알수있다. 따라 서, d 4에대하여 이다. [ 정리 3.15] n( 6) 및 4 d n 을만족하는모든정수 n 및 d 에서대하여만일 p 라면 d=2 또는 d=3 일때A(p) 는최소값을갖는다. 증명 : 정리 3.14로부터 d 4 에대하여 A 2 (p) A d (p) 이므로만일 A 3 (p) < A 2 (p) 라면 A 3 (p) 가 A(p) 의최소값이되며만일A 3(p) A 2(p) 라면 A 2(p) 가 A(p) 의최소값이다. -57-
[ 따름정리 3.16] 완전정규트리모델 T 에서탈퇴동작의발생율이 50% 이상이라면키갱신메세지를최소화할수있는구조는T의차수d가 2 또는 3 일때이다. 따름정리 3.16은 p 0.5 인경우 A 2 (p) 및 A 3 (p) 등 2 개의값들만을비교함으로서 A(p) 의최소값을구할수있다는것을보여준다. 그러나, p < 0.5라면모든 A d(2 d n) 값들과비교를하여야할것이다. 다음은완전정규트리를이용한키트리모델에서키갱신메세지갯수를최소화할수있는차수 d 를계산하는알고리즘이다. [ 알고리즘 3.1] 완전정규트리의최적화알고리즘입력 : n은최대사용자수,p는탈퇴동작발생율. 출력: 최적화를이룰수있는그룹키의차수 d. -58-
본알고리즘은 p < 0.5인경우 for loop 가모두 (n-1) 번반복수행되며 A i (p) 계산에는모두상수갯수의사칙연산이포함된다. 따라서본알고리즘의복잡도는 O(n-1) 이다. 높이 h 를갖는완전정규트리 T 의차수를 d 라하면 T 내에포함된서브그룹키갯수는모두 d 1 +d 2 + ㆍㆍㆍ + d h-2 = 이며다음정리는명백한것으로서 T 의서브그 룹키갯수는 T 가 star그래프즉 d=n 일때최소화가된다는것을보여준다. [ 정리 3.17] n 명의사용자를수용할수있는완전정규트리 T 에서서브그룹키의갯수 는 d=n 일때최소화가된다. 증명 : d = n 이면 가된다. 따라서 = 0 이다. 이것은 T 가 star 그래프임을의미하며 Star 그래프는서브그룹키를사용하지않는다. -59-
정리 3.17은그룹키모델 T 에서서브그룹키의갯수를최소화하는것은 p( 탈퇴동작의비율가 ) 0 이되지않는한불가능하다는것을암시한다. -60-
제 4 장. 가변트리를이용한그룹키관리알고리즘최적화 3 장에서는키트리의기반구조를완전정규트리에국한한상태에서키갱신메세지의갯수를최소화할수있는키트리의차수 d 를분석하였다. 본장에서는완전정규트리를포함하지만더욱일반적인트리구조인가변트리를키트리의기반구조로이용한상태에서키트리의최적화를분석하도록한다. 3장과마찬가지로키트리의최적화는키갱신메세지갯수를최소화할수있는구조를나타냄에주의하도록한다. 1 절에서는가변트리를이용한키트리의최적화의타당성을분석한후 2 절에서는실제적인가변트리를이용한최적화방안을분석한다. 제 1 절. 가변트리를이용한키트리최적화의타당성분석 가변트리는트리의일종으로서다음과같이완전정규트리에비하여훨씬유연한구조를갖는트리구조이다. [ 정의 4.1] 가변트리 T는트리로서모든말단정점들은동일한레벨에위치하며동일한레벨에위치한내부정점들은동일한갯수의자식노드를갖지만서로다른레벨에위치한내부정점들은서로다른갯수의자식노드를가질수있다. 높이 h 를갖는가변트리 T 의차수수열 Deg(T) = {d 1, d 2,..., d h-1 } 는 T 의레벨 i, 1 i h-1, 에서각내부정점들이갖는자식노드의갯수를나타낸다. -61-
차수수열 Deg(T) = {d 1, d 2,..., d h-1 } 에서모든 d i(1 i h-1) 들이 2 인차수수열을 (2)- 차수수열 이라정의하며모든 d (1 i i h-1) 들이 2 또는 3 인차수수열을 (2, 3) - 차수수열 이라정의한다. 다음그림 4.1은모두 18개의말단정점을포함하는가변트리로서 Deg(T) = {3, 2, 3} 을갖 는다. 표현의단순화를위하여 Deg(T) = {a 1, a 2,..., a i, b 1, b 2,..., b } j 로표현하기로한 다. 예를들어서 Deg(T)={2 3 5 4 }{2,2,2,5,5,5,5,} 이다. 그림 4.1. Deg(T)={3, 2, 3} 으로구성된가변트리 T 완전정규트리는구조의단순함으로인하여그룹키서버의관리측면에서매우효율적이지만관리하여야하는최대사용자수에따라서는비효율적인데이터구조가될수도있다. 그룹키서버가키트리를이용하여관리하여야할최대사용자수가 n 이라하자. -62-
만일 n = d k 의정수라면완전정규트리에는불필요한말단정점이포함되지않지만만일 n d k 라면완전정규트리에는상당히많은수의불필요한말단정점및서브그룹키들이포함되게된다. 예를들어서, n = 1,000,000인경우다음표는서로다른트리차수를갖는완전정규트리들의효율성을보여준다. 표 4.1. 1,000,000 명을수용하기위한키트리의효율성 이때만일탈퇴동작의발생율이 30% ( 즉, p = 0.3) 라면 3장의알고리즘 3.1로부터트리의 차수는 3일때최소한의키갱신메세지가발생된다는것을알수있으며표 4.2는본경우 에서완전정규트리의효율성을보여준다. 표 4.2 및 4.3에서 ReKey(T) 는 p = 0.3 일때 발생되는평균키갱신메세지갯수이다. 표 4.2. p=0.3 인경우최적화된완전정규트리의효율성 차수 높이 Rekey(k) Enc(T) SubKey(T) 최대로가능한사용자수 3 12 15 25 88,572 131,072-63-
또한표 4.3은 p =0.3인경우Deg(T)={4 6 5 2 } 로구성된가변트리의효율성을보여준다. 1) 표 4.3. p=0.3 인경우최적화된가변트리의효율성 차수 높이 Rekey(k) Enc(T) SubKey(T) 최대로가능한사용자수 {4 6 5 2 } 9 14.1 21.1 25,940 102,400 우리는표 4.2 및 4.3을비교함으로서모든효율성파라메타에서가변트리가우월함을알수있다. 특히요구되는서브그룹키의경우완전정규트리는가변트리에비하여약 4 배정도의서브그룹키를필요로한다는것을알수있다. 서브그룹키들은그룹키서버에의하여모두저장및관리되어야하므로최소한의서브그룹키를사용하는것은그룹키서버의효율성측면에서매우중요한것이다. 가변트리가완전정규트리에비하여진보된효율성을보이는이유는가변트리의경우그룹이필요로하는최대사용자수에서완전정규트리보다더욱근접한갯수의말단정점들을생성할수있기때문이다. 예를들어서, 표 4.2 및 4.3에서최대로필요한말단정점의갯수가 100,000일때완전정규트리의경우 131,072개의말단정점이필요하지만가변트리의경우 102,400로서가변트리가필요한말단정점의갯수에서완전정규트리보다훨씬근접하도록구성할수있다는것을알수있다. 이것은가변트리가트리구조측면에서완전정규트리보다훨씬유연하기때문에가능한것이다. 1) 가변트리의최적화방법은추후에분석됨 -64-
제 2 절. 가변트리를이용한키트리최적화 가변트리를이용한그룹키관리구조의효율성은다음과같이계산할수있으며증명과정은단순한것이므로생략한다. [ 정리 4.1] T를 Deg(T) = {d 1, d 2,..., d h-1 } 의차수를갖는가변트리라하자. 그러면 T 의효율성은다음과같다. 가변트리모델에서가입및탈퇴동작이각각 50% 씩균등하게발생한다고가정하자. 그렇다 면평균적으로발생하는키갱신메세지갯수 A 는다음과같다. -65-
A 는 (d 1, d 2,...,d h-1) = d 가 i 최소가될때최소가된다. 따라서, 가입및탈퇴동작이동일한비율로발생할때우리는 d 를 i 최소화할수있는수열 {d 1, d 2,..., d h-1 } 을찾는것이목적이다. 그러나, 키트리는항상주어진 n 명의사용자를수용하여야하므로수열 {d 1, d 2,..., d h-1 } 로구성되는키트리의말단정점들의개수 d 1d 2 ㆍㆍㆍd h-1 = d 로서 i 이값은반드시 n 보다크거나같아야한다. 즉, 수열 {d 1, d 2,..., d h-1 } 은 d 1 d 2 ㆍㆍㆍd h-1 = d i n의조건을만족시켜야만한다. 따름정리 4.6은가변트리모델에서가입및탈퇴동작의발생비율이 50-50 인경우 (2, 3)- 차수수열이키갱신메세지갯수를최소화할수있는구조임을보여준다. 정리 4.2 4.5는 따름정리 4.6 을증명하는과정에서필요한정리들이다. [ 정리 4.2] 모든 n( 5) 에대하여 2n+1<2 이다. 증명 : 증명은 n에대한귀납법을이용한다. n=5 이면 2(5)+1 = 11 < 2 4 = 16 이다. 이제 n(>6) 에대하여주어진식이성립한다고가정하고다음을증명한다. 식 (4.2) 은다음과같으므로 -66-
2(n+1) + 1 < 2 n 이다. [ 정리 4.3] 모든 n( 7) 에대하여s=d1d 2 ㆍㆍㆍd m n 및 p = d1+d 2 + ㆍㆍㆍ +d m n를만 족하는 (2)- 차수수열 {d 1,d 2,..., d m } 이존재한다. 증명 : (1) 이라하자. 먼저 을증명하자. 식 (4.3) 는 n 1에대하여참이므로 s n 이다. (2) 다음은 p = 2ㆍ n 임을증명하도록하자. 이것을위하여먼저 2ㆍlog 2 n < n - 1 임을 n( 7) 에대한귀납법을이용하여증명하도록한다. 그러나, 2ㆍlog 2n < n - 1 log 2 n 2 < log 2 n2 n-1 이므로우리는 n 2 < 2 n-1 을 n 에귀납법을이용하여증명하도록 한다. n = 7이면 7 2 = 49 < 2 6 = 64 이다. 이제주어진식이 n 에대하여성립한다고가정하고 다음을증명한다. -67-
식 (4.4) 은다음과같으므로 이성립하며따라서, 2ㆍlog 2 n < n-1 이다. 이제정리3.3에의하여 이다. [ 정리 4.4] 모든정수 n( 4) 에대하여 s = d 1 d 2 ㆍㆍㆍd m n 및 p = d 1 +d 2 + ㆍㆍㆍ +d m n 를만족하는 (2, 3)- 차수수열 {d 1,d 2, ㆍㆍㆍ,d m } 이존재한다. 증명 : n =4,5,6 인경우다음과같은 (2,3)- 차수수열들이존재한다. - n = 4 인경우{2ㆍ2} - n = 5 인경우{2ㆍ3} - n = 6 인경우{2ㆍ3} n 7 인경우정리 4.3은 n 에대하여 (2)- 차수수열이존재함을보여준다. (2)-차수수열 은 (2, 3)- 차수수열에포함되므로증명은완료된다. -68-
[ 정리 4.5] 가변트리 T 에서가입및탈퇴동작이발생하는비율을 50-50이라하고키갱신 메세지의갯수를최소로하는차수수열을 s min = {d 1,d 2,..., d h-1 } 이라하자. 그렇다면 s mi n 중에는 (2, 3)- 차수수열이존재한다. 증명 : 가변트리에서주어진사용자수 n 에대한최적의수열을 s min = {d 1, d 2,..., d h-1} 이라하자. 만일 S min 이 (2, 3)- 차수수열이라면증명은완료된다. 만일그렇지않다면 1 i h-1 에대하여 d i 2 및 di 3인 d i 가존재한다. 이제 s' min 을 s min 으로부터 d i 를제거하고 d i 대신에정리 4.4 에서제시되는수열 {d 1 1, d 1 2,..., d 1 t}(t 2) 로대체한차수 수열이라하자 (s' min 수열의길이는 2 이상이된다). 정리 4.4로부터 d i 임을알수있으므로우리는다음과같은부등식들을얻는다. d' i d i 및 d' i 이제만일 s' min (2, 3)- 차수수열이라면우리의증명은완료된다. 만일그렇지않다면상기한과정을반복적으로적용할수있다. 그러나우리의수열은유한하므로증명은완료된다. 식(4.1) 로부터 A = 을 ( di + 1) 를최소화하기위해서는 d 를 i 최소화하는것과동일하 다는것을알수있으며또한정리 4.5 는 (2, 3)-차수수열이 d 를 i 최소화할수있는차수수열들중하나라는것을밝혀주고있다. 따라서우리는다음의따름정리를얻게된다. -69-
[ 따름정리 4.6] 가변트리 T 를기반으로한그룹키관리에서가입및탈퇴동작의발생비울이 50-50인경우키갱신메세지를최소화할수있는 T 의차수수열은 Deg(T) 가 (2, 3)- 수열차수인경우이다. 3장에서따름정리 3.12를통하여완전정규트리 T 를기반으로한그룹키관리에서탈퇴동작의발생비율이 50% 이상인경우키갱신메세지의갯수를최소화할수있는 T 의차수는 2 또는 3 이라는것을증명하였었다. 우리는이와유사한성질을가변트리모델에서도증명할수있다. 즉, 가변트리모델에서탈퇴동작의발생비율이 50% 보다크다면키갱신메세지갯수를최소화할수있는차수수열은 (2, 3)- 차수수열임을증명할수있다. 가변트리 T 를기반으로하는그룹키관리에서탈퇴동작이발생하는비율을 p라하자. Deg (T) = {d 1, d 2,.., d k } 라하고탈퇴동작의발생비율이 p 인경우발생하는평균적인키갱신 메세지갯수를 A(p) 라하면A(p) 는다음과같다. -70-
[ 정리 4.7] 가변트리 T를모델로하는그룹키관리에서탈퇴동작의발생빈도수 p가 0.5보 다크다고하자, 즉 p > 0.5. 그렇다면키갱신메세지갯수를최소화하는수열은 (2, 3)-차 수수열이다. 증명 : 주어진사용자수 n 및 p (> 0.5) 에대하여 s = {d 1, d 2,..,, d k } 를 A(p) 를최소화하 는수열이라하자. 만일 s가 (2, 3)- 차수수열이라면증명은완료된다. 만일그렇지않다면 d i 2 및 d i 3인 d i, 1 i h - 1, 가 s 내에반드시존재한다. s' 를 s 로부터 d 를 i 제거하고정리 4.4 로부터정의된수열로대체한차수수열이라하자. T 및 T 를수열 s 및 s' 로부터정의된가변트리모델이라하고 h 및 h' 를 T 및 T의높이라하자. 또한 d i 및 d' 를 i 수열 s 및 s' 의합이라하자. 그렇다면명확히 h < h' 이며또한정리 4.4로부터 d i d' i 이다. A(p) 및 A (p) 를탈퇴동작의발생비율이 p 일때 s 및 s' 를차수수열로하는가변트리모델의평균키갱신메세지갯수라하자. 그러면 가된다. 그러나, h - h' > 0 및 d i d' i 이고또한 0.5 < p 1 이면 1 (1-2p) < 0 이므로다음관계가성립한다. -71-
따라서, A(p) > A (p) 임을알수있다. 만일 s' 가 (2, 3)-차수수열이라면증명은완료되며만일 (2, 3)- 차수수열이아니라면상기한과정을반복적으로적용할수있다. 그러나, 가변트리모델의차수수열은유한하므로증명은완료된다. 따름정리 4.6 및정리 4.7 에서언급되는 (2, 3)-차수수열은실제로는유일한것이아니므로우리는가능한모든 (2, 3)- 차수수열들을모두고려하여야한다. 정리 4.8은이미널리알려진정리이며우리는이를이용하여정리 4.9에서최대 n 명의사용자를포함하는가변트리 T 에서나타날수있는모든 (2, 3)- 수열의최대갯수를계산한다. [ 정리 4.8] X 가 t 개의원소를가진집합이라고할때, 반복이허용된다면, X 에서순서에관계없이 k 개의원소를선택하는방법의수는다음과같다. [ 정리4.9] n( 4) 개의말단정점을포함하는가변트리 T의 (2, 3)-차수수열의길이를 k 라하자. 그렇다면 k 의범위는 2 k 이며 T 를구성할수있는 (2, 3)-차수수 열의총갯수는 C(k+1, 1) 0(( ) 2 ) 이다. -72-
증명 : n 4 이므로 (2, 3)-차수수열로구성된가변트리의높이는반드시 3 보다크거나같아야한다. 또한 n 개의말단정점을포함할수있는최소한의높이를가지는완전이진정규트리의높이는 이다. 따라서, k 의범위는 2 k 이다. 각 k(2 k ) 에대하여서로다른 (2-3)-차수수열은정리 4.8에의하여모두 C(k+2-1, 1)=C(k+1, 1) 이므로가능한 (2, 3)-차수수열의총갯수는 C(k+1, 1) 이된다. 또한, 이다. 끝으로 이다. -73-
정리 4.9의예제를위하여높이 h 및 Deg(T) = {d 1, d 2,..., d h-1 } 를갖는가변트리 T 가최대 n = 20 명의사용자를관리하여야한다고하자. 그렇다면이러한 T 를구성할수있는가능한 (2, 3)-차수수열의총개수는 이므로정리 4.9에의하여 =18 개가되며이들수열들은다음표와같다. 표4.4.n=20 인경우가변트리를구성할수있는(2, 3)-차수수열 표 4.4에는모두 18 개의 (2, 3)- 차수수열들이나타나지만이들을모두고려할필요는없다. 이는이들수열들의합인 d 가 i 모두 d i n 을만족하는것이아니기때문이며 d i < n 인수열들은당연히고려할필요가없다. A(p) = h(1-2p)+p( + 1) 값을분석해보면 p (0.5 p 1) 가상수일때동일한 h 값에대해서는 d i 값이작을수록 A(p) 값이작아진 다는것을알수있다. 이것은다시말해서, 표 4.4 의각행은동일한높이를가지는 (2, 3) -차수수열이며각행에서아래로내려갈수록 d i 값이증가하므로일단 d i n 인수열이 발견되면더이상동일한행내의( 즉, 동일한높이를가진) 다른수열을검사할필요가없 다는것을의미한다. -74-
예를들어, 표 4.4 의첫번째행의첫번째열에있는 (2, 3)- 차수수열 {2, 2, 2, 2, } d i = 32 로서 n = 20 보다크거나같다. 따라서, 첫번째행의두번째이상의열들에포함된수열들의합은모두{2,2,2,2,2} 보다크므로이들을고려할필요는없다. 지금까지우리는가변트리 T 를이용한그룹키관리모델에서탈퇴동작의발생비율이 5 0% 이상인경우에는 (2, 3)-차수수열이평균키갱신메세지를최소화할수있다는것을증명하였으며이경우가능한 (2, 3)- 수열들의총갯수를밝혔다. 그러나, 만일탈퇴동작이 5 0% 보다작은경우에는우리는모든가능한가변트리들을고려하여야만한다. 즉, 다시말해서 (2, 3)- 차수수열이외의모든수열들을고려하여야만한다. 높이 h 및 n 개의말단정점을갖는가변트리 T 의차수수열을 {d 1, d 2,..., d h-1 } 이라하자. 만일우리가 d (1 i i h-1) 에특정한제약을부여하지않는다면개개 d i 들은 2 부터 n 까지조사가되어야하므로만일 n 값이충분히크다면이것은현실적으로조사가능한범위를벗어나게된다. 따라서, 우리는조사되어야할수열의갯수및각수열의 d i 값들을최소화하여야한다. 또한 3 장에서 Star 그래프는가입동작을위한최적의구조이며완전이진정규트리는탈퇴동작을위한최적의구조라는것을증명하였었다. 따라서우리는완전이진정규트리를기반으로하여모든가능한높이및차수수열을고려함으로서최선의효율성( 즉, 적은키갱신메세 지) 을보이는가변트리를찾는다. -75-
식 (4.5) 의 A(p)=h(1-2p)+p( d i +1) 는 p 및 h 가상수값인경우 A(p) 의최소값은 d i 최소값에결정된다는것을알수있다. 따라서, 동일한높이를가지는가변트리들사이에서각가변트리들의차수수열의합이최소 인가변트리가동일한높이를갖는가변트리들사이에서 A(p) 값을최소로한다는것을알 수있다. [ 정리 4.10] 가변트리 T 의차수수열 {d 1, d 2,..., d k}(d i 2, 1 i k) 가 의 길이를갖는 (2)- 차수수열과동일한길이를갖으며( 즉, k = ) d 1 ㆍd 2 ㆍㆍㆍd k n 을만족하지만 (2)- 차수수열과는다른수열이라하자. 그렇다면정수 n( 2) 에대하여 > 2 이다. 증명 : {d 1, d 2,..., d k } 는 2-수열과는다르므로최소한한개의 d j(1 j k) 는 2보다크다. 따라서, d j > 2 라하자. 그렇다면, d (1 i i k - 1, i ) j 의크기는최소한 2 이므 로 d i 의최소값은다음과같다. -76-
따라서, 이므로 d i > 2 이다. 사용자수 n ( 2) 을말단정점으로포함할수있는최소한의높이를갖는 (2)-차수수열로구성된가변트리를 T bin 라하자. 그렇다면 T bin 의높이 h는 +1이되며 Deg(T bin ) = { } 이다. 따라서 T bin 의차수수열의합은 2 이다. 정리 4.10은 T bin 과동일한높이를가지는다른가변트리들의차수수열의합은 2 보다크다는것을증명한것이므로우리는 T bin 과동일한높이를갖는가변트리들을고려할필요가없다는것을의미한다. 따라서우리가고려할가변트리들의높이의상한선은 ( ) 이다. 사용자수 n ( 7) 을말단정점으로포함할수있는최소한의말단정점의갯수를가지는 S tar 그래프를 T star 라하자. 따라서 Deg(T star ) = {n} 이며다음의정리 4.12는모든 n ( 7) 에대하여 T star 들의차수수열의합은 2 보다크다는것을보여준다. 따라서, 우리가고려할가변트리들의높이의하한선은 2 임을증명하고있다. 물론알고리즘에서 Star 그래프자체는다른가변트리들과비교가되어야한다. 그러나, 정리 4.12는비교하여야될 Star 그래프는 K 1,n 한개뿐이라는것을보여주는것이다. 정리 4.11은정리 4.12 를위한것으로서명백한내용이므로증명은생략한다. -77-
[ 정리 4.11] 모든 n d 2에대하여 (1) 만일 n d k 이면 (2) 만일 n = d k 이면. 이다. [ 정리 4.12] 모든 n 7에대하여 n > 2 이다. 증명 : ( 경우1) n=2 k (k 3) 이다. 따라서 =k 이므로우리는 2 k > 2k 임을 k에대한귀납 법을이용하여증명하도록한다. k = 3이면 2 3 = 8 > 2ㆍ3 = 6이므로기본단계는성립한 다. k 3에대하여 2 > 2k라고가정하고우리는 2 k+1 > 2(k+1) 임을증명하도록한다. k 3 이므로다음관계는명백하다. ( 경우2) n 2 k (k 3) 이다. 우리는 n에대한귀납법을이용하여증명하도록한다. n = 7 이면 7 > 2 = 6 이므로기본단계는성립한다. n > 7에대하여 n > 2 이라가정하고우리는 n > 2-1 임을증명하도록한다. 정리 4.11에의하여 n 2 k 라면 이므로 이다. -78-
n( 7) 개의말단정점을갖는가변트리 T 의차수수열 Deg(T) 를 {d 1, d 2,..., d k } 라하자. 정리 4.10 및 4.12는우리가고려하여야할 k 의범위는 2 k ( - 1) 임을밝 혀주었다. 다음정리는이러한 k 의범위내에서우리가고려하여야할 d i 의범위를밝혀준 다. [ 정리 4.13] n 개의말단정점을갖는가변트리 T의차수수열을 {d 1, d 2,..., d k } 라하자. 만 일 d j >2-2(k- 1) (1 j k) 이면 d i >2 이다. 증명 : d i (1 i k) 는 2보다크거나같기때문에 d i 의하한값은다음과같다. 정리 4.13에의하여 n 개의말단정점을갖는가변트리T( 차수수열은 {d 1, d 2,..., d k } 의각 높이에서고려하여야할 d (1 i i k) 의범위는 2 d i 2-2(k-1) 임을알 수있다. 다음은최적의가변트리모델을계산하는알고리즘으로서 p < 0.5 인경우를다룬것이다. p 0.5 인경우에는단지 (2, 3)-차수수열들만이고려되므로알고리즘 4.1과매우유사한 것이므로생략한다. -79-
또한더욱자세한알고리즘은첨부된프로그램을참고하도록한다. 알고리즘 4.1에서수열 s = {s 0, s 1,..., s t-2 } 및 b = {b 0, b 1,..., b t-1} (t = ) 들은 s i = 2 (0 i t - 2) 및 b j = 2(0 j -1) t 로초기화되었다고가정한다. 또한 r i x[u i v] 는부분수열 r u r v 들의값을 x 로대체하는동작이라고정의한다. [ 알고리즘 4.1] 가변트리의최적화알고리즘 입력 : n 은최대사용자수,p 는탈퇴동작발생율, 수열 J 및 b. 출력 : 최적화를이룰수있는가변트리차수수열 b = {b 1, b 2,..., b m-1 }(m 값은알고리즘 참조 ) -80-
[ 정리 4.14] 알고리즘 4.1 에서고려되는차수수열의총갯수는다음과같다. 증명 : 알고리즘 4.1에의하여고려되고있는수열의길이를 k 라하자. 그러면 k 에대하여 2-2(k-1) - 2+1 = 2-2k+1개의서로다른 d i 가고려되므로정리 4.8에의하여고려되는차수수열의갯수는 C(2-2k+1+k-1, k) = C(2 -k, k) 이며 k 의범위는 2 k - 1 이므로총차수수열의갯수는 C(2 -k, k) 이다. 예를들어서, n=20 이며 p 0.5인경우 = 20이므로알고리즘 4.1은모두 C(10-k, k) =78 개의다음과같은차수수열들을고려하게된다. -81-
표4.5. n=20 및p 0.5 인경우고려되는차수수열들 -82-
n = 20 인경우서로다른 p 값에따라서알고리즘 4.1은다음표와같이서로다른최적의가변트리들을계산한다. 표4.6.n=20 인경우서로다른p 값에따른가변트리의효율성 또다른예제로서 n = 100,000 인경우알고리즘 4.1은서로다른탈퇴비율 p 값에대하여다음과같은가변트리들을제시한다. -83-
표 4.7. n=100,000 인경우서로다른 p 값에따른가변트리의효율성 표 4.7을통해서탈퇴비율 p 가커질수록생성되는최적화된가변트리의높이가커지는것 을알수있다. 이것은 [ 따름정리 3.7] 및 [ 정리 3.8] 에서증명한것처럼탈퇴동작의경우 이진트리가그리고가입동작의경우 Star 그래프가최적의트리이기때문에발생하는현상 이다. 따라서, p 가커질수록가변트리의높이가증가되므로요구되는평균서브그룹키의 갯수도따라서증가하는경향을표4.7 을통해서알수있다. 그림 4.2는상기한알고리즘들을자바프로그램언어를이용하여종합적으로구현한시스템 의초기화면이다. 시스템초기화면에서그룹통신에참가할최대사용자및사용자들의탈퇴비율을입력한후 완전정규트리및가변트리들중하나를선택한후 Find the optimized tree 버튼을클릭 하면다음과같은결과화면이생성된다. -84-
그림 4.2. 구현시스템의초기화면 또한, 그림 4.3은최대사용자 100,000, 탈퇴비율 0.4 및가변트리를선택한경우최적의가변트리의차수수열이 {3,3,3,3,3,3,3,3,4,4} 임을보여주고있다. 또한이러한차수수열을바탕으로한가변트리의각종효율성파라메타들을보여주고있다. -85-
그림 4.3. n=100,000, p=0.4, 및가변트리를선택한결과화면 -86-
제 5 장. 결론 본연구의주된목적은그룹통신에서사용자들의가입및탈퇴동작의발생비율을감안한상태에서최소한의키갱신메세지를발생시키는데이타구조및키관리알고리즘을개발하는것이다. 우리는 3장에서완전정규트리 T 를기반으로한키트리모델에서탈퇴동작의발생비율이 50% 이상일경우 T 의차수가 2 또는 3 일경우에발생되는평균키갱신메세지가최소가된다는것을증명하였으며탈퇴동작이 50% 이하일경우에가능한모든완전정규트리들을고려하여최적의차수를계산하는알고리즘을제시하였다. 완전정규트리모델은가변트리모델보다유연성에서뒤지지만트리구조의단순성으로인하여전체적인키관리메카니즘을단순화한다는장점이있다. 완전정규트리의구조적경직성을보완하기위하여본연구에서는새로이가변트리를정의하여본구조를통한최적화가가능한지의타당성을분석하였다. 가변트리는완전정규트리에비하여그룹통신에서최대사용자의수에더욱근접한갯수만의말단정점들을생성하는것이가능하다는것이분석되었다. 이것은그룹통신에서최대사용자수가 d k 의형태로나타나지않는것이더욱일반적임을감안할때가변트리는그룹키관리에서더욱적합한모델이라고판단된다. 완전정규트리와유사하게사용자의탈퇴비율이 50% 를넘는경우가변트리에서도 (2, 3)-차수수열을갖는가변트리들이평균키갱신메세지가최소가된다는것이증명되었다. -87-
또한완전이진정규트리및 Star 그래프가각각사용자의탈퇴및가입동작에대하여최 적의트리구조임을증명하였으며이는탈퇴및가입동작을동시에최적화하는것이불가 능하다는것을분석이수행되었다. 이러한분석을바탕으로한알고리즘들이제시되었으며제안된알고리즘은자바언어로구 현되었다. 구현된알고리즘은최대사용자수및탈퇴동작의발생비율을입력값으로최적 의 ( 최소한의키갱신메세지를발생시키는) 완전정규트리또는가변트리의구조및제시 되는트리구조의효율성이나타나도록구현되었다. 가변트리는완전정규트리에비하여상당히유연한트리구조이지만일반적인트리구조보 다는경직된구조이다. 따라서, 향후에는일반트리구조에기반을둔최적화방안이연구 되어야할것이다. -88-
참고문헌 [1] Chung Kei Wong, Mohamed Gouda, Simon S. Lam, "Secure Group Communicatio ns Using Key Graphs", ACM SIGCOMM'98, 1998. [2] Debby M. Waliner, Eric J. Harder, "Key Management for Multicast: Issues and Arc hitecture", internet draft, draft-wallner-key-arch-01.txt, 1998. [3] M. J. Moyer, J. R. Rao, P. Rohatgi, "Maintaining Balanced Key Trees for Secure Multicast", internet draft, draft-irtf-smug-key-tree-balance-00.txt, 1999 [4] Harray," [5] Thomas Hardjono, Brad Cain, Indermohan Monga, "Intra-domain Group Key Mana gement Protocol", internet-draft, draft-irtf-smug-intragkm-00.txt, 2000. [6] Mitra S., "Iolus : A Framework for Scalable Secure Multicast", ACM SIGCOMM'97, 1977. [7] Balenson, "Key Management for Large Dynamic Groups: One-Way Function Trees and Amotized Initialization", internet-draft, draft-balenson-groupkeymanagement-oft -0 0.txt, [8] H. Harney, A. Colegrove, B. Harder, V. Meth, R. Fleishcher, "Group Secure Associ ation Key Management Protocol", internet-draft, draft-irtf-smug-gaskmp-02.txt, [9] D. Harkins, D. Carrel, "The Internet Key Exchange (IKE)", RFC2409, 1998-89-
-90-