KR100509233B1

KR100509233B1 - 멀티캐스트 그룹 키 관리 방법 및 장치

Info

Publication number: KR100509233B1
Application number: KR10-2003-0036738A
Authority: KR
Inventors: 권정옥; 황정연; 이동훈
Original assignee: 학교법인고려중앙학원
Priority date: 2003-06-09
Filing date: 2003-06-09
Publication date: 2005-08-22
Also published as: KR20040107698A

Abstract

본 발명의 키 관리 방법은 (a) 그룹 관리자 노드로부터 가장 가까운 기존 구성원 노드를 검색하여, 기존 구성원 노드의 부모 노드의 자식 노드로서 중간 내부 노드를 생성하고, 그 중간 내부 노드에 기존 구성원 노드 및 추가 구성원 단말에 대응되는 추가 구성원 노드를 자식 노드로서 추가하는 단계; (b) 기존 구성원 노드의 고유키 및 그룹키를 이용하여 중간 내부 노드의 키를 생성하는 단계; (c) 중간 내부 노드보다 상위 레벨의 내부 노드들의 키를 갱신하는 단계; (d) 갱신된 내부 노드들의 목록을 포함하는 키 갱신 메시지를 생성하여 구성원 노드들에 멀티캐스트 전송하는 단계; (e) 추가 구성원 노드부터 루트노드까지의 경로에 위치하는 각 노드의 키값을 추가 구성원 단말기에게 유니캐스트 전송하는 단계; 및 (f) 각 구성원 단말기에서 키 갱신 메시지를 수신하여, 갱신된 내부 노드 목록에 대응되는 내부 키값들 및 그룹 키를 갱신하고, 추가 구성원 노드에서 각 노드의 키 값 및 고유키값을 복원하는 단계를 포함한다.

Description

멀티캐스트 그룹 키 관리 방법 및 장치{Method and apparatus for multicast group key management}

본 발명은 그룹 키 관리 방법에 관한 것이다. 구체적으로, 구성원들이 빈번히 추가 및 삭제되는 이진 트리 구조의 멀티캐스트 그룹에서 효과적으로 그룹의 키를 갱신하고 분배하는 방법에 관한 것이다.

최근 멀티캐스트 기법은 인터넷을 기반으로 한 유료 TV, 유료 영상 서비스, 비밀 원격회의 등 공개된 네트워크 상에서 디지털 정보들을 전송하는데 적용되고 있다. 멀티캐스트 통신에서 그룹 메시지는 그룹의 모든 구성원들에게 전달된다. 일반적으로 멀티캐스트 그룹에서 정보에 대한 접근권한을 제어하기 위해서는, 그룹키 (세션키)로 데이터를 암호화한다. 그룹키는 단지 그룹내의 구성원들에게만 알려져 있고, 이 키를 알고 있는 구성원들만이 메시지를 복호할 수 있다. 멀티캐스트 통신은 메시지를 개별적으로 n 명의 그룹 구성원들에게 각각 n번 보내는 대신에 모든 구성원에게 단지 메시지를 한번만 전달하면 되기 때문에 효율성면에서 매우 뛰어나지만, 구성원들의 추가 또는 삭제로 인한 그룹의 변동성 때문에 프라이버시에 대한 안전성과 키 갱신 작업의 효율성에 관한 보완이 요구된다.

다양한 암호기술들이 그룹 통신을 보호하기 위해서 사용되는데, 그 메카니즘 중에 하나가 암호화이다. 암호 알고리즘은 입력값으로 그룹 메시지를 받고, 임의로 생성된 키를 이용하여 변환(transformation)을 수행한다. 결과적으로 이 처리 과정은 암호화된 메시지를 생성한다. 그러나 암호화된 메시지를 복호할 때, 키를 알고 메시지를 복호하는 방법보다 쉽게 암호문으로부터 원래의 메시지를 복호할 수 있는 방법은 없다. 따라서 이러한 암호화 기술을 이용하는 것이 안전한 멀티캐스트 세션의 수행을 가능하게 한다. 그룹 메시지는 선택된 키(그룹키)를 이용해 암호화됨으로써 보호되고, 그룹키를 알고 있는 사람만이 본래의 메시지를 복호할 수 있다.

그러나, 정당한 구성원들에게 그룹키를 분배하는 것은 복잡한 문제이다. 비록 새로운 구성원이 추가되는 경우에 그룹의 키들을 변경하는 것이 쉽다 할지라도 구성원이 삭제된 후에 키들을 갱신하는 것은 더 복잡하다. 왜냐하면 갱신된 키들은 삭제된 구성원들이 알고 있는 키들에 의존하지 않는 새로운 키 값들이여야 하기 때문이다.

그룹키 분배 문제와 키 갱신 문제를 해결하기 위해서 제안된 방법들의 양호도는 구성원 저장공간, 그룹 관리자 저장공간, 및 구성원과 그룹 관리자의 계산량에 기반해서 평가된다. 구성원 저장공간은 각 구성원이 저장해야 하는 키의 수이다. 보통 저장해야 하는 키의 수가 작기 때문에 구성원의 키 저장량은 문제가 되지 않는다. 그룹 관리자는 그룹내의 모든 구성원들의 키들을 저장하여야 하는데, 본 발명은 그룹 관리자가 수백만의 가입자들에게 데이터를 보내기 때문에 충분한 저장공간을 가지고 있다고 가정한다. 한편, 구성원과 그룹 관리자의 계산량은 키 갱신에 소요되는 계산량으로, 보통 암·복호화와 다른 타입의 오퍼레이션들을 구분한다. 멀티캐스트 그룹은 매우 변동적이고 수 많은 가입자들로 구성되기 때문에 키 갱신 속도가 가능한 빨라야 한다.

그룹키를 갱신하는 종래의 방법은, 그룹키 관리를 위해서 키를 갱신하는 경우에 논리적 키 계층 (LKH :Logical Key Hierarchy)을 이용하였다. 종래의 키 갱신 방법의 일예는 구성원의 변동이 있을 때마다 변동에 영향을 받는 내부 키들이 새롭게 갱신하고, 새로운 키들은 영향을 받는 노드의 자식 키들로 암호화한 후 멀티캐스트 채널을 통해 분배한다. 한 명의 구성원이 삭제되는 경우에 키 갱신 메시지에는 개의 키가 포함된다.

종래의 다른 키 갱신 방법은 여러명의 구성원들을 동시에 삭제하는 문제에 초점을 맞추고, 이진트리에 boolean function minimization technique을 이용해서 통신비용을 줄였다. 이 종래의 방법에서 구성원의 저장량은이고, 그룹 관리자의 저장량이으로 감소한다. 그러나 이 방법은 id가 서로 보수인 2명이 공모할 경우에는 시스템내의 모든 키들을 알아낼 수 있다는 단점이 있다.

종래의 또 다른 키 갱신 방법은 구성원 추가시에 새로운 키 값들을 대응되는 자식 노드의 키들을 이용해서 암호화하는 대신에 일방향 함수에 새로운 키들을 통과시켜 생성한다. 따라서 새롭게 변경되는 키들의 인덱스들만을 멀티캐스트로 전달하면된다. 이때, 멀티캐스트되는 인덱스의 크기는 키 크기 보다 작으므로, 추가 오퍼레이션 동안에 멀티캐스트되는 메시지의 크기가 이전에 제시된 것보다 작아지게 된다.

LKH 방식의 개선된 접근방법은 McGrewa와 Sherman이 『"Key Establishment in Large Dynamic Groups Using One-Way Function Trees". Technical Report No. 0755, TIS Labs at Network Associates, Inc., Glenwood, MD , May 1998.』논문에서 제안한 일방향 함수트리 OFT 방식이다. 이 방법은 하나의 노드키 값은 자식 노드들의 키들을 일방향 함수로 블라인드 (blind)한 후 XOR 연산자로 혼합한 결과이다. XOR된 결과값은 KEK (KEK:Key Encryption Key)로 유지된다. 이 방법은 하나의 노드 키가 변경될 때, 단지 변경된 키의 블라인드 값이 동기 (sibling) 노드의 키로 암호화된다는 점에서 이전의 방법들보다 개선된 방법으로 평가된다.

한편, 종래 방법의 또 다른 일 예는, 상술한 OFT 방식과 매우 비슷하다. 그러나 이 방법에서는 pseudo-random-function들 (PRFs)을 사용하여 트리내의 키들을 정기적으로 생성하고 갱신한다. 따라서 그룹 관리자는 시간 간격을 두고 그룹키를 PRF를 이용해서 갱신하고, 그 키를 이용해 전체 키 트리를 갱신한다. 이 방법은 모든 구성원들이 자신의 키들을 스스로 갱신할 수 있기 때문에 추가 오퍼레이션 동안에 어떤 멀티캐스트 메시지도 필요 없게되고, 구성원이 삭제될 때는 OFT와 같이 새로운 키들은 그것의 자식 키들을 이용해 생성된다.

종래의 또 다른 키 관리 방법으로 계층적인 이진 트리에 기반한 효율적인 방법(Efficient Hierarchical Binary Tree - EHBT)이 있다. 이 방법은 구성원이 추가되는 경우에는 (단, I 는 키 인텍스로 I < K) 사이즈의 메시지가, 구성원이 삭제되는 경우에는 사이즈의 메시지가 멀티캐스트된다. 하지만 이 방법은 전방보호(Forward Secrecy)를 만족하지 않는다.

한편, 종래 방법의 또 다른 일예는 각 내부 노드마다 내부키 및 보조키를 설정하고, 구성원이 추가 또는 삭제되는 경우에 내부 노드의 자식 노드들의 내부키 및 보조키를 이용하여 상기 내부 노드들을 갱신한다(ESSR 방식).

