Complete Subtree scheme(CS) [1] is a well known broadcast encryption scheme to perform group rekeying in a stateless manner. However, statelessness comes at a cost in terms of storage and message overhead in transmitting key material. We propose a Merged Complete Subtree scheme(MCS) to reduce the communication overhead. It is more practical to make broadcast encryption schemes in network environments with limited bandwidth resources. We define all possible subset unions of CS as new subsets having own key. The modification causes more storage overhead. Nevertheless, our evaluation shows that the proposed scheme significantly improves the communication overhead of CS, reducing by half the rekey communication cost. The proposed scheme has the advantage of rekey communication cost when the number of revoked users is significant percentage of the number of potential users. The proposed scheme is fully collusion resistant.
Complete Subtree(CS) 기법은 잘 알려진 브로드캐스트암호화기법 중 비상태성을 만족시키는 방법으로 그룹의 키의 배포 및 업데이트를 수행하는 방법이다. 브로드캐스트가 서비스 제공자로부터 단방향으로 이루어지는 환경에서 서비스 제공자가 사용자의 과거 키에 대한 기록 여부를 확인할 수 없는 비상태적인 상황을 만족시키기 위한 브로드캐스트암호화기법은 키 관련 자료를 주기적으로 메시지와 함께 전송하여야 하며 이때 저장 오버헤드와 통신 오버헤드가 발생한다. 본 논문을 통하여 두 가지 오버헤드 중 통신 오버헤드를 최소화하기 위한 Merged Complete Subtree(MCS) 기법을 제안한다. 이런 MCS기법은 제한된 대역폭을 가지는 네트워크 환경에서 보다 실용적인 기법이라 할 수 있다. MCS기법에서는 CS기법에서 사용된 부분집합의 가능한 모든 두 합집합을 키를 가지는 새로운 부분집합으로 정의한다. 이 수정 사항은 분명 더 많은 저장 오버헤드를 필요로 하지만 우리가 제안한 기법에서의 통신 오버헤드가 CS기법과 비교했을 때 현격하게 개선되었음을 보이며 그 양은 CS기법의 절반에 해당한다. 제안된 MCS기법은 그룹커뮤니케이션에서 전체 잠재적 사용자에 대한 탈퇴한 사용자가의 비율이 커졌을 때 보다 큰 이득을 가지며 공모를 통한 공격에 대하여 완벽한 저항성을 가진다.
