クリーク問題を用いたスパム対策用プライシング関数に関する研究

砂見 渉 (0451069)


近年のネットワーク社会において, ユーザの負荷やネットワークトラフィックの増大を 引き起こすスパムメール(スパム)の氾濫が深刻な問題となっている.

スパム対策の一環として, 電子メールを一通送信する毎に, メール送信ユーザにコストを支払わせ てメールの大量送信を抑制する手法が研究されている. ここでいうコストとは計算資源 (時間, 計算パワー)のことであり, 実際にはプライシング関数と呼ばれる関数の計算を 課すことになる. これにより単位時間当りに送信可能な電子メールの数を制限すること ができ, スパムが抑制されることが期待できる. しかしながら適当なプライシング関数 はいまだ提案されておらず, その構成法が重要な問題点となっている.

本発表では, 始めにスパムメールの現状を報告し, 続いてプライシング手法の既存研究 を紹介する. さらにNP完全問題をプライシング関数に応用する提案手法を紹介し, その 利用法と問題点について述べる. また, NP完全問題の一つであるクリーク問題を用いた プライシング関数の構成法を提案する. 提案する構成法では平均計算量の下界に関する 既存研究の結果を利用しており, より公平で実用的なプライシング関数の実現になって いると考えられる.