본 발명은 그룹 구성원의 추가 및 탈퇴시에 각 구성원에게 제공되는 모든 갱신된 키값들을 암화화하지 않고 새로운 알고리즘을 이용하여 간단한 방법으로 은닉함으로써, 키 갱신에 필요한 계산량을 현저히 감소시키는 그룹 키 관리 방법을 제공하는 것을 목적으로 한다.

전술한 기술적 과제를 이루기 위한 본 발명의 키 관리 방법은 (a) 그룹 관리자 노드로부터 가장 가까운 기존 구성원 노드를 검색하여, 기존 구성원 노드의 부모 노드의 자식 노드로서 중간 내부 노드를 생성하고, 그 중간 내부 노드에 기존 구성원 노드 및 추가 구성원 단말에 대응되는 추가 구성원 노드를 자식 노드로서 추가하는 단계; (b) 기존 구성원 노드의 고유키 및 그룹키를 이용하여 중간 내부 노드의 키를 생성하는 단계; (c) 중간 내부 노드보다 상위 레벨의 내부 노드들의 키를 갱신하는 단계; (d) 갱신된 내부 노드들의 목록을 포함하는 키 갱신 메시지를 생성하여 구성원 노드들에 멀티캐스트 전송하는 단계; (e) 추가 구성원 노드부터 루트 노드까지의 경로에 위치하는 각 노드의 키값을 추가 구성원 단말기에게 유니캐스트 전송하는 단계; 및 (f) 각 구성원 단말기에서 키 갱신 메시지를 수신하여, 갱신된 내부 노드 목록에 대응되는 내부 키값들 및 그룹 키를 갱신하고, 추가 구성원 단말에서 각 노드의 키 값 및 고유키값을 복원하는 단계를 포함한다.

또한, 전술한 키 관리 방법의 (b) 단계는, 기존 구성원 노드의 고유키값과 루트 노드의 키 값에 XOR(exclusive or)연산을 수행하여 내부 노드의 키값을 생성하는 것이 바람직하며, XOR 연산 값을 일방향 함수에 대입한 값을 내부 노드의 고유키값으로서 생성하는 것이 더 바람직하다.

또한, 전술한 키 관리 방법의 (c) 단계는, 상위 레벨 노드들의 키 값을 일방향 함수에 대입한 결과 값으로 상위 레벨 노드들을 갱신하는 것이 바람직하다.

또한, 전술한 키 관리 방법의 (e) 단계는, 추가 구성원 노드부터 루트 노드까지의 경로에 위치하는 각 노드의 키값을 블라인드하여 유니캐스트 전송하는 것이 바람직하다.

또한, 추가 구성원 노드의 인덱스와 세션키의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수값과, 추가 구성원 노드의 고유키값의 XOR 연산을 수행하여, 추가 구성원 노드의 고유키값을 블라인드 하는 것이 더 바람직하다.

또한, 추가 구성원에게 유니캐스트 전송으로 키 값을 전송할 때, 추가 구성원 노드의 부모 노드부터 그룹 관리자 루트 노드까지의 경로에 위치하는 각 노드의 키 값은, 각 노드의 인덱스와 하위 노드의 키값의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수 값과, 각 노드의 키 값의 XOR 연산을 수행하여 블라인드되는 것이 바람직하고, 추가 구성원 노드의 키값은 이 노드의 인덱스와 사전에 공유된 세션 키값의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수 값과, 추가 구성원 노드의 키 값의 XOR 연산을 수행하여 블라인드되는 것이 더 바람직하다.

또한, 전술한 (f) 단계에서 추가 구성원 단말기는 추가 구성원 노드의 인덱스와 사전에 공유된 세션키의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수값과 블라인드된 고유키값의 XOR 연산을 수행하여, 추가 구성원 노드의 고유키값을 복원하는 것이 더 바람직하다.

또한, 추가 구성원 단말기는 각 노드의 인덱스와 하위 노드의 키값의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수 값과 블라인드된 각 노드의 개인 키값의 XOR 연산을 수행하여 각 내부 노드의 키값을 복원하는 것이 더 바람직하다.

한편, 본 발명의 다른 키 관리 방법은 (a) 탈퇴를 요청한 구성원 노드(탈퇴 노드) 및 탈퇴 노드의 부모 노드를 삭제하고, 삭제된 부모 노드에 속하는 인접 구성원 노드를 삭제된 부모 노드의 레벨로 배치하는 단계; (b) 인접 구성원 노드의 키 및 이전 세션의 그룹키를 이용하여 하위 레벨로부터 상위 레벨로 노드 키 값을 순차적으로 갱신하는 단계; (c) 갱신된 각 노드의 키 값을 이전 세션의 그룹키 및 갱신된 각 노드의 자식 노드 중 갱신되지 않은 자식 노드의 키값을 이용하여 블라인드하는 단계; (d) 블라인드된 각 노드의 키 값을 포함하는 키 갱신 메시지를 각 구성원 단말기에게 멀티캐스팅 전송하는 단계; 및 (e) 키 갱신 메시지에 따라서 구성원 단말기들이 키 갱신을 수행하는 단계를 포함한다.

또한, 전술한 키 관리 방법의 (b) 단계는 하위 레벨인 자식 노드의 갱신된 키 값과 이전 세션의 그룹키를 이용하여 상위 레벨인 부모 노드의 키 값을 갱신하는 것이 바람직하며, 자식 노드의 갱신된 키 값과 이전 세션의 그룹키값에 XOR 연산을 수행한 값을 일방향 함수에 대입한 결과값을 부모 노드의 키 값으로 갱신하는 것이 더 바람직하다.

또한, 전술한 키 관리 방법의 (c) 단계는 이전 세션의 그룹 키와 갱신되지 않은 자식 노드의 키값을 XOR 연산을 수행한 결과값을 일방향 함수에 대입하여 나온 결과값으로 갱신된 각 노드의 키 값을 블라인드 하는 것이 바람직하며, 일방향 함수의 연산 결과값과 갱신된 노드의 키 값을 XOR 연산하여 갱신된 노드의 키 값을 블라인드하는 것이 더 바람직하다.

또한, 전술한 키 관리 방법의 (e) 단계에서 갱신 메시지를 수신한 구성원 단말기들은 블라인드된 키 값을, 가지고 있는 이전 세션의 그룹키 및 블라인드된 키의 자식 노드의 키 값을 이용하여 언블라인드함으로써, 갱신된 각 노드의 키 값을 복원하는 것이 바람직하며, 이전 세션의 그룹키 및 블라인드된 키의 자식 노드의 키 값에 XOR 연산을 수행하고, XOR 연산 결과값의 해쉬 함수값과 블라인드된 키 값들의 XOR 연산을 수행하여 갱신된 각 노드의 키 값을 복원하는 것이 더 바람직하다.

한편, 본 발명의 바람직한 실시예에 따른 키 관리 시스템은, 루트 노드로부터 가장 가까운 기존 구성원 노드를 검색하여, 구성원 노드 위치에 중간 내부 노드를 생성하고, 생성한 중간 내부 노드의 자식 노드로서, 기존 구성원 노드 및 추가 구성원 단말에 대응되는 구성원 노드를 추가한 후, 기존 구성원 노드의 고유키 및 그룹 관리자 키를 이용하여 내부 노드의 키를 생성하는 구조 변경부, 내부 노드보다 상위 레벨의 내부 노드들의 키를 갱신하는 키 갱신부, 갱신된 내부 노드들의 키 인덱스 목록을 포함하는 키 갱신 메시지를 생성하여 구성원 노드들에 멀티캐스트 전송하는 갱신 메시지 생성부, 및 추가 구성원 노드부터 루트 노드까지의 경로에 위치하는 각 노드의 키값을 추가 구성원 단말기에게 유니캐스트 전송하는 유니캐스트 메시지 생성부를 포함하는 그룹 관리자 서버; 키 갱신 메시지를 수신하여, 갱신된 내부 노드 목록에 대응되는 내부 키값들을 갱신하는 복수의 구성원 단말기; 및 유니캐스트 메시지에 따라서 상기 각 노드의 키 값 및 고유키값을 복원하는 추가 구성원 단말기를 포함한다.

한편, 본 발명의 바람직한 다른 실시예에 따른 키 관리 시스템은, 탈퇴를 요청한 구성원 노드(탈퇴 노드) 및 탈퇴 노드의 부모 노드를 삭제하고, 부모 노드에 속하는 인접 구성원 노드를 부모 노드의 레벨로 배치하는 구조 변경부, 인접 구성원 노드의 키 및 이전 세션의 그룹키를 이용하여 하위 레벨로부터 상위 레벨로 노드 키 값을 순차적으로 갱신하고, 갱신된 각 노드의 키 값을 이전 세션의 그룹키 및 갱신된 각 노드의 자식 노드 중 갱신되지 않은 자식 노드의 키값을 이용하여 블라인드하는 키 갱신부, 및 블라인드된 각 노드의 키 값을 포함하는 키 갱신 메시지를 생성하여 각 구성원 단말로 멀티캐스팅 전송하는 갱신 메시지 생성부를 포함하는 그룹 관리자 서버; 및 키 갱신 메시지에 따라서 자신의 대응 노드로부터 그룹 관리자 노드까지의 경로상에 위치하는 노드들의 키를 갱신하는 구성원 단말기를 포함한다.

이하, 첨부된 도면을 참조하여 본 발명의 바람직한 실시예들을 상세히 설명한다.

