α分木ハフマン法を用いたグループ鍵管理方式: 坂本 一仁
α分木ハフマン法を用いたグループ鍵管理方式
坂本 一仁 (0751054)
長期間に渡る運用でも鍵更新の効率が劣化しないようなグループ鍵管理方式を提案する．
グループ鍵管理方式としてLKH法が広く知られている．LKH法は信頼できる鍵管理サーバ
の存在を仮定し，鍵木と呼ばれる木構造を用いることで，グループ鍵を安全かつ効率的
に管理する方法である．この方式は汎用性が高く，例えば，一定期間内の加入者および
脱退者をまとめて更新するバッチ型LKH法への拡張も可能である．これらの方式の効率
は，鍵管理者の内部データ構造である鍵木の構造に大きく依存する．一般に，長期間の
運用にともなって鍵更新を多数繰り返すと，鍵木のバランスが次第に崩れ，効率の劣化
が必要以上に大きくなる．本論文では，木構造の外部経路長に着目し，鍵更新時にハフ
マンアルゴリズムを用いて鍵木を常に最適な構造に組み直すことにより，LKH法の性能
劣化を最小限に食い止める手法を提案する．予備的検討により，鍵木の分岐数が 2 の
場合の有効性についてはすでに確認されているが，本論文では鍵木の分岐数をα(>2)に
拡張し，その性能を評価する．性能評価に当たっては，ポアソン分布により与えられる
確率モデルを用いてグループメンバの振る舞いを表現する．提案法について，鍵木の分
岐数を変化させながら，現実的な実験モデルによる詳細な性能評価を行った結果，鍵木
の分岐数を4に設定することが最も効率的であり，どのような実験モデルにおいても鍵木
のバランス（外部経路長）が最適に保たれることを確認できた．これにより，提案法は
常に鍵更新コストを最小化し，大規模グループにおける長期的な鍵管理に有用性がある
といえる．