■平成14年度 卒業論文

●八反田 一宏

電子透かしとは，データの中に情報を埋め込む手法である．例えばデータに著 作権情報を埋め込むことで，データの不正コピーに対して著作権を主張するこ とができる．電子署名も電子透かしと類似の概念である(本研究の範囲内では 同一視して良い)．

Davidsonらは，プログラムコードの基本ブロックを並べ替 えて電子署名を構成する方法を考案した．基本ブロックとは，連続した命令列 からなり，先頭の命令に制御が与えられ，途中で分岐することなく終端で制御 を離れるものをいう．実行順序さえ保持すれば，基本ブロックの アドレスは自由に変更することができる．ただし，実行順序を保持するにはジャ ンプ命令を挿入しなければならないので，プログラムの性能は低下する．

本研究では，Davidsonらの方法をMIPS命令セットを用いて実装し，署名前後の 実行命令数比とプログラムサイズ比，埋め込み可能な情報量を定量的に評価し た．

●山本 浩司

2つのグラフ$G_\alpha$，$G_\beta$が与えられたとき，$G_\alpha$が $G_\beta$のいずれかの部分グラフと同型か否か判定する問題を“部分グラフ 同型判定問題”と呼ぶ．$G_\alpha$から$G_\beta$への写像のう ち，隣接関係(辺)が保持されるような写像を探す問題と言い換えても良い．こ の問題は幅広い応用を持つが，一般にNP完全で，実用時間で解くことは困難で ある．

部分グラフ同型判定問題を高速に解く手法として，専用回路の利用が考えられ ている．Ullmannの回路は有効であるが，回路規模が大きくなる ため実装困難である．

Ullmannの回路をデータ依存回路で実装すると回路規模が減少することが知ら れている．一般に入力が定数であれば論理回路を簡単化できる ので，入力データごとに専用回路を生成すると回路規模を削減できる．この場 合，生成された回路は入力データに依存するので“データ依存回路”とよぶ．

小西のアルゴリズムは，Ullmannのアルゴリズムよりも枝刈りが 単純である．そのためUllmannのアルゴリズムより小さい回路で実装すること ができる．本研究では，小西のアルゴリズムの隣接判定部分をデータ依存回路 で実装し，その回路規模と判定時間を評価する．