본 발명은 멀티캐스트 키 분배 방식에서 중앙 그룹 관리자 (또는 키 서버)가 개개의 수신자를 허가하고 인증할 수 있다고 가정한다. 따라서, 이 방식에서는 멀티캐스트되는 컨텐츠를 복호하고자 하는 수신자가 유니캐스트로 키 서버에 접속해서 복호화 키를 요구하면, 키 서버는 그 수신자를 표준 인증 프로토콜을 통해 인증하고, 안전한 (기밀성, 무결성, 인증을 제공하는) 채널을 확립한다. 그룹 관리자는 컨텐츠를 복호할 수 있는 그룹키와 키 관리 목적들을 위한 구성원 고유의 키들로 구성된 키 정보를 각 구성원에게 보낸다. 이 때, 멀티캐스트되는 정보는 기밀성 (confidentiality)과 접근권한(access control)을 유지하기 위해서 그룹키로 암호화된다.

본 발명은 종래 기술인 LKH의 이진 키 트리 구조에 기반하고 있다. 따라서, 본 발명의 이진 트리는 각 노드가 하나의 키에 대응되고 각 사용자-노드는 하나의 구성원에 대응되는 트리이다. 각 구성원은 자신의 구성원-노드부터 루트까지 경로내의 키를 알고있고, 그 이외의 키들은 알 수 없다고 가정한다. 이하에서는 구성원들의 집합을이라 하고, n개의 구성원-노드 (최하위 노드)를 가진 트리를 T 라 한다. 트리의 노드 (노드 키)들은 내부 노드들과 구성원-노드 (구성원 고유키)들로 구분된다. 각 노드에 하나의 노드 키 k_i 가 주어지고, i 는 키를 식별하는 인덱스로써 유일한 수이다. 트리에서 최하위 노드들은 각각 하나의 구성원 단말기 m 에 대응된다. 본 발명에서는 내부 키들을 KBK (Key Blind Key)라 정의하고, 구성원에 대응되는 최하위 노드 키를 구성원의 고유키로 정의한다.

그룹 관리자는 키 트리 T 를 유지하고, 각 사용자에게 대응되는 키-리스트 (구성원-노드부터 루트 노드까지 경로내에 대응되는 키)를 구성원들에게 안전한 채널로 전달한다. 구성원 m 의 구성원-노드의 상위 노드부터 루트 노드까지의 트리 경로내의 키의 집합을 AK(m)이라 할 때, 각 구성원은 자신의 고유키와 AK(m)을 유지하게 된다.

본 발명은 그룹 관리자가 갱신된 키들을 멀티캐스트할 때, 어떤 특정한 암호 알고리즘을 사용하지 않고, 일방향 함수와 XOR만을 이용해 변경된 키 값을 은닉해서 분배하는 효율적인 그룹키 관리 방법이다. 따라서, 이 키 갱신 메시지를 받은 구성원들은 복호화 과정 대신에 일방향 함수와 XOR만을 적용해서 변경된 키 값을 복원할 수 있다. 그리고 구성원 추가 오퍼레이션 동안에는 갱신된 키들을 구성원들에게 전달할 필요가 없다.

본 발명의 바람직한 실시예를 설명하기에 앞서, 본 발명의 키 관리 방법에서 수행되는 함수의 기능에 관하여 설명한다.

새롭게 추가된 구성원이 자신이 추가된 세션 이전의 콘텐츠를 복호화할 수 없도록하고(backward secrecy), 삭제한 구성원이 자신이 탈퇴한 세션 이후의 콘텐츠를 복호화할 수 없도록(forward secrecy)하기 위해서는, 추가되는 구성원들 또는 삭제되는 구성원들의 키-리스트에 포함되는 키들은 그룹의 구성원이 변동될 때마다 변경되야 한다.

먼저, 구성원 삭제시와 추가시에 다른 키들로부터 새로운 키들을 생성하기 위해서 다음의 수학식 1 에 기재된 갱신함수가 사용된다.

상기 수학식 1에서 함수 h 는 일방향 함수로서 본 발명에서는 해쉬 함수를 이용하고,는 일반적인 XOR 연산자이다. 함수 h는 본래의 값 및 그룹 키(GK)를 숨김으로써, 단지 또는 GK만 알고 있는 사람이 다른 값을 알 수 없게 만드는 역할을 수행한다. 는 및 GK의 값을 혼합함으로써 새로운 값을 생성하는 역할을 수행한다. 구성원 삭제시에 변경되야하는 키 k_i는 새로운 키 로 변경된다. 여기서 는 키 트리에서 인덱스 i 에 대응되는 노드의 왼쪽 또는 오른쪽 자식 노드에 대응되는 키로써 가장 최근의 키 (갱신된 키)이고, GK는 사건이 발생하기 바로 전 세션에서 구성원들이 가지고 있던 그룹키이다.

한편, 구성원 추가시, 새로 생성된 노드에 대응되는 키 k_i는 를 통해 생성된다. 여기서 GK 는 추가사건이 이어서 발생하는 경우에 새로 추가되는 구성원이 받은 정보로부터 이전의 키 값을 알아내는 것을 방지하는 역할을 하고, 함수 h 는 삭제된 구성원들과 새로 추가된 구성원들의 공모로부터 를 은닉하는 역할을 한다.

한편, 이전 세션의 키는 다음의 수학식 2 에 따라서 갱신된다.

상기 수학식 2에서 함수 h 는 일방향 함수로서 본 발명에서는 해쉬(hash) 함수를 이용한다.

한편, 갱신된 키들은 다음의 수학식 3에 의해서 은닉(블라인드)되고, 그룹 관리자는 정당한 구성원들만이 키를 얻을 수 있도록 하기 위해서 은닉된 값을 키 갱신 메시지에 포함시켜 멀티캐스트 채널로 전달한다.

상기 수학식 3 은 k 값을 이용하여 x 값을 블라인드하는 블라인드 함수를 나타낸 것으로, 본 발명의 바람직한 실시예에서, 구성원 삭제의 경우에 상술한 y 값으로서 이전 세션의 그룹키값(GK)을 이용하며, 구성원 추가의 경우에는 y 값으로서 x 를 블라인드 하는데 이용되는 키 k 의 인덱스를 이용한다. 여기에서 GK 는 사건이 발생할 때마다 전달되는 멀티캐스트 메시지로부터 키 값을 알아내는 것을 막기 위해서 사용되고, h 는 일방향 함수로써 키 값들을 숨기는 역할을 한다.

구성원 단말기는 상술한 수학식 3을 통해서 블라인드된 값으로부터 메시지를 얻기 위해 다음의 수학식 4 에 기재된 언블라인드 함수를 이용한다.

따라서, k 및 y 에 해당하는 키 값을 알고있는 구성원 단말기는 키 x 를 복원할 수 있다.

이하, 첨부된 도면을 참조하여 본 발명의 바람직한 실시예에 따른 그룹 키 관리 방법에 관하여 설명한다.

도 1 은 본 발명의 바람직한 실시예에 따른 키 갱신 메시지의 형식을 도시한 도면이다.

본 발명의 바람직한 실시예에서 이용되는 키 갱신 메시지(M_rkey)는 정당한 구성원들만이 갱신된 키들을 얻을 수 있도록 하기위해, 갱신된 키들은 앞에 붙여진 키 인덱스로 블라인드되어 있으나, 명령어들은 공개적으로 알려져도 안전성에 영향을 주지 않기 때문에 블라인드되지 않는다. 구성원들은 이 명령어들과 키 값들에 근거해서 어떤 키가 생성되어야 하고, 갱신되어야 하며, 대체되어야 하는지 알 수 있다.

이러한 키 갱신 메시지를 수신한 구성원은 키 갱신 메시지에서 두 가지 종류의 정보를 얻을 수 있는데, 하나는 키의 갱신여부를 나타내는 명령어이고 다른 하나는 새로운 키값이다. 이 두 종류의 정보 앞에는 키 인덱스 (키 식별자)가 포함된다. 본 발명의 바람직한 실시예에서는 명령어로서 +i, -i, 및 *i를 사용하며, 각각의 명령어는 키 i 의 추가, 삭제, 및 갱신을 나타낸다.

키 갱신 메시지를 수신한 구성원은 키 갱신 메시지에 자신이 가지고 있는 키들의 집합 (키-리스트)에 대응되는 명령어가 포함되어 있다면, 키 인덱스에 대응되는 키의 해당 (메시지에 명시된) 명령을 수행한다. 그리고 키 갱신 메시지에 키 값이 포함되어 있는 경우에 구성원은 먼저 메시지내에 자신이 가지고 있는 키 인덱스와 대응되는 인덱스가 존재하는지 확인한다. 만약 대응되는 인덱스가 존재한다면, 그 키 인덱스에 대응되는 키로 자신이 가지고 있는 키를 대체한다. 즉 블라인드된 키 값을 복원한다.

예컨대, 후술할 도 3 에 도시된 바와 같이 새로운 구성원 m₂ 가 추가될 경우에, 구성원들은 그룹 관리자로부터 키 갱신 메시지를 수신하게 된다. 구성원 m₁ 은 받은 명령어 (+)에 따라 노드 12를 새로 만들고 대응되는 키를 구한 후, 키 갱신 메시지내에 명시된 키들을 갱신한다. 그리고 나머지 구성원들은 키 갱신 메시지내에 자신이 가지고 있는 키-리스트에 대응되는 인덱스의 명령어 (*)를 실행한다.

이하, 도 2a 및 도 2b 를 참조하여, 본 발명의 바람직한 제 1 실시예에 따른 구성원 추가의 경우에 그룹 키 관리 방법을 설명한다.

도 2a 는 본 발명의 바람직한 제 1 실시예에 따른 키 관리 시스템의 구조를 도시하는 블록도이고, 도 2b 는 본 발명의 바람직한 제 1 실시예에 따른 키 관리 방법을 설명하는 흐름도이다.

