最小配置証明書分散問題に対する多項式時間2近似アルゴリズムについて Hardness and an Approximation Algorithm for Minimum Certificate Dispersal Problems

本論文では公開鍵証明書と呼ばれるデータを用いた安全な通信を行うネットワークを考える.ネットワーク上で発行されたすべての公開鍵証明書は有向グラフでモデル化される.任意の2ユーザuからvへ通信を行う場合, uはvの公開鍵を必要とする.その際ユーザuはuに保存されている公開鍵証明書とvに保存されている公開鍵証明書を用いてvの公開鍵を獲得する事ができる.従って, uがvへ安全に通信を行うためにはuとv中にuがvの公開鍵を獲得しうる為に十分な量の公開鍵証明書が保存されている必要がある.本論文では公開鍵証明書をどのように各ユーザに分散するかという問題をMINIMUM CERTIFICATE DISPERSAL PROBLEM(MCD)として定式化した.そしてMCDのいくつかの制限された問題がNP-完全であることを示した.また, 強連結グラフを入力とするMCDに対する多項式時間2-近似アルゴリズムを示し, そのアルゴリズムは木, リング, 超立方体, 格子そしてトーラスにおいて最適解を出力する事を示した.

We consider a network, where a special data called certificate is issued between two users and all certificates issued by the users in the network can be represented by a directed graph. For any two users u and v, when u needs to send a message to v securely, v's public-key is needed. The user u can obtain v's public-key using the certificates stored in u and v. We need to disperse the certificates to the users such that when a user wants to send a message to the other user securely, there are enough certificates in them to get the reliable public-key. In this paper, we formulate this problem as MINIMUM CERTIFICATE DISPERSAL PROBLEM(MCD). We show that some special cases of MCD are NP-Complete. We also present a polynomial-time 2-approximation algorithm MinPivot for strongly connected graphs of the restricted case of MCD which is NP-Complete. We introduce some graph classes for which MinPivot can compute optimal dispersals, such as trees, rings, hypercubes, meshes, and tori.