ユーザの加入や脱退など，グループメンバが変動するようなグループにあっては，グループ鍵を更新し, 適切に再配布する手続きが必要となる．たとえば，あるユーザがグループから脱退する場合， そのユーザは，脱退後にグループ内で流通する情報へのアクセスを禁止する必要がある．脱退ユーザ からグループ鍵を没収することは技術的に困難であるため，グループ鍵を更新し， グループに残るメンバにだけ新しいグループ鍵を配布する必要が生じるが，グループサイズが大きい場合， 各メンバに対して個別に新しいグループ鍵を配布するのは効率的であるとはいえない．
安全かつ効率的にグループ鍵を管理する手法について，これまで多くの研究がなされている．もっとも よく知られているグループ鍵管理手法として，LKH法(Logical Key Hierarchy)がある． LKH法では，鍵木と呼ばれる木構造に基づいて，ユーザに配布する鍵情報を管理する． 鍵木の葉とグループメンバとは一対一に対応しており，ユーザの新規加入や脱退は， ある種の操作を鍵木に対して行うことで実現される．また，LKH法の一般化として， バッチ型LKH 法に関する研究もなされて いる．グループのサイズが大きくなる場合，ユーザの加入や脱退も頻 繁に発生すると考えられるが，これらユーザの加入・脱退イベントに対して個 別に LKH 法を適用したのでは，効率が悪くなってしまう． そこで，一定の期間内に発生するユーザ加入・脱退への 対応をバッチ的に処理することが現実的であると考えられる．バッチ型LKH 法では，複数ユーザの加入・脱退操作を同時に実行することで，鍵更新にかか るオーバヘッドを削減可能とする．
LKH 法，バッチ型 LKH 法の効率は，鍵木における葉の平均深さに大きく依存する． 葉の平均深さが大きくなるほど，鍵更新にかかるオーバヘッドは大きくなるため，鍵 木はできるだけ低く，かつバランスしていることが望ましい．一方，ユーザの加入・ 脱退にともなって鍵木の形は変化するため，グループ鍵の更新を繰り返すと， 鍵木のバランスが崩れるおそれがある． LKH 法では鍵木を再構成する手段が準備されていないため，鍵 木のバランスが一度崩れると，本来の性能を取り戻すことは困難である． LKH 法の鍵更新の手順を詳細に検討すると，グループ鍵の更新は，鍵木を分解し， 再構成する手順であると考えることができる．
LKH 法では，グループを脱退するユーザの先祖にあたる節 点のノード鍵を無効化するが，これにともない，鍵木は複数の部分木に分解さ れる．ここに新規加入ユーザを加え，複数に分割された部分木を再び一つの鍵 木に構成しなおすことで，新しいグループ鍵の共有を実現する． 木構造を再構成する目的は， 分解された部分木を再び一個の木として結びつけることにあり，結果として得 られる木構造が当初の木構造と異なっていても，グループ鍵の管理上は問題な い．また，詳しくは本文中で議論するが，木の再構成にかかるオーバヘッドは， 再構成される鍵木の構造とは無関係であり，再構成される鍵木を自由に選ぶこ とについて，なんら追加のコストは発生しない．
本発表では，ハフマンアルゴリズムを用いることで鍵木構造を最適な状態に保つ鍵管理法 を紹介し，提案法における新規ユーザの加入操作を3種(単一木構成法・単節点構成法・バランス部分木構成法)紹介する． さらに，提案法の鍵更新効率について議論を行う．また，計算機実験により， 鍵更新コストや鍵木の構造パラメータを詳細に評価し，既存研究より 提案法が優れていることを示す．