제 1 실시예에 따른 키 관리 시스템은 구성원 단말기(30, 30-1 내지 30-n), 및 그룹 관리자 서버(20)를 포함하고, 그룹 관리자 서버(20)는 구성원 단말의 추가에 따른 이진 트리의 구조를 변경하고 새로운 개인키를 할당하는 구조 변경부(21), 구성원 노드의 추가에 따라서 노드들의 키 값을 갱신하는 키 갱신부(23), 키 갱신 메시지를 생성하여 구성원 단말들(30-1 내지 30-n)로 멀티캐스트 전송하는 갱신 메시지 생성부(25), 및 추가된 구성원 단말(30)로 블라인드된 키 값들을 유니캐스트 전송하는 유니캐스트 메시지 생성부(27)을 포함한다.

새로 추가될 구성원 단말기(30)로부터 가입 요청을 수신한 그룹 관리자(20)의 구조 변경부(21)는 그룹에 중간 내부 노드 및 구성원 노드를 새롭게 생성하여 기존의 트리 구조를 변경한다(S210). 이 때, 구조 변경부(21)는 트리를 가능한 작게 유지하기 위해서, 왼쪽에서부터 루트까지 경로가 가장 짧은 구성원 노드 x 자리에서부터 새로 추가되는 구성원-노드들을 트리에 추가한다.

구조 변경부는 가장 짧은 경로에 위치한 기존 구성원 노드 x 자리에 새로운 내부 노드 p 를 만들고 기존 구성원 노드 x를 내부 노드 p 의 왼쪽 자식 노드로, 새로운 구성원-노드를 오른쪽 자식 노드로 추가시키고, 갱신된 트리 에 영향 받는 노드들과 키들의 레벨을 재배열한다.

구조 변경부(21)는 새로 추가된 구성원-노드마다 키 집합에서 임의로 선택한 키를 할당하고, 새로운 구성원들을 새로운 구성원-노드에 대응시킨 후, 내부 노드의 키를 기존 구성원 노드의 고유키 및 그룹키를 이용하여 생성한다(S220).

그 후, 그룹 관리자(20)의 키 갱신부(23)는 생성된 내부 노드의 상위 레벨 노드들의 고유키를 일방향 함수에 대입하여 갱신한다(S230).

그룹 관리자(20)의 갱신 메시지 생성부(25)는 각 구성원들이 갱신된 노드 키들을 스스로 갱신할 수 있도록, 갱신된 키 인덱스를 포함하는 키 갱신 메시지를 생성하여 그룹 관리자에 속하는 구성원 단말들에게 멀티캐스팅한다.(S240).

또한, 그룹 관리자(20)의 유니캐스트 메시지 생성부(27)는 추가된 구성원 노드에 고유키 및 루트 노드까지의 경로에 위치하는 각 노드의 키값을 블라인드하여 유니캐스트 전송한다(S250).

각 구성원 단말들(30-1 내지 30-n)은 키 갱신 메시지를 수신하여 변경된 노드 키들을 스스로 갱신하고, 추가 구성원 단말(30)은 유니캐스트로 수신된 고유키 및 경로상의 내부 노드의 키값을 복원한다(S260).

하나의 구성원(m₂)이 추가되는 경우에 노드 구성도를 도시한 도 3을 더 참조하여, 구성원 추가의 경우의 그룹키 관리 방법을 자세히 설명한다.

도 3 에 도시된 바와 같이, 그룹 관리자는 새로운 구성원-노드 n₂ 와 새로운 노드 n₁₂를 추가시킴으로써 트리 구조를 갱신한다. 점선으로 표시된 노드의 레벨이 변경되므로 이 노드의 레벨을 재배열한다.

그룹 관리자는 새로 추가되는 구성원-노드 n₂ 에 구성원 m₂ 를 대응시키고, 고유키 k₂ 를 키 집합에서 임의로 선택해서 할당하고, 내부 노드(n₁₂)의 키를 생성하고 경로상의 다른 노드의 키들을 갱신한다.

먼저, 새롭게 생성되는 내부 노드 n₁₂의 키 값 k₁₂를 기존의 구성원 노드의 키값 k₁ 및 이전 세션의 그룹키값 k₁₈을 이용해서 구하는데, 본 발명에서는 k ₁ 과 k₁₈에 대해서 XOR(Exclusive OR) 연산을 수행하고, XOR의 연산 결과를 일방향 함수인 해쉬함수에 대입하여, 해쉬 함수값을 내부노드 n₁₂의 키 k₁₂로서 생성한다().

그 후, 그룹 관리자는 내부 노드 n₁₂의 상위 레벨 노드인 n₁₄ 및 n₁₈의 기존의 키 값을 일방향 함수인 해쉬 함수에 대입한 값으로, 키 값 k₁₄ 및 k₁₈을 갱신한다().

그룹 관리자는 구성원 노드들이 스스로 해당 경로의 노드키들을 갱신할 수 있도록 키 갱신 메시지를 작성하여 멀티캐스트 하는데, 상술한 예에서는 키 갱신 메시지 를 멀티캐스트한다.

한편, 그룹 관리자는 갱신된 트리상에 새로 추가되는 구성원 m₂ 에 대응하는 키를 블라인드하여 m₂ 에게 유니캐스트 채널로 안전하게 전달한다. sk₂ 를 그룹 관리자와 추가 구성원인 m₂ 가 사전에 공유한 세션키라 할 때, 그룹 관리자는 전송할 키값을 다음의 수학식 5 와 같이 순차적으로 블라인드 한다.

한편, 추가되는 구성원의 동기 m₁ 은 키 갱신 메시지를 수신한 후, 대응되는 첫 번째 명령어를 실행한다. 즉, 노드 n₁₂ 를 생성하여 이 노드를 자신의 구성원-노드 n₁ 의 상위 노드로 만든 후 레벨을 재배열하고, 자신의 개인키 k₁ 및 이전 세션의 자신의 부모 노드의 내부키 k₁₄의 XOR 연산 결과를 해쉬함수에 대입하여 새롭게 생성된 내부 노드의 내부키를 생성한다(). 그 후, m₁ 은 노드 n₁₄ 및 그룹 관리자 노드인 n₁₈ 의 키인 k₁₄ 및 k₁₈을 해쉬 함수에 대입하고, 해쉬 함수값으로 k ₁₄ 및 그룹키인 k₁₈을 갱신하므로써 두 번째와 세 번째 명령어를 실행한다(). 결국, m₁ 은 이전 세션의 자신의 노드로부터 그룹 관리자 노드까지의 경로상의 모든 키()을 알고 있으므로 스스로 키를 갱신할 수 있다.

한편, 다른 구성원들은를 수신한 후, 자신의 키-리스트에 대응하는 인덱스 14 및 18 에 대응하는 명령어를 실행한다().

도 4를 참조하여, 복수의 구성원이 기존의 그룹에 추가되는 경우의 그룹키 관리 벙법을 설명한다.

그룹 관리자는 도 4 에 도시된 바와 같이, 새로운 구성원 m₂ 및 m₃ 로부터 가입 요청을 수신하면, 새로운 내부 노드 n₁₂ 및 n₄₃을 생성하고, n₁₂ 의 자식 노드로서 기존의 구성원 노드 n₁ 및 추가 구성원 노드 n₂를 설정하고, n₄₃ 의 자식 노드로서 기존의 구성원 노드 n₄ 및 추가 구성원 노드 n₃를 설정한 후, 이 노드들과 키 레벨들을 재배열한다.

그룹 관리자는 새로 추가되는 구성원-노드 n₂ 및 n₃ 에 가입 요청한 구성원 m₂ 및 m₃를 각각 대응시키고, n₂ 및 n₃ 의 고유키 k ₂ 및 k₃를 각각 키 집합에서 임의로 선택해서 할당한다. 그리고 새로운 구성원의 추가로 인해서 영향 받는 노드들의 내부키들을 변경한다.

먼저, 새로 생성된 내부 노드 n₁₂ 및 n₄₃ 에 대응되는 내부키 k₁₂ 및 k ₄₃을 이전 세션의 그룹키 k₁₈ 및 이전 세션의 구성원의 고유키 k₁ 및 k₄를 각각 이용하여 생성한다(). 또한, 새로 생성한 중간 내부 노드의 부모 노드부터 루트 노드까지의 경로에 위치하는 내부 노드들의 키들을 기존의 키들을 이용하여 갱신하는데, 갱신 방법은 상술한 바와 같이 이전 세션의 기존 키들을 해쉬 함수에 대입한 결과값을 갱신된 키값으로 이용한다() 단, 이 키들은 한 세션에 한 번만 갱신된다.

내부 노드들의 키를 모두 갱신한 그룹 관리자는 기존의 각 구성원들이 스스로 해당 경로의 키들을 갱신할 수 있도록 키 갱신 메시지를 작성하여 멀티캐스트 하는데, 도 4 의 경우에서는 를 멀티캐스트한다.

한편, 그룹 관리자는 다음의 수학식 6 을 수행함으로써, 새롭게 생성된 키 및 갱신된 키들을 블라인드하여, 갱신된 트리상에 새로 추가되는 구성원 m₂ 에 대응하는 키를 m₂에게, 구성원 m₃ 에 대응하는 키를 m₃ 에게 유니캐스트 채널로 안전하게 전달한다.

한편, 기존의 구성원중 추가되는 m₂ 및 m₃ 의 동기인 m₁ 및 m₄ 는 상술한 키 갱신 메시지를 수신한 후, 자신들의 키-리스트에 대응되는 명령어를 수행하게 된다. 즉, m₁ 은 첫 번째 명령어에 따라서 새로운 노드 n₁₂ 를 생성하여 이 노드를 자신의 구성원-노드 n₁ 의 상위 노드로 만든 후 레벨을 재배열하고, 생성된 노드에 대응되는 키를 생성한다(). 그리고 세 번째와 네 번째 명령어를 실행하여, 노드 n₁₄ 및 그룹 관리자 노드인 노드 n₁₈의 내부 키(k₁₄) 및 그룹 키(k₁₈)를 갱신한다(). 구성원 m₄ 도 m₁과 동일한 방법으로 키들을 갱신한다.

