参加者が多いいくつかのアクセス構造に対する秘密分散法の最悪情報レートについて

摘要

秘密分散法は秘密情報を参加者間で安全に分散共有する方式である．秘密分散法は有資格集合に属する参加者集合の部分集合からは秘密情報が復元され，禁止集合に属する参加者集合の部分集合からは秘密情報が一切漏れないように構成される．近年，Komargodskiらが[3]でディーラーが可算無限の参加者に対してシェアを逐次的に配布するEvolving型の秘密分散法を提案した．しかし，［3］で提案されている方式は簡単なしきい値型のアクセス構造でさえ最悪情報レートは0になってしまう．本稿では，Evolving型の秘密分散法では最悪情報レートが正の定数となるような例を提示する．そして，導出した最悪情報レートを情報理論的な不等式を用いて評価する．また，偶数角形のグラフ型アクセス構造をもつ秘密分散法に関しても最悪情報レートの上界と下界を与える．