k互換なセパレータの族について

概要

論文の詳細を見る
本報告では, 有向閉路を持たない有向グラフの上でk互換なセパレータの族という概念を定義し, k=1の場合について, グラフの点数に対するk互換なセパレータの族のサイズの上界を明らかにする. この概念は, 情報セキュリティの分野において, One-time署名およびこの拡張であるk-time署名を実現するための中核となる概念である. 従来の代表的な署名方式としては共通鍵暗号方式や公開鍵暗号方式をほぼそのままの形で利用した署名方式がよく知られているが, 前者は鍵配送が不便であり, 後者は速度の点に問題点がある. これら双方の問題点を解決した署名方式としてLamportらによってOne-time署名方式が以前より提案され, 改良されてきた. しかし, この署名方式には署名を行う毎に鍵の設定および配送が必要になり, 効率の点に最も大きな問題点がある. 本報告は, One-time署名の効率の上界を明らかにしつつ, グラフ理論上の問題として扱うことによってk-time署名への拡張を目指すものである.
社団法人電子情報通信学会の論文
1997-06-26