한편, 기존의 다른 구성원들 는 M_rkey 를 수신한 후, 자신의 키-리스트와 대응되는 인덱스 18 에 대응되는 명령어를 실행한다().

이하, 도 5a 및 도 5b 를 참조하여 본 발명의 바람직한 제 2 실시예에 따른, 구성원 삭제시의 그룹키 관리 방법을 설명한다.

도 5a 는 본 발명의 바람직한 제 2 실시예에 따른 그룹키 관리 시스템의 구성을 도시한 블록도이다. 제 2 실시예의 그룹키 관리 시스템은 복수의 구성원 단말기(60, 60-1 내지 60-n), 및 그룹 관리자 서버(50)를 포함하고, 그룹 관리자 서버(50)는 구조 변경부(52), 키 갱신부(54), 및 갱신 메시지 생성부(56)를 포함한다. 구조 변경부(52)는 단순히 이진트리의 노드 구조만을 변경할 뿐 새로운 키를 생성하지 않는 점에서 도 2a 에 도시된 제 1 실시예의 구조 변경부(21)와 차이가 있고, 키 갱신부(54), 및 갱신 메시지 생성부(56)는 제 1 실시예의 키 갱신부(23), 및 갱신 메시지 생성부(25)와 그 기능이 유사하다.

구성원 삭제시의 그룹 키 관리방법은 그룹에서 삭제된 구성원이 알고 있는 모든 키를 삭제된 구성원이 계산할 수 없는 새로운 키로 변경해야하기 때문에 구성원 추가시의 그룹 키 관리 방법보다 복잡하다.

그룹 관리자의 구조 변경부(52)는 구성원들로부터 탈퇴 요청을 수신하면, 탈퇴 구성원 노드 및 탈퇴 구성원 노드의 부모 노드(과잉 내부 노드)를 삭제하고, 삭제된 부모 노드에 속하는 탈퇴 구성원 노드의 동기 노드를 삭제된 부모 노드의 위치에 배치하여 변경된 트리 구조를 생성한다(S510).

그 후, 그룹 관리자의 키 갱신부(54)는 그룹 키를 갱신하기 위해서 먼저 변경된 트리 구조에서 레벨이 변경된 노드 중 가장 왼쪽 구성원 노드m_x 의 고유키 k_x 를 이용해 다음의 수학식 7 에 따라서 하위 레벨의 노드 키부터 상위 레벨의 그룹 키까지 순차적으로 갱신한다(S520).

수학식 7에서 S_i 는 구성원들이 삭제되기 이전의 세션을 S_i+1 은 구성원들이 삭제된 후의 세션을 각각 의미한다.

키 갱신부(54)는 갱신된 각 노드의 키값을 이전 세션의 그룹키 및 갱신된 각 노드의 자식 노드 중 갱신되지 않는 자식 노드의 키값을 이용하여 블라인드 한다(S530).

그 후, 그룹 관리자의 갱신 메시지 생성부(56)는 각 구성원 노드가 갱신된 키를 계산할 수 있도록 키 갱신 메시지를 생성하여 각 구성원 노드에 멀티캐스팅 전송한다(S540). 키 생성 메시지에는 삭제되는 노드의 인덱스, 및 갱신된 각 노드의 블라인드된 키 값이 포함된다.

키 갱신 메시지를 수신한 각 구성원 노드들(60-1 내지 60-n)은 키 갱신 메시지에 자신의 키-리스트에 대응되는 인덱스가 존재하면 대응되는 명령어를 수행한다(S550). 구성원 노드들 중 삭제된 노드의 동기 노드는 부모 노드를 삭제하고, 이전 세션의 부모 노드의 상위 레벨 노드들의 키값을 수학식 7 에 따라서 갱신한다. 또한, 동기 노드는 키 갱신 메시지내에 자신이 갱신한 키로 블라인드된 키가 존재하면, 그 인덱스에 대응되는 키로 블라인드된 키를 언블라인드하여 갱신된 키를 복원한다.

한편, 삭제되는 구성원의 동기 이외의 그룹내의 모든 구성원들은 자신의 키 경로내의 키들을 알고 있고, 키 갱신 메시지의 키들은 이들 구성원들의 키 경로내의 키 중 하나의 키로 블라인드되어 있으므로, 이 키들을 갱신할 때 자신이 가지고 있는 노드의 위치 변경 없이 관리자가 멀티캐스팅한 키 갱신 메시지를 이용하여 키를 갱신할 수 있다. 따라서 이 구성원들은 키 갱신 메시지내의 키-리스트에 자신이 가지고 있는 키 인덱스들이 존재하면 그 인덱스에 대응되는 키를 이용해 블라인드된 키 값을 언블라인드함으로써 갱신된 키를 복원한다.

이하, 도 6을 참조하여, 한 명의 구성원(m₂)이 그룹내에서 삭제되는 경우의 그룹키 관리 방법을 상세히 설명한다.

탈퇴 요청을 구성원(m₂)으로부터 수신하면, 그룹 관리자는 구성원-노드 n₂ 를 삭제하고, 트리내의 과잉 내부 노드 n₁₂를 삭제한 후, 노드 n₁₂ 자리에 노드 n ₁을 배치하고 그대로 고유키 k₁ 을 할당하며 노드 n₁ 과 k₁ 의 레벨을 변경한다.

그 후, 그룹 관리자는 m₁ 의 고유키 k₁을 이용하여 하위 레벨 노드의 키부터 순차적으로 갱신한다. 도 6 을 참조하면, 그룹 관리자는 노드 n₁의 이전 세션의 고유키 k₁을 이용하여 노드 n₁₄ 의 키 k₁₄를 갱신한다(). 그 후, 갱신된 키 k₁₄를 이용하여 관리자 노드인 n₁₈의 키 k₁₈ 을 갱신한다().

그룹 관리자는 갱신된 키들을 구성원 노드들이 스스로 갱신할 수 있도록, 갱신된 키들을 블라인드하여 키 갱신 메시지를 생성하여, 각 구성원 노드들로 멀티캐스팅한다.

그룹 관리자는 이를 위해, 갱신된 각 노드의 자식 노드 중 갱신되지 않은 노드의 고유키와 이전 세션의 그룹키를 이용하여 갱신된 키를 블라인드한다. 구체적으로, 그룹 관리자는 이전 세션의 그룹키 k₁₈ 및 노드 n₁₄ 의 자식 노드인 노드 n₃₄ 의 키 k₃₄를 이용하여 에 따라서 갱신된 키 를 블라인드한값 을 생성한다. 마찬가지로, 그룹 관리자는 키 k₅₈을 이용하여 갱신된 키 을 블라인드한 값 을 생성한다.

그 후, 그룹 관리자는 각 구성원들이 스스로 키를 갱신할 수 있도록 키 갱신 메시지 을 생성하여 각 구성원 노드에 멀티캐스트 전송한다.

한편, 키 갱신 메시지를 수신한 삭제되는 구성원의 동기 m₁ 은 에 따라 노드 n₁₂ 와 k₁₂ 를 제거하고, 그 자리에 자신의 구성원-노드 n₁ 을 배치하고 고유키 k₁ 을 할당한다. 그 후, m ₁ 은 상위 레벨 노드인 n₁₄ 및 n₁₈의 키 값을 그룹관리자와 동일한 방식으로 순차적으로 갱신한다() .

한편, 다른 구성원들은 키 갱신 메시지 M_rkey 를 수신하고, 대응되는 [34: ] 를 실행한다. m₃ 및 m₄ 는 기존의 노드 n₃₄의 키값을 알고 있으므로, 키 k₃₄ 및 그룹키 k₁₈을 이용하여 블라인드된 값 을 언블라인드함으로써, 갱신된 키 를 복원한다(). 그리고 갱신한 로 블라인드된 값이 없으므로, k₁₈ 을 갱신한다. 갱신한 과 이전의 그룹키 k₁₈ 를 이용해 갱신된 그룹키 를 계산할 수 있다(). 마찬가지로은 수신된 M_rkey 에서 자신들의 키-리스트에 대응되는를 실행한다. 이미 알고있는 키 k₅₈ 와 그룹키 k₁₈ 을 이용해 를 언블라인드 함으로써 갱신된 그룹키 를 얻는다().

도 7을 참조하여 복수의 구성원이 삭제되는 경우의 그룹 키 관리 방법을 설명한다.

그룹 관리자는 복수의 구성원(m₂ 및 m₆)들이 동시에 삭제될 때, 먼저, 구성원-노드 n₂ 및 n₆ 를 제거하고, 트리내의 과잉 내부 노드 n₁₂ 및 n ₅₆를 제거한 후 그 자리로 n₁ 및 n₅ 를 차례대로 배치하고, 키 k₁, k₅ 를 할당한다. 그리고 n₁, k₁ 과 n₅, k₅ 의 레벨을 변경하므로써 전체 트리구조를 으로 새롭게 변경한다.

새롭게 변경된 트리 에서 갱신해야 하는 내부 키들은이므로, 먼저변경된 트리구조에서 가장 왼쪽의 키 k₁ 을 이용해 k₁₄ 및 k₁₈ 을 갱신한다( ). 그 후, 내부키 k₅₈을 로 갱신한다. 이 때, k₁₄ 및 k₁₈의 갱신 및 k₅₈의 갱신이 순차적으로 수행될 필요는 없고, 동시에도 수행 가능함은 물론이다.

그룹 관리자는 키 갱신을 완수한 후, 갱신된 키 값들을 블라인드한다. 키값을 블라인드하는 방법은 상술한 하나의 구성원이 삭제되는 경우와 동일하다.

그룹 관리자는 구성원 노드들이 스스로 키값을 갱신할 수 있도록 키 갱신 메시지를 각 구성원 노드에 멀티캐스팅하는데, 키 갱신 메시지는 삭제될 구성원 노드의 인덱스와 키가 갱신된 노드의 인덱스 및 그에 대응되는 블라인드된 키 값(, 및 )을 포함한다. 도 7 의 경우에 생성된 키 갱신 메시지는 와 같다.

수신된 갱신 메시지 에 따라서, 삭제되는 구성원의 동기인 구성원 m₁ 은 노드 n₁₂ 와 k₁₂ 를 제거하고, 그 자리에 자신의 구성원-노드 n₁ 을 배치하고 고유키 k₁ 을 할당한 후, 키 k₁₄ 및 k₁₈을 순차적으로 갱신한다( ).

마찬가지로, 구성원 m₅ 는 노드 n₅₆ 와 k₅₆ 을 제거하고 그 자리에 자신의 구성원-노드 n₅ 를 배치한 후 고유키 k₅ 를 할당한다. 키 k₅₆ 이 삭제되었으므로 k₅₈ 및 k₁₈은 갱신되어야 한다. m₅ 는 이미 알고 있는 k₅ 및 이전 세션의 그룹키 k₁₈을 이용하여 k₅₈을 갱신한다(). 그리고 이 갱신한 키 과 이전의 그룹키 k₁₈ 를 이용해서 블라인드된 갱신된 그룹키 을 복원한다 ()

한편, 다른 구성원들인 은 키 갱신 메시지 M_rkey 를 수신한 후에, 자신들의 키-리스트에 대응되는을 실행한다. 구성원는 가지고 있는 키 k₃₄ 를 이용해 블라인드 메시지 로부터 갱신된 키 를 복원한다(). 그리고 갱신한 와 이전의 그룹키 k₁₈ 을 이용해 그룹키 을 갱신한다().

마찬가지로, 은 자신들의 키-리스트에 대응되는[78: , 58 :] 를 실행한다. 우선, 이미 알고 있는 키 k₇₈ 와 그룹키 k₁₈ 을 이용해 블라인드된 키 로부터 키 을 계산한다(). 그리고 M_rkey 에 갱신한 키 로 블라인드된 값 이 존재하므로, 키 를 이용해서 새로운 그룹키를 얻을 수 있다().

이하, 표 1 내지 표 7을 참조하여, 본 발명에 따른 키 관리 방법(ELKH)과 종래의 EHBT 방식 및 ESSR (스테이트리시버를 위한 효율적인 그룹키 관리 방법)방식의 성능을 비교하여 본다.

표 2 내지 표 8 은 그룹 관리자의 계산량과 추가되는 구성원의 계산량, 추가되는 구성원/삭제되는 구성원의 동기 구성원의 계산량과 그 이외의 그룹에 다른 구성원들의 계산량과 멀티캐스트되는 키 갱신 메시지의 크기와 유니캐스트 메시지의 크기를 기재하였다. 먼저, 표 2 내지 표 8 에서 사용된 기호의 의미는 다음의 표 1 에 기재된 바와 같다.

n	그룹내 구성원들의 수
d	트리의 깊이(균형잡힌 트리에 대해서 d=log₂n)
I	하나의 키 인덱스의 bits사이즈
K	키 하나의 bits사이즈
G	키 생성 연산
H	해쉬 함수 연산
X	XOR 연산
E	암호화 연산
D	복호화 연산

표 2 에는 구성원 한 명 추가시에 그룹 관리자에게 요구되는 계산량과 추가되는 구성원 및 추가되는 구성원의 동기 구성원의 계산량, 그리고 그 이외의 다른 구성원들의 계산량을 기재하였다. 표 2 에서 다른 구성원들의 계산량은 모두 worst case 즉, 추가 사건으로 인해서 키 갱신 연산을 가장 많이 요하는 구성원들 에 대해 비교한다. 예컨대, 도 3 의 경우에, 구성원들의 경우에 대해서 기재하였다. 그리고, 표 3 에는 추가되는 구성원과 추가되는 구성원의 동기에게 유니캐스트로 보내는 메시지의 크기와 추가 오퍼레이션들을 수행하는 동안에 멀티캐스트되는 메시지의 크기를 기재하였다.

Scheme/ Resource	Computation
Scheme/ Resource	GC	Join member	Sib member	Max other member
EHBT	G+(d+1)(E+H+X)	(d+1)D	(d+1)(H+X)	(d-1)(H+X)
ESSR	(d+2)G+E+d(2H+3X)	D+d(H+2X)	d(H+2X)	(d-1)(H+2X)
ELKH	G+(2d+1)H+(2d+3)X	(d+1)(H+2X)	dH+X	(d-1)H

Scheme/ Resource	Size of Re-keying
Scheme/ Resource	Join Unicast	Sibling Unicast	Multicast
EHBT	(d+1)K	I	(d-1)I
ESSR	K	I	(2d+1)K
ELKH	(d+1)K	I	(d-1)I

표 4 및 표 5 는 여러명의 구성원들이 동시에 추가될 경우에 성능을 비교한 결과를 기재하였다. 각 비교 파라메터들은 표 2 및 표 3 에서 사용된 파라메터들과 같다. 표 4 및 표 5의 식들은 기존의 구성원들의 수가 두 배가되는 경우에 유효하다. 즉, 기존의 구성원들이 각자 하나의 동기 구성원을 얻고, 기존 트리내의 키들에 영향을 받는 모든 경우에 대해서 고려한다. 이렇게 기존의 구성원에 새로운 동기 구성원이 추가되는 경우는 추가 오퍼레이션 중에 키 갱신 연산량이 가장 많이 소요되는 worst case를 나타낸다. 표 4 및 표 5에서 n 은 추가사건이 발생하기 이전의 그룹의 구성원들의 수를, d 는 새롭게 변경된 트리의 깊이를 각각 나타낸다.

Scheme/ Resource	Comutation
Scheme/ Resource	GC	Join Member	Sib Member
EHBT	nG+n(d+1)E+(3n-1)(H+X)	(d+1)D	(d+1)(H+X)
ESSR	3nG+nE+(2n-1)(2H+3X)	D+d(H+2X)	d(H+2X)
ELKH	nG+(6n-3)H+(8n-4)X	(d+1)(H+2X)	dH+X

Scheme/ Resource	Size of Re-keying
Scheme/ Resource	Join Unicast	Sibling Unicast	Multicast
EHBT	n:(d+1)K	n:I	(n-1)I
ESSR	n:K	n:I	(4n-1)K
ELKH	n:(d+1)K	n:I	(n-1)I

본 발명의 키 관리 방법(ELKH)은 상술한 표에서 기재된 바와 같이, 다른 종래의 방식들과 비교할 때, 계산량의 측면에서 훨씬 효율적이라는 것을 알 수 있다.

한편, 표 6 은 단일 구성원 삭제시 그룹 관리자의 계산량, 삭제되는 동기의 계산량과 그 이외의 구성원들의 계산량과 멀티캐스트되는 키 갱신 메시지를 기재한다. 표에서 다른 구성원의 계산량은 단일 구성원 삭제로 인해서 키 갱신 연산을 가장 많이 소요하게되는 구성원들의 경우에 대해서 고려한다. 예컨대, 도 6 에서 구성원들의 경우이다.

그리고 여러명의 구성원이 동시에 삭제될 때의 연산량들을 표 7 에 기재하였다. 특히, 표 7 은 구성원들의 정확히 반이 그룹에서 삭제되는 상황에서의 연산량을 기재하였다. 삭제되는 모든 구성원들의 동기들이 트리내에 남게되고, 결과적으로 트리내의 모든 키들이 영향을 받는다. 표 6 및 표 7 에서는 n 이 삭제사건이 발생하기 이전의 그룹의 구성원들의 수를, d 가 새롭게 변경된 트리의 깊이를 각각 나타낸다.

Scheme/ Resource	Computation			Multicast
Scheme/ Resource	GC	Sib member	Max other member	Multicast
EHBT	(d-1)E+d(H+X)	d(H+X)	D+(d-1)(H+X)	I+(d-1)K
ESSR	dG+(d-1)(2H+3X)	(d-1)(H+2X)	(d-1)(H+2X)	I+(2d-1)K
ELKH	2(d-1)H+3(d-1)X	(d-1)(H+X)	(d-1)H+dX	I+(d-1)K

Scheme/ Resource	Computation		Multicast
Scheme/ Resource	GC	Sib member	Multicast
EHBT	(n-1)E+(2n-1)(H+X)	dD+(H+X)	nI+(n-1)K
ESSR	nG+(2n-1)(2H+3X)	d(H+2X)	nI+(2n-1)K
ELKH	2(n-1)H+3(n-1)X	d(H+2X)	nI+(n-1)K

구성원 삭제의 경우에도 본 발명의 키 관리 방법(ELKH)은 종래의 다른 방식보다 계산량에 측면에서 더 효율적이다. 왜냐하면, ELKH는 그룹 관리자가 갱신된 키를 분배할 때, 암호화 과정을 거치지 않고 일방향 함수와 XOR연산만을 사용해서 갱신된 키들을 블라인드하기 때문에 다른 구성원들이 갱신된 키를 얻기 위해서 복호화 과정 없이, 단지 일방향 함수연산과 XOR연산만을 수행하면 되고, 동기 구성원의 고유키가 변하지 않기 때문이다.

표 8 은 여러명의 구성원들이 동시에 추가되는 경우에 그룹 관리자와 추가되는 구성원 및 추가되는 구성원의 동기 구성원의 키 갱신 계산속도와 여러명의 구성원들이 삭제되는 경우의 계산속도를 분석한 것이다. 즉, 암호화, 복호화에 RC5 알고리즘을 사용하고, MD5 해쉬함수를 사용한다. 그리고 64비트 길이의 키들을 사용하고, 인텔 Pentium IV 프로세서 상에서 리눅스 gcc 버젼 3.2와 openssl 2.9.7 라이브러리를 사용하였다.

상술한 표 1 의 G 연산에 의해서 64비트 키를 생성할 경우에 2.88 ms가 소요되고, E 연산에 의해서 64비트 키를 이용해서 16 비트 키를 암호화하는 경우에 1·67 ms가 소요되며, D 연산에 수행에 1.43 ms가 소요되고, ,H 연산에 의해서 64비트 키를 해쉬할 경우에 0.50 ms가 소요되며, X 연산에 의해서 64비트 키를 XOR할 경우에 0.02 ms가 소요될 때, 다음의 환경하에서 키 갱신시에 어느 정도의 계산량이 요구되는지 실험한 결과를 표 8 에 기재하였다. 그룹에 16384명의 구성원이 존재한다고 가정한다. 그리고, 여러명의 구성원 추가 오퍼레이션 동안에 기존의 구성원의 두 배가 증가한 32768의 구성원이 그룹내에 존재하게 된다고 가정한다. 또한, 여러명의 구성원 삭제 오퍼레이션 동안에는 추가된 모든 구성원이 그룹에서 삭제된다고 가정한다. 결국, 그룹에는 기존의 16384명의 그룹 구성원이 존재하게 된다.

Scheme/ Resource	Multiple Joins			Multiple Revocations
Scheme/ Resource	GC	Join member	Sib member	GC	Sib member
EHBT	510525	22.88	8.32	22198.13	19.11
ESSR	203652	9.53	8.10	40958.54	7.28
ELKH	98958	8.64	7.52	8082.46	7.28

한편, 본 발명은 또한 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플라피디스크, 광데이터 저장장치 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다.

이제까지 본 발명에 대하여 그 바람직한 실시예들을 중심으로 살펴보았다. 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자는 본 발명이 본 발명의 본질적인 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현될 수 있음을 이해할 수 있을 것이다. 그러므로 개시된 실시예들은 한정적인 관점이 아니라 설명적인 관점에서 고려되어야 한다. 본 발명의 범위는 전술한 설명이 아니라 특허청구범위에 나타나 있으며, 그와 동등한 범위 내에 있는 모든 차이점은 본 발명에 포함된 것으로 해석되어야 할 것이다.

상술한 본 발명의 키 관리 방법은 키 갱신 메시지를 분배할 때, 암·복호화 과정 없이 일방향 함수와 XOR 연산만을 이용하고, 키 갱신시에도 일방향 함수와 XOR 연산만을 사용함으로 인해서, 다른 종래의 키 관리 방법과 비교하여 그룹 관리자와 그룹 구성원의 키 저장공간과 멀티캐스트되는 키 갱신 메시지의 크기를 증가시키지 않으면서, 그룹 관리자와 그룹 구성원들에게 키 갱신을 위해 요구되는 키 갱신 계산량을 대폭 줄일 수 있고, 따라서 키 갱신 속도가 향상되는 효과가 있다. 향상된 키 갱신 속도를 제공하는 본 발명은 그룹 관리자나 그룹 구성원들이 키 갱신에 소요하는 속도가 매우 중요시되는 모바일 멀티캐스트 등에 유용하게 사용될 수 있을 것이다.

도 2a 는 본 발명의 바람직한 실시예에 따른 그룹 키 관리 시스템의 구성을 도시하는 블록도이고, 도 2b 는 본 발명의 바람직한 실시예에 따른 구성원 추가의 경우에 그룹 키 관리 방법을 설명하는 흐름도이다.

도 3 은 한명의 구성원이 추가되는 경우에 본 발명의 바람직한 실시예에 따른 노드 구성도를 도시한 도면이다.

도 4 는 복수의 구성원이 추가되는 경우에 본 발명의 바람직한 실시예에 따른 노드 구성도를 도시한 도면이다.

도 5a 는 본 발명의 바람직한 다른 실시예에 따른 그룹 키 관리 시스템의 구성을 도시하는 블록도이고, 도 5b 는 본 발명의 바람직한 실시예에 따른 구성원 삭제의 경우에 그룹 키 관리 방법을 설명하는 흐름도이다.

도 6 은 한명의 구성원이 탈퇴하는 경우에 본 발명의 바람직한 실시예에 따른 노드 구성도를 도시한 도면이다.

도 7 은 복수의 구성원이 탈퇴하는 경우에 본 발명의 바람직한 실시예에 따른 노드 구성도를 도시한 도면이다.

Claims

이진 트리 기반의 멀티캐스트 통신 시스템에서, 그룹 관리자 서버에 대응되는 루트노드, 구성원 단말기에 대응되는 구성원 노드, 및 상기 루트노드와 구성원 노드를 연결하는 내부 노드들의 키를 관리하는 방법으로서,

(a) 상기 그룹 관리자 노드로부터 가장 가까운 기존 구성원 노드를 검색하여, 상기 기존 구성원 노드의 부모 노드의 자식 노드로서 중간 내부 노드를 생성하고, 상기 중간 내부 노드에 상기 기존 구성원 노드 및 추가 구성원 단말에 대응되는 추가 구성원 노드를 자식 노드로서 추가하는 단계;

(b) 상기 기존 구성원 노드의 고유키 및 그룹키를 이용하여 상기 중간 내부 노드의 키를 생성하는 단계;

(c) 상기 중간 내부 노드보다 상위 레벨의 내부 노드들의 키를 갱신하는 단계;

(d) 상기 갱신된 내부 노드들의 목록을 포함하는 키 갱신 메시지를 생성하여 구성원 노드들에 멀티캐스트 전송하는 단계;

(e) 상기 추가 구성원 노드부터 상기 루트노드까지의 경로에 위치하는 각 노드의 키값을 상기 추가 구성원 단말기에게 유니캐스트 전송하는 단계; 및

(f) 각 구성원 단말에서 상기 키 갱신 메시지를 수신하여, 상기 갱신된 내부 노드 목록에 대응되는 내부 키값들을 갱신하고, 상기 추가 구성원 단말에서 상기 각 노드의 키 값 및 고유키값을 복원하는 단계를 포함하는 것을 특징으로 하는 키 관리 방법.
제 1 항에 있어서, 상기 (b) 단계는

상기 기존 구성원 노드의 고유키값과 상기 루트노드의 키 값에 XOR(exclusive or)연산을 수행하여 상기 중간 내부 노드의 키값을 생성하는 것을 특징으로 하는 키 관리 방법.
제 2 항에 있어서, 상기 (b) 단계는

상기 XOR 연산 값을 일방향 함수에 대입한 값을 상기 중간 내부 노드의 키값으로서 생성하는 것을 특징으로 하는 키 관리 방법.
제 1 항에 있어서, 상기 (c) 단계는

상기 상위 레벨 노드들의 키 값을 일방향 함수에 대입한 결과 값으로 상기 상위 레벨 노드들을 갱신하는 것을 특징으로 하는 키 관리 방법.
제 1 항에 있어서, 상기 (e) 단계는

상기 추가 구성원 노드부터 상기 루트 노드까지의 경로에 위치하는 각 노드의 키값을 블라인드하여 유니캐스트 전송하는 것을 특징으로 하는 키 관리 방법.
제 5 항에 있어서,

추가 구성원 노드의 인덱스와 세션키의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수값과, 상기 추가 구성원 노드의 고유키값의 XOR 연산을 수행하여, 상기 추가 구성원 노드의 고유키값을 블라인드 하는 것을 특징으로 하는 키 관리 방법.
제 5 항에 있어서,

상기 추가 구성원 노드부터 상기 루트 노드까지의 경로에 위치하는 각 노드의 키 값은, 각 노드의 인덱스와 하위 노드의 키값의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수 값과, 상기 각 노드의 키 값의 XOR 연산을 수행하여 블라인드되는 것을 특징으로 하는 키 관리 방법.
제 5 항에 있어서, 상기 (f) 단계에서 상기 추가 구성원 단말은

상기 추가 구성원 노드의 인덱스와 세션키의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수값과 상기 블라인드된 고유키값의 XOR 연산을 수행하여, 상기 추가 구성원 노드의 고유키값을 복원하는 것을 특징으로 하는 키 관리 방법.
제 5 항에 있어서, 상기 추가 구성원 단말은

각 노드의 인덱스와 하위 노드의 키값의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수 값과 상기 블라인드된 각 노드의 개인 키값의 XOR 연산을 수행하여 상기 각 내부 노드의 키값을 복원하는 것을 특징으로 하는 키 관리 방법.
이진 트리 기반의 멀티캐스트 통신 시스템에서, 그룹 관리자 서버에 대응되는 루트 노드, 구성원 단말기에 대응되는 구성원 노드, 및 상기 루트 노드와 구성원 노드를 연결하는 내부 노드들의 키를 관리하는 방법으로서,

(a) 탈퇴를 요청한 구성원 노드(탈퇴 노드) 및 상기 탈퇴 노드의 부모 노드를 삭제하고, 상기 삭제된 부모 노드에 속하는 인접 구성원 노드를 상기 삭제된 부모 노드의 레벨로 배치하는 단계;

(b) 상기 인접 구성원 노드의 키를 이용하여 하위 레벨로부터 상위 레벨로 노드 키 값을 순차적으로 갱신하는 단계;

(c) 갱신된 각 노드의 키 값을 이전 세션의 그룹키 및 갱신된 각 노드의 자식 노드 중 갱신되지 않은 자식 노드의 키값을 이용하여 블라인드하는 단계;

(d) 블라인드된 각 노드의 키 값을 포함하는 키 갱신 메시지를 각 구성원 단말로 멀티캐스팅 전송하는 단계; 및

(e) 상기 키 갱신 메시지에 따라서 구성원 단말들이 키 갱신을 수행하는 단계를 포함하는 것을 특징으로 하는 키 관리 방법.
제 10 항에 있어서, 상기 (b) 단계는

하위 레벨인 자식 노드의 갱신된 키 값과 이전 세션의 그룹키를 이용하여 상위 레벨인 부모 노드의 키 값을 갱신하는 것을 특징으로 하는 키 관리 방법.
제 11 항에 있어서, 상기 (b) 단계는

자식 노드의 갱신된 키 값과 이전 세션의 그룹키값에 XOR 연산을 수행한 값을 일방향 함수에 대입한 결과값을 부모 노드의 키 값으로 갱신하는 것을 특징으로 하는 키 관리 방법.
제 10 항에 있어서, 상기 (c) 단계는

이전 세션의 그룹 키와 상기 갱신되지 않은 자식 노드의 키값을 XOR 연산을 수행한 결과값을 일방향 함수에 대입한 결과값으로 상기 갱신된 각 노드의 키 값을 블라인드 하는 것을 특징으로 하는 키 관리 방법.
제 13 항에 있어서,

상기 일방향 함수의 연산 결과값과 상기 갱신된 노드의 키 값을 XOR 연산하여 상기 갱신된 노드의 키 값을 블라인드하는 것을 특징으로 하는 키 관리 방법.
제 10 항에 있어서, 상기 (e) 단계에서

상기 갱신 메시지를 수신한 구성원 단말들은 블라인드된 키 값을, 이전 세션의 그룹키 및 블라인드된 키의 자식 노드의 키 값을 이용하여 언블라인드함으로써, 갱신된 각 노드의 키 값을 복원하는 것을 특징으로 하는 키 관리 방법.
제 15 항에 있어서,

상기 갱신 메시지를 수신한 구성원 단말들은, 상기 이전 세션의 그룹키 및 블라인드된 키의 자식 노드의 키 값에 XOR 연산을 수행하고, 상기 XOR 연산 결과값의 해쉬 함수값과 상기 블라인드된 키 값들의 XOR 연산을 수행하여 갱신된 각 노드의 키 값을 복원하는 것을 특징으로 하는 키 관리 방법.
제 3 항, 제 4 항, 제 12 항, 및 제 13 항 중 어느 한 항에 있어서, 상기 일방향 함수는 해쉬 함수인 것을 특징으로 하는 키 관리 방법.
제 1 항 내지 제 16 항 중 어느 한 항의 키 관리 방법을 컴퓨터에서 판독할 수 있고, 실행 가능한 프로그램 코드로 기록한 기록 매체.
이진 트리 기반의 멀티캐스트 통신 시스템에서, 그룹 관리자 서버에 대응되는 루트 노드, 구성원 단말기에 대응되는 구성원 노드, 및 상기 루트 노드와 구성원 노드를 연결하는 내부 노드들의 키를 관리하는 시스템으로서,

상기 루트 노드로부터 가장 가까운 기존 구성원 노드를 검색하여, 상기 구성원 노드 위치에 중간 내부노드를 생성하고, 상기 중간 내부 노드의 자식 노드로서, 기존 구성원 노드 및 추가 구성원 단말에 대응되는 구성원 노드를 추가한 후, 상기 기존 구성원 노드의 고유키 및 그룹키를 이용하여 상기 중간 내부 노드의 키를 생성하는 구조 변경부,

상기 내부 노드보다 상위 레벨의 내부 노드들의 키를 갱신하는 키 갱신부,

상기 갱신된 내부 노드들의 목록을 포함하는 키 갱신 메시지를 생성하여 구성원 노드들에 멀티캐스트 전송하는 갱신 메시지 생성부, 및

상기 추가 구성원 노드부터 상기 루트 노드까지의 경로에 위치하는 각 노드의 키값을 상기 추가 구성원 단말로 유니캐스트 전송하는 유니캐스트 메시지 생성부를 포함하는 그룹 관리자 서버;

상기 키 갱신 메시지를 수신하여, 상기 갱신된 내부 노드 목록에 대응되는 내부 키값들을 갱신하는 복수의 구성원 단말기; 및

상기 유니캐스트 메시지에 따라서 상기 각 노드의 키 값 및 고유키값을 복원하는 추가 구성원 단말기를 포함하는 것을 특징으로 하는 키 관리 시스템.
제 19 항에 있어서, 상기 구조 변경부는

상기 기존 구성원 노드의 고유키값과 상기 루트 노드의 키 값에 XOR(exclusive or)연산을 수행하여 일방향 함수에 대입한 값을 상기 중간 내부 노드의 키값으로서 생성하는 것을 특징으로 하는 키 관리 시스템.
제 19 항에 있어서, 상기 키 갱신부는

상기 상위 레벨 노드들의 키 값을 일방향 함수에 대입한 결과 값으로 상기 상위 레벨 노드들을 갱신하는 것을 특징으로 하는 키 관리 시스템.
제 19 항에 있어서, 상기 유니캐스트 메시지 생성부는

상기 추가 구성원 노드부터 상기 루트 노드까지의 경로에 위치하는 각 노드의 키값을 블라인드하여 유니캐스트 전송하는 것을 특징으로 하는 키 관리 시스템.
제 22 항에 있어서, 유니캐스트 메시지 생성부는

추가 구성원 노드의 인덱스와 세션키의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수값과, 상기 추가 구성원 노드의 고유키값의 XOR 연산을 수행하여, 상기 추가 구성원 노드의 고유키값을 블라인드 하는 것을 특징으로 하는 키 관리 시스템.
제 22 항에 있어서, 유니캐스트 메시지 생성부는

상기 추가 구성원 노드부터 상기 루트 노드까지의 경로에 위치하는 각 노드의 키 값은, 각 노드의 인덱스와 하위 노드의 키값의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수 값과, 상기 각 노드의 키 값의 XOR 연산을 수행하여 블라인드되는 것을 특징으로 하는 키 관리 시스템.
제 22 항에 있어서, 상기 추가 구성원 단말기는

상기 추가 구성원 노드의 인덱스와 세션키의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수값과 상기 블라인드된 고유키값의 XOR 연산을 수행하여, 상기 추가 구성원 노드의 고유키값을 복원하는 것을 특징으로 하는 키 관리 시스템.
제 22 항에 있어서, 상기 추가 구성원 단말기는

각 노드의 인덱스와 하위 노드의 키값의 XOR 연산 결과를 해쉬 함수에 대입하여 구한 해쉬 함수 값과 상기 블라인드된 각 노드의 개인 키값의 XOR 연산을 수행하여 상기 각 내부 노드의 키값을 복원하는 것을 특징으로 하는 키 관리 시스템.
이진 트리 기반의 멀티캐스트 통신 시스템에서, 그룹 관리자 서버에 대응되는 루트 노드, 구성원 단말기에 대응되는 구성원 노드, 및 상기 루트 노드와 구성원 노드를 연결하는 내부 노드들의 키를 관리하는 시스템으로서,

탈퇴를 요청한 구성원 노드(탈퇴 노드) 및 상기 탈퇴 노드의 부모 노드를 삭제하고, 상기 삭제된 부모 노드에 속하는 인접 구성원 노드를 상기 삭제된 부모 노드의 레벨로 배치하는 구조 변경부,

상기 인접 구성원 노드의 키를 이용하여 하위 레벨로부터 상위 레벨로 노드 키 값을 순차적으로 갱신하고, 갱신된 각 노드의 키 값을 이전 세션의 그룹키 및 갱신된 각 노드의 자식 노드 중 갱신되지 않은 자식 노드의 키값을 이용하여 블라인드하는 키 갱신부, 및

블라인드된 각 노드의 키 값을 포함하는 키 갱신 메시지를 생성하여 각 구성원 단말로 멀티캐스팅 전송하는 갱신 메시지 생성부를 포함하는 그룹 관리자 서버; 및

상기 키 갱신 메시지에 따라서 자신의 대응 노드로부터 루트 노드까지의 경로상에 위치하는 노드들의 키를 갱신하는 구성원 단말기를 포함하는 것을 특징으로 하는 키 관리 시스템.
제 27 항에 있어서, 상기 키 갱신부는

하위 레벨인 자식 노드의 갱신된 키 값과 이전 세션의 그룹키를 이용하여 상위 레벨인 부모 노드의 키 값을 갱신하는 것을 특징으로 하는 키 관리 시스템.
제 28 항에 있어서, 상기 키 갱신부는

자식 노드의 갱신된 키 값과 이전 세션의 그룹키값에 XOR 연산을 수행한 값을 일방향 함수에 대입한 결과값을 부모 노드의 키 값으로 갱신하는 것을 특징으로 하는 키 관리 시스템.
제 27 항에 있어서, 상기 키 갱신부는

이전 세션의 그룹 키와 상기 갱신되지 않은 자식 노드의 킷값에 대해서 XOR 연산을 수행한 결과값을 일방향 함수에 대입하여 상기 갱신된 각 노드의 키 값을 블라인드 하는 것을 특징으로 하는 키 관리 시스템.
제 27 항에 있어서, 상기 구성원 단말기는

블라인드된 키 값을, 이전 세션의 그룹키 및 블라인드된 키의 자식 노드의 키 값을 이용하여 언블라인드함으로써, 갱신된 각 노드의 키 값을 복원하는 것을 특징으로 하는 키 관리 시스템.
제 31 항에 있어서, 상기 구성원 단말기는

상기 갱신 메시지를 수신한 구성원 노드들은, 상기 이전 세션의 그룹키 및 블라인드된 키의 자식 노드의 키 값에 XOR 연산을 수행하고, 상기 XOR 연산 결과값의 해쉬 함수값과 상기 블라인드된 키 값들의 XOR 연산을 수행하여 갱신된 각 노드의 키 값을 복원하는 것을 특징으로 하는 키 관리 시스템.